Maximaler Fluss und das lineare Zuordnungsproblem

Hier ist ein Problem: Ihr Unternehmen beauftragt Auftragnehmer mit der Erfüllung von Verträgen. Sie sehen Ihre Dienstpläne durch und entscheiden, welche Auftragnehmer für ein einmonatiges Engagement verfügbar sind, und Sie sehen Ihre verfügbaren Verträge durch, um zu sehen, welche davon für Aufgaben mit einer Dauer von einem Monat sind. Da Sie wissen, wie effektiv jeder Auftragnehmer jeden Vertrag erfüllen kann, wie weisen Sie Auftragnehmer zu, um die Gesamteffektivität für diesen Monat zu maximieren?

Dies ist ein Beispiel für das Zuordnungsproblem, und das Problem kann mit dem klassischen ungarischen Algorithmus gelöst werden.

Der ungarische Algorithmus (auch als Kuhn-Munkres-Algorithmus bekannt) ist ein polynomieller Zeitalgorithmus, der die Gewichtungsanpassung in einem gewichteten zweiteiligen Diagramm maximiert. Hier können die Kontrahenten und die Verträge als bipartiter Graph modelliert werden, mit ihrer Wirksamkeit als Gewichte der Kanten zwischen den Kontraktoren- und den Vertragsknoten.

In diesem Artikel lernen Sie eine Implementierung des ungarischen Algorithmus kennen, die den Edmonds-Karp-Algorithmus verwendet, um das lineare Zuordnungsproblem zu lösen. Sie erfahren auch, dass der Edmonds-Karp-Algorithmus eine leichte Modifikation der Ford-Fulkerson-Methode ist und wie wichtig diese Modifikation ist.

Das Maximum-Flow-Problem

Das Problem des maximalen Durchflusses selbst kann informell als das Problem beschrieben werden, eine Flüssigkeit oder ein Gas durch ein Rohrnetz von einer einzelnen Quelle zu einem einzelnen Terminal zu bewegen. Dies erfolgt unter der Annahme, dass der Druck im Netz ausreicht, um sicherzustellen, dass die Flüssigkeit oder das Gas nicht in einer beliebigen Rohrlänge oder Rohrverbindung (den Stellen, an denen unterschiedliche Rohrlängen zusammentreffen) verweilen kann.

Durch bestimmte Änderungen am Graphen kann das Zuordnungsproblem in ein Maximum-Flow-Problem umgewandelt werden.

Vorläufe

Die Ideen, die zur Lösung dieser Probleme benötigt werden, entstehen in vielen mathematischen und ingenieurwissenschaftlichen Disziplinen, oft sind ähnliche Konzepte unter verschiedenen Namen bekannt und werden auf unterschiedliche Weise ausgedrückt (z. B. Adjazenzmatrizen und Adjazenzlisten). Da diese Ideen ziemlich esoterisch sind, werden Entscheidungen darüber getroffen, wie allgemein diese Konzepte für eine bestimmte Umgebung definiert werden.

Dieser Artikel setzt außer einer kleinen Einführung in die Mengenlehre kein Vorwissen voraus.

Die Implementierungen in diesem Beitrag stellen die Probleme als gerichtete Graphen (digraph) dar.

DiGraphen

Ein Digraph hat zwei Attribute, setOfNodes und setOfArcs . Diese beiden Attribute sind Mengen (ungeordnete Sammlungen). In den Codeblöcken in diesem Beitrag verwende ich eigentlich Pythons Frozenset, aber dieses Detail ist nicht besonders wichtig.

 DiGraph = namedtuple('DiGraph', ['setOfNodes','setOfArcs'])

(Hinweis: Dieser und der gesamte andere Code in diesem Artikel sind in Python 3.6 geschrieben.)

Knoten

Ein Knoten n besteht aus zwei Attributen:

• n.uid : Ein eindeutiger Bezeichner.

  Dies bedeutet, dass für zwei beliebige Knoten x und y ,

 x.uid != y.uid

• n.datum : Dies repräsentiert ein beliebiges Datenobjekt.

 Node = namedtuple('Node', ['uid','datum'])

Bögen

Ein Bogen a setzt sich aus drei Attributen zusammen:

• a.fromNode : Dies ist ein Knoten , wie oben definiert.

• a.toNode : Dies ist ein Knoten , wie oben definiert.

• a.datum : Dies repräsentiert ein beliebiges Datenobjekt.

 Arc = namedtuple('Arc', ['fromNode','toNode','datum'])

Die Menge der Bögen im Digraph stellt eine binäre Beziehung auf den Knoten im Digraph dar. Die Existenz von Bogen a impliziert, dass eine Beziehung zwischen a.fromNode und a.toNode besteht.

In einem gerichteten Graphen (im Gegensatz zu einem ungerichteten Graphen) impliziert die Existenz einer Beziehung zwischen a.fromNode und a.toNode nicht , dass eine ähnliche Beziehung zwischen a.toNode und a.fromNode existiert.

Dies liegt daran, dass in einem ungerichteten Graphen die ausgedrückte Beziehung nicht unbedingt symmetrisch ist.

DiGraphen

Knoten und Bögen können verwendet werden, um einen Digraphen zu definieren, aber der Einfachheit halber wird ein Digraph in den folgenden Algorithmen als Wörterbuch dargestellt.

Hier ist eine Methode, die die obige Diagrammdarstellung in eine Wörterbuchdarstellung ähnlich dieser umwandeln kann:

 def digraph_to_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) G_as_dict[a.fromNode] = (G_as_dict[a.fromNode].union(frozenset([a]))) if (a.fromNode in G_as_dict) else frozenset([a]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = frozenset([]) return G_as_dict

Und hier ist eine andere, die es in ein Wörterbuch von Wörterbüchern umwandelt, eine weitere Operation, die nützlich sein wird:

 def digraph_to_double_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.fromNode not in G_as_dict): G_as_dict[a.fromNode] = dict({a.toNode : frozenset([a])}) else: if(a.toNode not in G_as_dict[a.fromNode]): G_as_dict[a.fromNode][a.toNode] = frozenset([a]) else: G_as_dict[a.fromNode][a.toNode] = G_as_dict[a.fromNode][a.toNode].union(frozenset([a])) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = dict({}) return G_as_dict

Wenn der Artikel über einen Digraphen spricht, wie er durch ein Wörterbuch dargestellt wird, wird G_as_dict erwähnt, um darauf zu verweisen.

Manchmal ist es hilfreich, einen Knoten von einem Digraphen G über seine uid (eindeutige Kennung) nach oben zu holen:

 def find_node_by_uid(find_uid, G): nodes = {n for n in G.setOfNodes if n.uid == find_uid} if(len(nodes) != 1): err_msg = 'Node with uid {find_uid!s} is not unique.'.format(**locals()) raise KeyError(err_msg) return nodes.pop()

Beim Definieren von Graphen werden manchmal die Begriffe Knoten und Vertex verwendet, um sich auf dasselbe Konzept zu beziehen; gleiches gilt für die Begriffe Bogen und Kante.

Zwei beliebte Diagrammdarstellungen in Python sind diese, die Wörterbücher verwendet, und eine andere, die Objekte zur Darstellung von Diagrammen verwendet. Die Darstellung in diesem Beitrag liegt irgendwo zwischen diesen beiden häufig verwendeten Darstellungen.

Dies ist meine Digraphdarstellung . Es gibt viele davon, aber dieses hier ist meins.

Spaziergänge und Pfade

Sei S_Arcs eine endliche Folge (geordnete Sammlung) von Bögen in einem Digraphen G , so dass, wenn a irgendein Bogen in S_Arcs außer dem letzten ist und b in der Folge auf a folgt, es einen Knoten n = a.fromNode in geben muss G.setOfNodes so, dass a.toNode = b.fromNode .

Beginnend mit dem ersten Bogen in S_Arcs und fortfahrend bis zum letzten Bogen in S_Arcs , sammle (in der angetroffenen Reihenfolge) alle Knoten n , wie oben definiert, zwischen jeweils zwei aufeinanderfolgenden Bögen in S_Arcs . Beschriften Sie die geordnete Sammlung von Knoten , die während dieser Operation gesammelt wurden, mit S_{Nodes} .

 def path_arcs_to_nodes(s_arcs): s_nodes = list([]) arc_it = iter(s_arcs) step_count = 0 last = None try: at_end = False last = a1 = next(arc_it) while (not at_end): s_nodes += [a1.fromNode] last = a2 = next(arc_it) step_count += 1 if(a1.toNode != a2.fromNode): err_msg = "Error at index {step_count!s} of Arc sequence.".format(**locals()) raise ValueError(err_msg) a1 = a2 except StopIteration as e: at_end = True if(last is not None): s_nodes += [last.toNode] return s_nodes

• Wenn irgendein Knoten mehr als einmal in der Sequenz S_Nodes , dann nenne S_Arcs einen Walk on Digraph G .

• Rufen Sie andernfalls S_Arcs als Pfad von list(S_Nodes)[0] zu list(S_Nodes)[-1] auf Digraph G auf.

Quellknoten

Rufen Sie node s einen Quellknoten in Digraph G auf, wenn s in G.setOfNodes ist und G.setOfArcs keinen Bogen a enthält, so dass a.toNode = s .

 def source_nodes(G): to_nodes = frozenset({a.toNode for a in G.setOfArcs}) sources = G.setOfNodes.difference(to_nodes) return sources

Endknoten

Nenne Knoten t einen Endknoten in Digraph G , wenn t in G.setOfNodes ist und G.setOfArcs keinen Bogen a enthält, so dass a.fromNode = t .

 def terminal_nodes(G): from_nodes = frozenset({a.fromNode for a in G.setOfArcs}) terminals = G.setOfNodes.difference(from_nodes) return terminals

Schnitte und st Schnitte

Ein Schnitt cut eines verbundenen Digraphen G ist eine Teilmenge von Bögen aus G.setOfArcs , die die Menge von Knoten G.setOfNodes in G partitioniert. G ist verbunden, wenn jeder Knoten n in G.setOfNodes und mindestens einen Bogen a in G.setOfArcs , so dass entweder n = a.fromNode oder n = a.toNode , aber a.fromNode != a.toNode .

 Cut = namedtuple('Cut', ['setOfCutArcs'])

Die obige Definition bezieht sich auf eine Teilmenge von Bögen , kann aber auch eine Partition der Knoten von G.setOfNodes .

Für die Funktionen predecessors_of und successors_of ist n ein Knoten in der Menge G.setOfNodes von Digraph G und cut ist ein Schnitt von G :

 def cut_predecessors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) predecessors = frozenset({}) previous_count = len(predecessors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.fromNode for a in allowed_arcs if (a.toNode in reach_fringe)}) reach_fringe = reachable_from predecessors = predecessors.union(reach_fringe) current_count = len(predecessors) keep_going = current_count - previous_count > 0 previous_count = current_count return predecessors def cut_successors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) successors = frozenset({}) previous_count = len(successors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.toNode for a in allowed_arcs if (a.fromNode in reach_fringe)}) reach_fringe = reachable_from successors = successors.union(reach_fringe) current_count = len(successors) keep_going = current_count - previous_count > 0 previous_count = current_count return successors

Sei cut ein Schnitt des Digraphen G .

 def get_first_part(cut, G): firstPartFringe = frozenset({a.fromNode for a in cut.setOfCutArcs}) firstPart = firstPartFringe for n in firstPart: preds = cut_predecessors_of(n,cut,G) firstPart = firstPart.union(preds) return firstPart def get_second_part(cut, G): secondPartFringe = frozenset({a.toNode for a in cut.setOfCutArcs}) secondPart = secondPartFringe for n in secondPart: succs= cut_successors_of(n,cut,G) secondPart = secondPart.union(succs) return secondPart

cut ist ein Schnitt des Digraphen G , wenn: (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) and (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut wird als xy-Schnitt bezeichnet, wenn (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . Wenn der Knoten x in einem xy-Schnitt cut Quellknoten und der Knoten y in einem xy-Schnitt ein Endknoten ist, dann wird dieser Schnitt ein st-Schnitt genannt.

 STCut = namedtuple('STCut', ['s','t','cut'])

Flussnetzwerke

Sie können einen Digraphen G verwenden, um ein Flussnetzwerk darzustellen.

Weisen Sie jedem Knoten n , wobei n in G.setOfNodes enthalten ist, ein n.datum , das ein FlowNodeDatum ist:

 FlowNodeDatum = namedtuple('FlowNodeDatum', ['flowIn','flowOut'])

Weisen Sie jedem Bogen a zu, wobei sich a in G.setOfArcs und a.datum befindet, das ein FlowArcDatum ist.

 FlowArcDatum = namedtuple('FlowArcDatum', ['capacity','flow'])

flowNodeDatum.flowIn und flowNodeDatum.flowOut sind positive reelle Zahlen.

flowArcDatum.capacity und flowArcDatum.flow sind ebenfalls positive reelle Zahlen.

Für jeden Knoten node n in G.setOfNodes :

 n.datum.flowIn = sum({a.datum.flow for a in G.Arcs if a.toNode == n}) n.datum.flowOut = sum({a.datum.flow for a in G.Arcs if a.fromNode == n})

Digraph G repräsentiert nun ein Flussnetzwerk .

Der Fluss von G bezieht sich auf den a.flow für alle Bögen a in G .

Machbare Flüsse

Der Digraph G stelle ein Flussnetzwerk dar .

Das durch G dargestellte Flussnetzwerk hat zulässige Flüsse , wenn:

1. Für jeden Knoten n in G.setOfNodes außer Quellknoten und Endknoten : n.datum.flowIn = n.datum.flowOut .

2. Für jeden Bogen a in G.setOfNodes : a.datum.capacity <= a.datum.flow .

Bedingung 1 wird Erhaltungsbedingung genannt.

Bedingung 2 wird als Kapazitätsbeschränkung bezeichnet.

Schnittkapazität

Die Schnittkapazität eines st-Schnitts stCut mit Quellknoten s und Endknoten t eines durch einen Digraphen G repräsentierten Flussnetzes ist:

 def cut_capacity(stCut, G): part_1 = get_first_part(stCut.cut,G) part_2 = get_second_part(stCut.cut,G) s_part = part_1 if stCut.s in part_1 else part_2 t_part = part_1 if stCut.t in part_1 else part_2 cut_capacity = sum({a.datum.capacity for a in stCut.cut.setOfCutArcs if ( (a.fromNode in s_part) and (a.toNode in t_part) )}) return cut_capacity

Kürzung der Mindestkapazität

Sei stCut = stCut(s,t,cut) ein st-Schnitt eines durch einen Digraphen G repräsentierten Flussnetzwerks .

stCut ist der minimale Kapazitätsschnitt des durch G dargestellten Flussnetzwerks , wenn es keinen anderen st cut stCutCompetitor in diesem Flussnetzwerk gibt, so dass:

 cut_capacity(stCut, G) < cut_capacity(stCutCompetitor, G)

Abstreifen der Strömungen

Ich möchte mich auf den Digraphen beziehen, der das Ergebnis wäre, wenn man einen Digraphen G nimmt und alle Flussdaten von allen Knoten in G.setOfNodes und auch allen Bögen in G.setOfArcs .

 def strip_flows(G): new_nodes= frozenset( (Node(n.uid, FlowNodeDatum(0.0,0.0)) for n in G.setOfNodes) ) new_arcs = frozenset([]) for a in G.setOfArcs: new_fromNode = Node(a.fromNode.uid, FlowNodeDatum(0.0,0.0)) new_toNode = Node(a.toNode.uid, FlowNodeDatum(0.0,0.0)) new_arc = Arc(new_fromNode, new_toNode, FlowArcDatum(a.datum.capacity, 0.0)) new_arcs = new_arcs.union(frozenset([new_arc])) return DiGraph(new_nodes, new_arcs)

Maximum-Flow-Problem

Ein als Digraph G dargestelltes Flussnetzwerk , ein Quellknoten s in G.setOfNodes und ein Endknoten t in G.setOfNodes , G kann ein Maximum-Flow-Problem darstellen, wenn:

 (len(list(source_nodes(G))) == 1) and (next(iter(source_nodes(G))) == s) and (len(list(terminal_nodes(G))) == 1) and (next(iter(terminal_nodes(G))) == t)

Beschriften Sie diese Darstellung:

 MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid'])

Wobei sourceNodeUid = s.uid , terminalNodeUid = t.uid und maxFlowProblemStateUid eine Kennung für die Probleminstanz ist.

Maximum-Flow-Lösung

Sei maxFlowProblem ein Maximum-Flow-Problem . Die Lösung von maxFlowProblem kann durch ein als Digraph H dargestelltes Flussnetzwerk dargestellt werden.

Digraph H ist eine zulässige Lösung für das Problem des maximalen Flusses bei der Eingabe von python maxFlowProblem , wenn:

1. strip_flows(maxFlowProblem.G) == strip_flows(H) .

2. H ist ein Flussnetzwerk und hat zulässige Flüsse .

Wenn zusätzlich zu 1 und 2:

1. Es kann kein anderes Flussnetzwerk geben, das durch Digraph K dargestellt wird, so dass strip_flows(G) == strip_flows(K) und find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Dann ist H auch eine optimale Lösung für maxFlowProblem .

Mit anderen Worten kann eine zulässige Lösung mit maximalem Durchfluss durch einen Digraphen dargestellt werden, der:

1. Ist identisch mit Digraph G des entsprechenden Maximum-Flow-Problems mit der Ausnahme, dass n.datum.flowIn , n.datum.flowOut und a.datum.flow aller Knoten und Bögen unterschiedlich sein können.

2. Stellt ein Flussnetzwerk dar , das zulässige Flüsse aufweist .

Und es kann eine optimale Lösung für maximalen Durchfluss darstellen, wenn zusätzlich:

1. Der flowIn für den Knoten , der dem Endknoten im Maximum-Flow-Problem entspricht, ist so groß wie möglich (wenn die Bedingungen 1 und 2 noch erfüllt sind).

Wenn Digraph H eine zulässige Lösung mit maximalem Fluss darstellt: find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn folgt dies aus dem Max-Flow-Min-Cut-Theorem (unten diskutiert). Da angenommen wird, dass H zulässige Flüsse hat, bedeutet dies informell, dass der Fluss weder 'erzeugt' (außer am Quellknoten s ) noch 'zerstört' (außer am Endknoten t ) werden kann, während er einen (anderen) Knoten kreuzt ( Erhaltungsbedingungen ).

Da ein Maximum-Flow-Problem nur einen einzigen Quellknoten s und einen einzigen Endknoten t enthält, müssen alle bei s 'erzeugten' Flüsse bei t 'zerstört' werden, oder das Flussnetzwerk hat keine zulässigen Flüsse (die Erhaltungsbedingung wäre verletzt worden). ).

Der Digraph H stelle eine zulässige Lösung mit maximalem Fluss dar ; der obige Wert wird als st Flow Value von H bezeichnet.

Lassen:

 mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid)

Dies bedeutet, dass mfps ein Nachfolgezustand von maxFlowProblem ist, was nur bedeutet, dass mfps genau wie maxFlowProblem ist, mit der Ausnahme, dass die Werte von a.flow für Bögen a in maxFlowProblem.setOfArcs unterschiedlich sein können von a.flow für Bögen a in mfps.setOfArcs .

 def get_mfps_flow(mfps): flow_from_s = find_node_by_uid(mfps.sourceNodeUid,mfps.G).datum.flowOut flow_to_t = find_node_by_uid(mfps.terminalNodeUid,mfps.G).datum.flowIn if( (flow_to_t - flow_from_s) > 0): raise Exception('Infeasible st flow') return flow_to_t

Hier ist eine Visualisierung eines mfps zusammen mit dem zugehörigen maxFlowProb . Jeder Bogen a im Bild hat ein Label, diese Labels sind a.datum.flowFrom / a.datum.flowTo , jeder Knoten n im Bild hat ein Label, und diese Labels sind n.uid {n.datum.flowIn / a.datum.flowOut} .

st Schnittfluss

Lassen Sie mfps einen MaxFlowProblemState und lassen Sie stCut einen Schnitt von mfps.G . Der Schnittfluss von stCut ist definiert:

 def get_stcut_flow(stCut,mfps): s = find_node_by_uid(mfps.sourceNodeUid, mfps.G) t = find_node_by_uid(mfps.terminalNodeUid, mfps.G) part_1 = get_first_part(stCut.cut,mfps.G) part_2 = get_second_part(stCut.cut,mfps.G) s_part = part_1 if s in part_1 else part_2 t_part = part_1 if t in part_1 else part_2 s_t_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in s_part) ) t_s_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in t_part) ) cut_flow = s_t_sum - t_s_sum return cut_flow

st cut flow ist die Summe der Flüsse von der Partition, die den Quellenknoten enthält, zu der Partition, die den Endknoten enthält, abzüglich der Summe der Flüsse von der Partition, die den Endknoten enthält, zu der Partition, die den Quellenknoten enthält.

Maximaler Durchfluss, minimaler Schnitt

Lassen Sie maxFlowProblem ein Maximum-Flow-Problem darstellen und lassen Sie die Lösung von maxFlowProblem durch ein als Digraph H dargestelltes Flow-Netzwerk darstellen.

Sei minStCut der minimale Kapazitätsschnitt des durch maxFlowProblem.G dargestellten maxFlowProblem.G .

Da der Fluss beim Maximum-Flow-Problem nur von einem einzigen Quellknoten ausgeht und an einem einzigen Endknoten endet, wissen wir aufgrund der Kapazitätsbeschränkungen und der Erhaltungsbeschränkungen , dass der gesamte Fluss, der in maxFlowProblem.terminalNodeUid eintritt, jeden st-Schnitt kreuzen muss , insbesondere muss es minStCut kreuzen. Das heisst:

 get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G)

Lösung des Maximum-Flow-Problems

Die Grundidee zum Lösen eines Maximum-Flow-Problems maxFlowProblem besteht darin, mit einer Maximum-Flow-Lösung zu beginnen, die durch den Digraphen H repräsentiert wird. Ein solcher Ausgangspunkt kann H = strip_flows(maxFlowProblem.G) . Die Aufgabe besteht dann darin, H zu verwenden und durch eine gierige Modifikation der a.datum.flow Werte einiger Bögen a in H.setOfArcs eine andere maximale Strömungslösung zu erzeugen, die durch den Digraphen K dargestellt wird, so dass K immer noch kein Strömungsnetzwerk mit zulässigen Strömungen darstellen kann und get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Solange dieser Prozess andauert, ist die Qualität ( get_flow_value(K, maxFlowProblem) ) der zuletzt gefundenen Maximalflusslösung ( K ) besser als jede andere gefundene Maximalflusslösung . Wenn der Prozess einen Punkt erreicht, an dem er weiß, dass keine weitere Verbesserung möglich ist, kann der Prozess enden und die optimale Maximalflusslösung zurückgeben.

Die obige Beschreibung ist allgemein und überspringt viele Beweise, wie z. B. ob ein solcher Prozess möglich ist oder wie lange er dauern kann. Ich werde ein paar weitere Details und den Algorithmus geben.

Das Max-Flow-Min-Cut-Theorem

Aus dem Buch Flows in Networks von Ford und Fulkerson lautet die Aussage des Max-Flow-Min-Cut-Theorems (Theorem 5.1):

Für jedes Netzwerk ist der maximale Durchflusswert von s nach t gleich der minimalen Schnittkapazität aller Schnitte, die s und t trennen.

Unter Verwendung der Definitionen in diesem Beitrag bedeutet dies:

Die Lösung eines maxFlowProblem , dargestellt durch ein als Digraph H dargestelltes Strömungsnetz, ist optimal, wenn:

 get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G)

Ich mag diesen Beweis des Theorems und Wikipedia hat einen anderen.

Das Max-Flow-Min-Cut-Theorem wird verwendet, um die Korrektheit und Vollständigkeit der Ford-Fulkerson-Methode zu beweisen.

Ich werde auch einen Beweis des Theorems im Abschnitt nach dem Erweitern von Pfaden geben.

Die Ford-Fulkerson-Methode und der Edmonds-Karp-Algorithmus

CLRS definiert die Ford-Fulkerson-Methode wie folgt (Abschnitt 26.2):

 FORD-FULKERSON-METHOD(G, s, t): initialize flow f to 0 while there exists an augmenting path p in the residual graph G_f augment flow f along

Residualdiagramm

Der als Digraph G dargestellte Residuengraph eines Flussnetzes kann als Digraph G_f dargestellt werden:

 ResidualDatum = namedtuple('ResidualDatum', ['residualCapacity','action']) def agg_n_to_u_cap(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.capacity for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def agg_n_to_u_flow(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.flow for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def get_residual_graph_of(G): G_as_dict = digraph_to_dict(G) residual_nodes = G.setOfNodes residual_arcs = frozenset([]) for n in G_as_dict: arcs_from = G_as_dict[n] nodes_to = frozenset([find_node_by_uid(a.toNode.uid,G) for a in arcs_from]) for u in nodes_to: n_to_u_cap_sum = agg_n_to_u_cap(n,u,G_as_dict) n_to_u_flow_sum = agg_n_to_u_flow(n,u,G_as_dict) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(n,u,datum=ResidualDatum(flow, 'push'))]) ) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(u,n,datum=ResidualDatum(flow, 'pull'))]) ) return DiGraph(residual_nodes, residual_arcs)

• agg_n_to_u_cap(n,u,G_as_dict) gibt die Summe von a.datum.capacity für alle Bögen in der Teilmenge von G.setOfArcs wobei Bogen a in der Teilmenge ist, wenn a.fromNode = n und a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) gibt die Summe von a.datum.flow für alle Bögen in der Teilmenge von G.setOfArcs wobei Bogen a in der Teilmenge ist, wenn a.fromNode = n und a.toNode = u .

Kurz gesagt stellt der Restgraph G_f bestimmte Aktionen dar, die auf dem Digraphen G durchgeführt werden können.

Jedes Knotenpaar n,u in G.setOfNodes des durch den Digraphen G repräsentierten Flussnetzwerks kann 0, 1 oder 2 Bögen im Restgraphen G_f von G erzeugen.

1. Das Paar n,u erzeugt keine Bögen in G_f , wenn es keinen Bogen a in G.setOfArcs , so dass a.fromNode = n und a.toNode = u .

2. Das Paar n,u erzeugt den Bogen a in G_f.setOfArcs , wobei a einen Bogen darstellt, der als Push-Flow-Bogen von n nach u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) bezeichnet wird, wenn n_to_u_cap_sum > n_to_u_flow_sum .

3. Das Paar n,u erzeugt den Bogen a in G_f.setOfArcs , wobei a einen Bogen darstellt, der als Pull-Flow-Bogen von n nach u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) bezeichnet wird, wenn n_to_u_flow_sum > 0.0 .

• Jeder Push-Flow-Bogen in G_f.setOfArcs stellt die Aktion des Addierens von insgesamt x <= n_to_u_cap_sum - n_to_u_flow_sum Fluss zu Bögen in der Teilmenge von G.setOfArcs wobei Bogen a in der Teilmenge ist, wenn a.fromNode = n und a.toNode = u .

• Jeder Pull-Fluss-Bogen in G_f.setOfArcs stellt die Aktion des Subtrahierens von insgesamt x <= n_to_u_flow_sum Fluss zu Bögen in der Teilmenge von G.setOfArcs wobei Bogen a in der Teilmenge ist, wenn a.fromNode = n und a.toNode = u .

Das Durchführen einer einzelnen Push- oder Pull -Aktion von G_f an den anwendbaren Bögen in G könnte ein Flussnetzwerk ohne zulässige Flüsse erzeugen, weil die Kapazitätsbeschränkungen oder die Erhaltungsbeschränkungen in dem generierten Flussnetzwerk verletzt werden könnten.

Hier ist eine Visualisierung des Residualdiagramms der vorherigen Beispielvisualisierung einer Maximalflusslösung , in der Visualisierung repräsentiert jeder Bogen a a.residualCapacity .

Augmentierender Pfad

Sei maxFlowProblem ein Max-Flow-Problem und sei G_f = get_residual_graph_of(G) der Restgraph von maxFlowProblem.G .

Ein augmentierender Pfad augmentingPath für maxFlowProblem ist ein beliebiger Pfad von find_node_by_uid(maxFlowProblem.sourceNode,G_f) bis find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

Es stellt sich heraus, dass ein augmentierender Pfad augmentingPath auf eine Max-Flow-Lösung angewendet werden kann, die durch Digraph H dargestellt wird, wodurch eine andere Max-Flow-Lösung erzeugt wird, die durch Digraph K dargestellt wird, wobei get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) ist, wenn H nicht optimal ist.

Hier ist wie:

 def augment(augmentingPath, H): augmentingPath = list(augmentingPath) H_as_dict = digraph_to_dict(H) new_nodes = frozenset({}) new_arcs = frozenset({}) visited_nodes = frozenset({}) visited_arcs = frozenset({}) bottleneck_residualCapacity = min( augmentingPath, key=lambda a: a.datum.residualCapacity ).datum.residualCapacity for x in augmentingPath: from_node_uid = x.fromNode.uid if x.datum.action == 'push' else x.toNode.uid to_node_uid = x.toNode.uid if x.datum.action == 'push' else x.fromNode.uid from_node = find_node_by_uid( from_node_uid, H ) to_node = find_node_by_uid( to_node_uid, H ) load = bottleneck_residualCapacity if x.datum.action == 'push' else -bottleneck_residualCapacity for a in H_as_dict[from_node]: if(a.toNode == to_node): test_sum = a.datum.flow + load new_flow = a.datum.flow new_from_node_flow_out = a.fromNode.datum.flowOut new_to_node_flow_in = a.toNode.datum.flowIn new_from_look = {n for n in new_nodes if (n.uid == a.fromNode.uid)} new_to_look = {n for n in new_nodes if (n.uid == a.toNode.uid) } prev_from_node = new_from_look.pop() if (len(new_from_look)>0) else a.fromNode prev_to_node = new_to_look.pop() if (len(new_to_look)>0) else a.toNode new_nodes = new_nodes.difference(frozenset({prev_from_node})) new_nodes = new_nodes.difference(frozenset({prev_to_node})) if(test_sum > a.datum.capacity): new_flow = a.datum.capacity new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + a.datum.capacity new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + a.datum.capacity load = test_sum - a.datum.capacity elif(test_sum < 0.0): new_flow = 0.0 new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow load = test_sum else: new_flow = test_sum new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + new_flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + new_flow load = 0.0 new_from_node_flow_out = round(new_from_node_flow_out, TOL) new_to_node_flow_in = round(new_to_node_flow_in, TOL) new_flow = round(new_flow, TOL) new_from_node = Node(prev_from_node.uid, FlowNodeDatum(prev_from_node.datum.flowIn, new_from_node_flow_out)) new_to_node = Node(prev_to_node.uid, FlowNodeDatum(new_to_node_flow_in, prev_to_node.datum.flowOut)) new_arc = Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, new_flow)) visited_nodes = visited_nodes.union(frozenset({a.fromNode,a.toNode})) visited_arcs = visited_arcs.union(frozenset({a})) new_nodes = new_nodes.union(frozenset({new_from_node, new_to_node})) new_arcs = new_arcs.union(frozenset({new_arc})) not_visited_nodes = H.setOfNodes.difference(visited_nodes) not_visited_arcs = H.setOfArcs.difference(visited_arcs) full_new_nodes = new_nodes.union(not_visited_nodes) full_new_arcs = new_arcs.union(not_visited_arcs) G = DiGraph(full_new_nodes, full_new_arcs) full_new_arcs_update = frozenset([]) for a in full_new_arcs: new_from_node = a.fromNode new_to_node = a.toNode new_from_node = find_node_by_uid( a.fromNode.uid, G ) new_to_node = find_node_by_uid( a.toNode.uid, G ) full_new_arcs_update = full_new_arcs_update.union( {Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, a.datum.flow))} ) G = DiGraph(full_new_nodes, full_new_arcs_update) return G

Oben ist TOL ein gewisser Toleranzwert zum Runden der Flusswerte im Netzwerk. Dies dient dazu, eine kaskadierende Ungenauigkeit von Gleitkommaberechnungen zu vermeiden. Also habe ich zum Beispiel TOL = 10 verwendet, um auf 10 signifikante Stellen zu runden.

Sei K = augment(augmentingPath, H) , dann repräsentiert K eine zulässige maximale Flusslösung für maxFlowProblem . Damit die Aussage wahr ist, muss das durch K dargestellte Flussnetzwerk zulässige Flüsse haben (die Kapazitätsbeschränkung oder die Erhaltungsbeschränkung nicht verletzen .

Hier ist der Grund: In der obigen Methode ist jeder Knoten , der dem neuen Flussnetzwerk hinzugefügt wird, das durch Digraph K dargestellt wird, entweder eine exakte Kopie eines Knotens aus Digraph H oder ein Knoten n , dem die gleiche Nummer zu seinem n.datum.flowIn as hinzugefügt wurde sein n.datum.flowOut . Das bedeutet, dass die Erhaltungsbedingung in K erfüllt ist, solange sie in H erfüllt war. Die Erhaltungsbedingung ist erfüllt, weil wir explizit prüfen, ob jeder neue Bogen a im Netzwerk a.datum.flow <= a.datum.capacity hat; solange also die Bögen aus der Menge H.setOfArcs , die unverändert in K.setOfArcs kopiert wurden, die Kapazitätsbeschränkung nicht verletzen, verletzt K die Kapazitätsbeschränkung nicht.

Es ist auch wahr, dass get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) ist, wenn H nicht optimal ist.

Hier ist der Grund: Damit ein augmentierender Pfad augmentingPath in der Digraph -Darstellung des Restgraphen G_f eines Max-Flow-Problems maxFlowProblem , muss der letzte Bogen a auf augmentingPath ein 'Push'- Bogen sein und a.toNode == maxFlowProblem.terminalNode . Ein augmentierender Pfad ist als einer definiert, der am Endknoten des Max-Flow-Problems endet, für das er ein augmentierender Pfad ist. Aus der Definition des Restgraphen geht hervor, dass der letzte Bogen in einem Augmentationspfad auf diesem Restgraphen ein „Push“ -Bogen sein muss, weil jeder „Pull“ -Bogen b im Augmentationspfad b.toNode == maxFlowProblem.terminalNode und b.fromNode != maxFlowProblem.terminalNode aus der Definition von path . Außerdem geht aus der Definition von path hervor, dass der Endknoten nur einmal durch die augment -Methode modifiziert wird. Somit modifiziert augment maxFlowProblem.terminalNode.flowIn genau einmal und erhöht den Wert von maxFlowProblem.terminalNode.flowIn weil der letzte Bogen im augmentingPath der Bogen sein muss, der die Modifikation in maxFlowProblem.terminalNode.flowIn während augment verursacht. Aus der Definition von augment , wie es für 'push' arcs gilt, kann maxFlowProblem.terminalNode.flowIn nur erhöht, nicht verringert werden.

Einige Beweise von Sedgewick und Wayne

Das Buch Algorithms, vierte Auflage von Robert Sedgewich und Kevin Wayne enthält einige wunderbare und kurze Beweise (Seiten 892-894), die nützlich sein werden. Ich werde sie hier neu erstellen, obwohl ich eine Sprache verwenden werde, die zu früheren Definitionen passt. Meine Etiketten für die Proofs sind die gleichen wie im Sedgewick-Buch.

Satz E: Für jeden Digraphen H , der eine zulässige maxFlowProblem für ein Maximalflussproblem maxFlowProblem darstellt, gilt für jeden stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Beweis: Sei stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Satz E gilt für stCut direkt aus der Definition von st flow value . Angenommen, wir möchten einen Knoten n von der s-Partition ( get_first_part(stCut.cut, G) ) in die t-Partition (get_second_part(stCut.cut, G)) , dazu müssen wir stCut.cut ändern stCut.cut , was stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) und Proposition E ungültig machen könnte. Lassen Sie uns jedoch sehen, wie sich der Wert von stcut_flow ändert, wenn wir diese Änderung vornehmen. Knoten n befindet sich im Gleichgewicht, was bedeutet, dass die Summe des Flusses in den Knoten n gleich der Summe des Flusses aus ihm heraus ist (dies ist notwendig, damit H eine zulässige Lösung darstellt). Beachten Sie, dass der gesamte Fluss, der Teil des stcut_flow ist, der in den Knoten n eintritt, von der s-Partition in ihn eintritt (der Fluss, der entweder direkt oder indirekt in den Knoten n von der t-Partition eintritt, wäre nicht im stcut_flow Wert gezählt worden, da er in die falsche Richtung geht nach Definition). Außerdem wird der gesamte Fluss, der n verlässt, schließlich (direkt oder indirekt) in den Endknoten fließen (früher bewiesen). Wenn wir den Knoten n in die t-Partition verschieben, muss der gesamte Fluss, der von der s-Partition in n eintritt, zum neuen stcut_flow Wert hinzugefügt werden; jedoch muss der gesamte Fluss, der n verlässt, von dem neuen stcut_flow Wert subtrahiert werden; der Teil des Flusses, der direkt in die t-Partition geht, wird subtrahiert, weil dieser Fluss nun intern in der neuen t-Partition ist und nicht als stcut_flow gezählt wird. Der Teil des Flusses von n , der in Knoten in der s-Partition geht, muss auch von stcut_flow subtrahiert werden: Nachdem n in die t-Partition verschoben wurde, werden diese Flüsse von der t-Partition in die s-Partition und so geleitet muss nicht im stcut_flow werden, da diese Flüsse vom Zufluss in die s-Partition entfernt werden und um die Summe dieser Flüsse und den Abfluss von der s-Partition in die t-Partition (woher alle fließen) reduziert werden müssen st muss am Ende) um den gleichen Betrag gekürzt werden. Da der Knoten n vor dem Prozess im Gleichgewicht war, wird die Aktualisierung den gleichen Wert zu dem neuen stcut_flow Wert hinzugefügt haben, den er subtrahiert hat, wodurch Aussage E nach der Aktualisierung wahr bleibt. Die Gültigkeit von Satz E folgt dann aus Induktion über die Größe der t-Partition.

Hier sind einige Beispiele für Flussnetzwerke , um die weniger offensichtlichen Fälle zu veranschaulichen, in denen Aussage E gilt; im bild zeigen die roten bereiche die s-partition, die blauen bereiche die t-partition und die grünen bögen einen st-schnitt an . Im zweiten Bild nimmt der Fluss zwischen Knoten A und Knoten B zu, während sich der Fluss in den Endknoten t nicht ändert:

Folgerung: Kein st-Schnitt-Durchflusswert kann die Kapazität eines beliebigen st-Schnitts überschreiten.

Proposition F. (max flow, min cut theorem): Sei f ein st flow . Die folgenden 3 Bedingungen sind gleichwertig:

1. Es gibt einen st-Schnitt, dessen Kapazität gleich dem Wert des Flusses f ist.

2. f ist ein maximaler Fluss .

3. Es gibt keinen augmentierenden Pfad bezüglich f .

Bedingung 1 impliziert Bedingung 2 durch die Folgerung. Bedingung 2 impliziert Bedingung 3, da die Existenz eines augmentierenden Pfades die Existenz eines Flusses mit größeren Werten impliziert, was der Maximalität von f widerspricht. Bedingung 3 impliziert Bedingung 1: Sei C_s die Menge aller Knoten , die von s aus mit einem augmentierenden Pfad im Restgraphen erreicht werden können. Seien C_t die verbleibenden Bögen , dann muss t in C_t (nach unserer Annahme). Die von C_s nach C_t kreuzenden Bögen bilden dann einen st-Schnitt , der nur Bögen a enthält, wobei entweder a.datum.capacity = a.datum.flow oder a.datum.flow = 0.0 . Wäre dies anders, dann lägen die durch einen Bogen mit verbleibender Restkapazität mit C_s verbundenen Knoten in der Menge C_s , da es dann einen augmentierenden Pfad von s zu einem solchen Knoten gäbe. Der Fluss über den st-Schnitt ist gleich der Kapazität des st-Schnitts (da Bögen von C_s nach C_t einen Fluss gleich der Kapazität haben) und auch gleich dem Wert des st-Flusses (nach Satz E ).

Diese Aussage des Max Flow, Min Cut-Theorems impliziert die frühere Aussage von Flows in Networks.

Korollar (Integritätseigenschaft): Wenn Kapazitäten ganze Zahlen sind, gibt es einen ganzzahligen maximalen Fluss, und der Ford-Fulkerson-Algorithmus findet ihn.

Beweis: Jeder augmentierende Pfad erhöht den Fluss um eine positive ganze Zahl, das Minimum der ungenutzten Kapazitäten in den „Push“ -Bögen und der Flüsse in den „Pull“ -Bögen , die alle immer positive ganze Zahlen sind.

Dies rechtfertigt die Ford-Fulkerson-Methodenbeschreibung von CLRS . Die Methode besteht darin, weiter augmentierende Pfade zu finden und augmentierend auf die neueste augment maxFlowSolution , um bessere Lösungen zu finden, bis kein augmentierender Pfad mehr vorhanden ist, was bedeutet, dass die neueste maximale Durchflusslösung optimal ist.

Von Ford-Fulkerson bis Edmonds-Karp

Die verbleibenden Fragen zur Lösung von Problemen mit maximalem Durchfluss sind:

1. Wie sollten augmentierende Pfade konstruiert werden?

2. Wird die Methode terminieren, wenn wir reelle Zahlen und keine ganzen Zahlen verwenden?

3. Wie lange dauert die Kündigung (wenn ja)?

Der Edmonds-Karp-Algorithmus spezifiziert, dass jeder augmentierende Pfad durch eine Breitensuche (BFS) des Restgraphen konstruiert wird; es stellt sich heraus, dass diese Entscheidung von Punkt 1 oben auch den Algorithmus zur Beendigung zwingen wird (Punkt 2) und es ermöglicht, die asymptotische Zeit- und Raumkomplexität zu bestimmen.

Hier ist zunächst eine BFS -Implementierung:

 def bfs(sourceNode, terminalNode, G_f): G_f_as_dict = digraph_to_dict(G_f) parent_arcs = dict([]) visited = frozenset([]) deq = deque([sourceNode]) while len(deq) > 0: curr = deq.popleft() if curr == terminalNode: break for a in G_f_as_dict.get(curr): if (a.toNode not in visited): visited = visited.union(frozenset([a.toNode])) parent_arcs[a.toNode] = a deq.extend([a.toNode]) path = list([]) curr = terminalNode while(curr != sourceNode): if (curr not in parent_arcs): err_msg = 'No augmenting path from {} to {}.'.format(sourceNode.uid, terminalNode.uid) raise StopIteration(err_msg) path.extend([parent_arcs[curr]]) curr = parent_arcs[curr].fromNode path.reverse() test = deque([path[0].fromNode]) for a in path: if(test[-1] != a.fromNode): err_msg = 'Bad path: {}'.format(path) raise ValueError(err_msg) test.extend([a.toNode]) return path

Ich habe eine Deque aus dem Python-Sammlungsmodul verwendet.

Um die obige Frage 2 zu beantworten, paraphrasiere ich einen weiteren Beweis von Sedgewick und Wayne: Proposition G. Die Anzahl der augmentierenden Pfade , die im Edmonds-Karp- Algorithmus mit N Knoten und A Bögen benötigt werden, beträgt höchstens NA/2 . Beweis: Jeder augmentierende Pfad hat einen Engpassbogen – einen Bogen , der aus dem Restgraphen gelöscht wird , weil er entweder einem „Push“ -Bogen entspricht, der bis zur Kapazitätsgrenze gefüllt wird, oder einem „Pull“ -Bogen , durch den der Fluss 0 wird. Jedes Mal, wenn an arc zu einem Engpass arc wird, muss die Länge jedes augmentierenden Pfads durch ihn um den Faktor 2 zunehmen. Dies liegt daran, dass jeder Knoten in einem Pfad nur einmal oder überhaupt nicht erscheinen kann (aus der Definition von path ), da die Pfade vorhanden sind Erkundet vom kürzesten zum längsten Pfad , das bedeutet, dass mindestens ein weiterer Knoten vom nächsten Pfad besucht werden muss, der durch den bestimmten Engpassknoten geht, was zwei zusätzliche Bögen auf dem Pfad bedeutet , bevor wir am Knoten ankommen . Da der Augmentationsweg höchstens N lang ist, kann jeder Bogen auf höchstens N/2 Augmentationswegen liegen, und die Gesamtzahl der Augmentationswege beträgt höchstens NA/2 .

Der Edmonds-Karp-Algorithmus wird in O(NA^2) ausgeführt. Wenn während des Algorithmus höchstens NA/2 -Pfade untersucht werden und die Erkundung jedes Pfads mit BFS N+A ist, dann ist der signifikanteste Term des Produkts und daher die asymptotische Komplexität O(NA^2) .

Sei mfp ein maxFlowProblemState .

 def edmonds_karp(mfp): sid, tid = mfp.sourceNodeUid, mfp.terminalNodeUid no_more_paths = False loop_count = 0 while(not no_more_paths): residual_digraph = get_residual_graph_of(mfp.G) try: asource = find_node_by_uid(mfp.sourceNodeUid, residual_digraph) aterm = find_node_by_uid(mfp.terminalNodeUid, residual_digraph) apath = bfs(asource, aterm, residual_digraph) paint_mfp_path(mfp, loop_count, apath) G = augment(apath, mfp.G) s = find_node_by_uid(sid, G) t = find_node_by_uid(tid, G) mfp = MaxFlowProblemState(G, s.uid, t.uid, mfp.maxFlowProblemStateUid) loop_count += 1 except StopIteration as e: no_more_paths = True return mfp

Die obige Version ist ineffizient und hat eine schlechtere Komplexität als O(NA^2) , da sie jedes Mal eine neue maximale Flusslösung und einen neuen Residuengraphen erstellt (anstatt vorhandene Digraphen zu modifizieren, wenn der Algorithmus fortschreitet). Um zu einer echten O(NA^2) -Lösung zu gelangen, muss der Algorithmus sowohl den Digraphen , der den Problemzustand des maximalen Flusses darstellt, als auch den zugehörigen Residuengraphen beibehalten. Der Algorithmus muss also vermeiden, unnötig über Bögen und Knoten zu iterieren, und ihre Werte und zugehörigen Werte im Residuendiagramm nur bei Bedarf aktualisieren.

Um einen schnelleren Edmonds-Karp -Algorithmus zu schreiben, habe ich mehrere Codeteile von oben umgeschrieben. Ich hoffe, dass das Durchgehen des Codes, der einen neuen Digraphen generiert hat, hilfreich war, um zu verstehen, was vor sich geht. Im schnellen Algorithmus verwende ich einige neue Tricks und Python-Datenstrukturen, auf die ich nicht im Detail eingehen möchte. Ich werde sagen, dass a.fromNode und a.toNode jetzt als Strings und UIDs zu Knoten behandelt werden. Für diesen Code sei mfps ein maxFlowProblemState

 import uuid def fast_get_mfps_flow(mfps): flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn if( (flow_to_t - flow_from_s) > 0.00): raise Exception('Infeasible st flow') return flow_to_t def fast_e_k_preprocess(G): G = strip_flows(G) get = dict({}) get['nodes'] = dict({}) get['node_to_node_capacity'] = dict({}) get['node_to_node_flow'] = dict({}) get['arcs'] = dict({}) get['residual_arcs'] = dict({}) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) get['nodes'][a.fromNode.uid] = a.fromNode get['nodes'][a.toNode.uid] = a.toNode lark = Arc(a.fromNode.uid, a.toNode.uid, FlowArcDatumWithUid(a.datum.capacity, a.datum.flow, uuid.uuid4())) if(a.fromNode.uid not in get['arcs']): get['arcs'][a.fromNode.uid] = dict({a.toNode.uid : dict({lark.datum.uid : lark})}) else: if(a.toNode.uid not in get['arcs'][a.fromNode.uid]): get['arcs'][a.fromNode.uid][a.toNode.uid] = dict({lark.datum.uid : lark}) else: get['arcs'][a.fromNode.uid][a.toNode.uid][lark.datum.uid] = lark for a in G.setOfArcs: if a.toNode.uid not in get['arcs']: get['arcs'][a.toNode.uid] = dict({}) for n in get['nodes']: get['residual_arcs'][n] = dict() get['node_to_node_capacity'][n] = dict() get['node_to_node_flow'][n] = dict() for u in get['nodes']: n_to_u_cap_sum = sum(a.datum.capacity for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) n_to_u_flow_sum = sum(a.datum.flow for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) get['residual_arcs'][n][u] = Arc(n,u,ResidualDatum(flow, 'push')) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) get['residual_arcs'][u][n] = Arc(u,n,ResidualDatum(flow, 'pull')) get['node_to_node_capacity'][n][u] = n_to_u_cap_sum get['node_to_node_flow'][n][u] = n_to_u_flow_sum return get def fast_bfs(sid, tid, get): parent_of = dict([]) visited = frozenset([]) deq = coll.deque([sid]) while len(deq) > 0: n = deq.popleft() if n == tid: break for u in get['residual_arcs'][n]: if (u not in visited): visited = visited.union(frozenset({u})) parent_of[u] = get['residual_arcs'][n][u] deq.extend([u]) path = list([]) curr = tid while(curr != sid): if (curr not in parent_of): err_msg = 'No augmenting path from {} to {}.'.format(sid, curr) raise StopIteration(err_msg) path.extend([parent_of[curr]]) curr = parent_of[curr].fromNode path.reverse() return path def fast_edmonds_karp(mfps): sid, tid = mfps.sourceNodeUid, mfps.terminalNodeUid get = fast_e_k_preprocess(mfps.G) no_more_paths, loop_count = False, 0 while(not no_more_paths): try: apath = fast_bfs(sid, tid, get) get = fast_augment(apath, get) loop_count += 1 except StopIteration as e: no_more_paths = True nodes = frozenset(get['nodes'].values()) arcs = frozenset({}) for from_node in get['arcs']: for to_node in get['arcs'][from_node]: for arc in get['arcs'][from_node][to_node]: arcs |= frozenset({get['arcs'][from_node][to_node][arc]}) G = DiGraph(nodes, arcs) mfps = MaxFlowProblemState(G, sourceNodeUid=sid, terminalNodeUid=tid, maxFlowProblemStateUid=mfps.maxFlowProblemStateUid) return mfps

Hier ist eine Visualisierung, wie dieser Algorithmus das beispielhafte Flussnetzwerk von oben löst. Die Visualisierung zeigt die Schritte, wie sie im Digraphen G widergespiegelt sind, der das aktuellste Flussnetzwerk darstellt, und wie sie im Residualdiagramm dieses Flussnetzwerks widergespiegelt sind. Augmentierende Pfade im Residualdiagramm werden als rote Pfade angezeigt, und der Digraph , der das Problem darstellt, der Satz von Knoten und Bögen , die von einem bestimmten augmentierenden Pfad betroffen sind, ist grün hervorgehoben. In jedem Fall werde ich die Teile des Diagramms hervorheben, die geändert werden (in Rot oder Grün), und dann das Diagramm nach den Änderungen anzeigen (nur in Schwarz).

Hier ist eine weitere Visualisierung, wie dieser Algorithmus ein anderes beispielhaftes Flussnetzwerk löst. Beachten Sie, dass dieser reelle Zahlen verwendet und mehrere Bögen mit denselben fromNode und toNode Werten enthält.

**Beachten Sie auch, dass die betroffenen Knoten im DiGraph des geflogenen Netzwerks möglicherweise nicht auf einem Pfad in G! .

Bipartite Graphen

Angenommen, wir haben einen Digraphen G , G ist zweigeteilt, wenn es möglich ist, die Knoten in G.setOfNodes in zwei Mengen ( part_1 und part_2 ) zu unterteilen, sodass es für jeden Bogen a in G.setOfArcs nicht wahr sein kann, dass a.fromNode in part_1 und a.toNode in part_1 . Es kann auch nicht wahr sein, dass a.fromNode in part_2 und a.toNode in part_2 .

Mit anderen Worten, G ist zweigeteilt , wenn es in zwei Mengen von Knoten unterteilt werden kann, sodass jeder Bogen einen Knoten in einer Menge mit einem Knoten in der anderen Menge verbinden muss.

Bipartit testen

Angenommen, wir haben einen Digraphen G , wir wollen testen, ob er zweigeteilt ist. Wir können dies in O(|G.setOfNodes|+|G.setOfArcs|) tun, indem wir den Graphen gierig in zwei Farben einfärben.

Zuerst müssen wir einen neuen Digraphen H erzeugen. Dieser Graph wird die gleiche Gruppe von Knoten wie G haben, aber er wird mehr Bögen als G haben. Jeder Bogen a in G erzeugt 2 Bögen in H ; der erste Bogen ist identisch mit a , und der zweite Bogen kehrt den Direktor von a ( b = Arc(a.toNode,a.fromNode,a.datum) ).

 Bipartition = coll.namedtuple('Bipartition',['firstPart', 'secondPart', 'G']) def bipartition(G): nodes = frozenset(G.setOfNodes arcs = frozenset(G.setOfArcs) arcs = arcs.union( frozenset( {Arc(a.toNode,a.fromNode,a.datum) for a in G.setOfArcs} ) ) H = DiGraph(nodes, arcs) H_as_dict = digraph_to_dict(H) color = dict([]) some_node = next(iter(H.setOfNodes)) deq = coll.deque([some_node]) color[some_node] = -1 while len(deq) > 0: curr = deq.popleft() for a in H_as_dict.get(curr): if (a.toNode not in color): color[a.toNode] = -1*color[curr] deq.extend([a.toNode]) elif(color[curr] == color[a.toNode]): print(curr,a.toNode) raise Exception('Not Bipartite.') firstPart = frozenset( {n for n in color if color[n] == -1 } ) secondPart = frozenset( {n for n in color if color[n] == 1 } ) if( firstPart.union(secondPart) != G.setOfNodes ): raise Exception('Not Bipartite.') return Bipartition(firstPart, secondPart, G)

Übereinstimmungen und maximale Übereinstimmungen

Angenommen, wir haben einen Digraphen G und das matching ist eine Teilmenge von Bögen aus G.setOfArcs . matching ist ein Matching, wenn für zwei beliebige Bögen a und b im matching gilt: len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Mit anderen Worten, keine zwei Bögen in einem Matching teilen sich einen Knoten .

Matching matching ist ein Maximum-Matching, wenn es kein anderes Matching alt_matching in G gibt, so dass len(matching) < len(alt_matching) . Mit anderen Worten, matching ist ein Maximum-Matching, wenn es der größte Satz von Bögen aus G.setOfArcs ist, der immer noch die Definition des Matchings erfüllt (das Hinzufügen eines Bogens , der nicht bereits im Matching enthalten ist, wird die Matching -Definition aufheben).

Ein Maximum-Matching - matching ist ein perfektes Matching, wenn für jeden Knoten n in G.setOfArcs ein Bogen a im matching existiert, wobei a.fromNode == n or a.toNode == n .

Maximales zweiteiliges Matching

Ein maximales bipartites Matching ist ein maximales Matching auf einem Digraphen G , der bipartit ist.

Da G bipartite ist, kann das Problem des Auffindens eines maximalen bipartiten Matchings in ein Maximum-Flow-Problem transformiert werden, das mit dem Edmonds-Karp- Algorithmus lösbar ist, und dann kann das maximale Bipartite-Matching aus der Lösung des Maximum-Flow-Problems wiedergewonnen werden.

Sei bipartition eine Bipartition von G .

Dazu muss ich einen neuen Digraphen ( H ) mit einigen neuen Knoten ( H.setOfNodes ) und einigen neuen Bögen ( H.setOfArcs ) generieren. H.setOfNodes enthält alle Knoten in G.setOfNodes und zwei weitere nodess , s (ein Quellknoten ) und t (ein Endknoten ).

H.setOfArcs enthält einen Bogen für jedes G.setOfArcs . Wenn ein Bogen a in G.setOfArcs und a.fromNode in bipartition.firstPart und a.toNode in bipartition.secondPart ist, dann schließen Sie a in H ein (Hinzufügen eines FlowArcDatum(1,0) ).

Wenn sich a.fromNode in bipartition.secondPart und a.toNode in bipartition.firstPart Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) in H.setOfArcs .

Die Definition eines zweiteiligen Graphen stellt sicher, dass kein Bogen Knoten verbindet, bei denen sich beide Knoten in derselben Partition befinden. H.setOfArcs enthält auch einen Bogen von Knoten s zu jedem Knoten in bipartition.firstPart . Schließlich enthält H.setOfArcs einen Bogen von jedem Knoten in bipartition.secondPart zu Knoten t . a.datum.capacity = 1 für alle a in H.setOfArcs .

Partitionieren Sie zuerst die Knoten in G.setOfNodes in die beiden disjunkten Mengen ( part1 und part2 ), so dass kein Bogen in G.setOfArcs von einer Menge zur selben Menge gerichtet ist (diese Partitionierung ist möglich, weil G bipartite ist). Als nächstes fügen Sie alle Bögen in G.setOfArcs , die von part1 zu part2 in H.setOfArcs sind. Erstellen Sie dann einen einzelnen Quellknoten s und einen einzelnen Endknoten t und erstellen Sie einige weitere Bögen

Erstellen Sie dann einen maxFlowProblemState .

 def solve_mbm( bipartition ): s = Node(uuid.uuid4(), FlowNodeDatum(0,0)) t = Node(uuid.uuid4(), FlowNodeDatum(0,0)) translate = {} arcs = frozenset([]) for a in bipartition.G.setOfArcs: if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) ): fark = Arc(a.fromNode,a.toNode,FlowArcDatum(1,0)) arcs = arcs.union({fark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a elif ( (a.toNode in bipartition.firstPart) and (a.fromNode in bipartition.secondPart) ): bark = Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) arcs = arcs.union({bark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a arcs1 = frozenset( {Arc(s,n,FlowArcDatum(1,0)) for n in bipartition.firstPart } ) arcs2 = frozenset( {Arc(n,t,FlowArcDatum(1,0)) for n in bipartition.secondPart } ) arcs = arcs.union(arcs1.union(arcs2)) nodes = frozenset( {Node(n.uid,FlowNodeDatum(0,0)) for n in bipartition.G.setOfNodes} ).union({s}).union({t}) G = DiGraph(nodes, arcs) mfp = MaxFlowProblemState(G, s.uid, t.uid, 'bipartite') result = edmonds_karp(mfp) lookup_set = {a for a in result.G.setOfArcs if (a.datum.flow > 0) and (a.fromNode.uid != s.uid) and (a.toNode.uid != t.uid)} matching = {translate[frozenset({a.fromNode.uid,a.toNode.uid})] for a in lookup_set} return matching

Minimale Knotenabdeckung

Eine Knotenabdeckung in einem Digraphen G ist eine Menge von Knoten ( cover ) aus G.setOfNodes , sodass für jeden Bogen a von G.setOfArcs dies wahr sein muss: (a.fromNode in cover) or (a.toNode in cover) .

Eine minimale Knotenüberdeckung ist die kleinstmögliche Menge von Knoten im Graphen, die noch eine Knotenüberdeckung ist. Der Satz von Konig besagt, dass in einem zweigeteilten Graphen die Größe der maximalen Übereinstimmung in diesem Graphen gleich der Größe der minimalen Knotenabdeckung ist, und er schlägt vor, wie die Knotenabdeckung von einer maximalen Übereinstimmung wiederhergestellt werden kann:

Angenommen, wir haben die Bipartition bipartition und das Maximum Matching matching . Definieren Sie einen neuen Digraphen H , H.setOfNodes=G.setOfNodes , die Bögen in H.setOfArcs sind die Vereinigung zweier Mengen.

Der erste Satz ist arcs a in matching , mit der Änderung, dass wenn a.fromNode in bipartition.firstPart und a.toNode in bipartition.secondPart dann a.fromNode und a.toNode im erstellten Bogen vertauscht werden, diesen Bögen ein a.datum.inMatching=True geben a.datum.inMatching=True Attribut, um anzuzeigen, dass sie von Bögen in einer übereinstimmenden .

Der zweite Satz ist arcs a NOT in matching , mit der Änderung, dass wenn a.fromNode in bipartition.secondPart und a.toNode in bipartition.firstPart dann a.fromNode und a.toNode im erstellten Bogen vertauscht werden (geben Sie solchen Bögen ein a.datum.inMatching=False Attribut).

Führen Sie als Nächstes eine Tiefensuche (DFS) aus, beginnend bei jedem Knoten n in bipartition.firstPart , der weder n == a.fromNode noch n == a.toNodes für einen beliebigen Bogen a in matching ist. Während des DFS werden einige Knoten besucht und andere nicht (speichern Sie diese Informationen in einem n.datum.visited -Feld). Die minimale Knotenüberdeckung ist die Vereinigung der Knoten {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } und der Knoten {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Dass dies von einem maximalen Matching zu einer minimalen Knotenüberdeckung führt, kann durch einen Widerspruchsbeweis gezeigt werden, man nehme einen Bogen a , der angeblich nicht überdeckt wurde, und betrachte alle vier Fälle, ob a.fromNode und a.toNode dazugehören (ob als toNode oder fromNode ) zu einem beliebigen Bogen im Matching - matching . Jeder Fall führt zu einem Widerspruch aufgrund der Reihenfolge, in der DFS die Knoten besucht, und der Tatsache, dass das matching ein Maximum-Matching ist.

Angenommen, wir haben eine Funktion, um diese Schritte auszuführen und den Satz von Knoten zurückzugeben, der die minimale Knotenabdeckung umfasst, wenn der Digraph G gegeben ist, und die maximale matching :

 ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ]) NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited']) def dfs_helper(snodes, G): sniter, do_stop = iter(snodes), False visited, visited_uids = set(), set() while(not do_stop): try: stack = [ next(sniter) ] while len(stack) > 0: curr = stack.pop() if curr.uid not in visited_uids: visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) ) visited_uids = visited.union(frozenset({curr.uid})) succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr}) stack.extend( succ.difference( frozenset(visited) ) ) except StopIteration as e: stack, do_stop = [], True return visited def get_min_node_cover(matching, bipartition): nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} ) G = DiGraph(nodes, None) charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} ) arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } ) arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } ) not_matching = bipartition.G.setOfArcs.difference( matching ) charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} ) arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } ) arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } ) arcs = arcs0.union(arcs1.union(arcs2.union(arcs3))) G = DiGraph(nodes, arcs) bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G) match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching}) match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching}) snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes) visited_nodes = dfs_helper(snodes, bip.G) not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes) H = DiGraph(visited_nodes.union(not_visited_nodes), arcs) cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } ) cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } ) min_cover_nodes = cover1.union(cover2) true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes}) return min_cover_nodes

Das lineare Zuordnungsproblem

Das lineare Zuordnungsproblem besteht darin, in einem gewichteten bipartiten Graphen eine Übereinstimmung mit maximaler Gewichtung zu finden.

Probleme wie das ganz am Anfang dieses Beitrags können als lineares Zuordnungsproblem ausgedrückt werden. Bei einer gegebenen Gruppe von Arbeitskräften, einer Reihe von Aufgaben und einer Funktion, die die Rentabilität einer Zuweisung einer Arbeitskraft zu einer Aufgabe angibt, möchten wir die Summe aller von uns vorgenommenen Zuweisungen maximieren; dies ist ein lineares Zuordnungsproblem .

Nehmen Sie an, dass die Anzahl der Aufgaben und Arbeiter gleich ist, obwohl ich zeigen werde, dass diese Annahme leicht zu entfernen ist. In der Implementierung stelle ich a.datum.weight für einen Bogen a dar.

 WeightArcDatum = namedtuple('WeightArcDatum', [weight])

Kuhn-Munkres-Algorithmus

Der Kuhn-Munkres-Algorithmus löst das lineare Zuordnungsproblem . Eine gute Implementierung kann O(N^{4}) Zeit in Anspruch nehmen (wobei N die Anzahl der Knoten im Digraphen ist, die das Problem darstellen). Eine einfacher zu erklärende Implementierung nimmt O(N^{5}) (für eine Version, die DiGraphs regeneriert) und O(N^{4}) für (für eine Version, die DiGraphs verwaltet ). Dies ähnelt den zwei unterschiedlichen Implementierungen des Edmonds-Karp- Algorithmus.

Für diese Beschreibung arbeite ich nur mit vollständigen bipartiten Graphen (solche, bei denen sich die Hälfte der Knoten in einem Teil der Bipartition und die andere Hälfte im zweiten Teil befinden). Bei der Worker-Task-Motivation bedeutet dies, dass es so viele Worker wie Tasks gibt.

Dies scheint eine wichtige Bedingung zu sein (was ist, wenn diese Sätze nicht gleich sind!), aber es ist einfach, dieses Problem zu beheben; Wie das geht, erkläre ich im letzten Abschnitt.

Die hier beschriebene Version des Algorithmus verwendet das nützliche Konzept von Bögen mit Nullgewichtung . Leider macht dieses Konzept nur Sinn, wenn wir eine Minimierung lösen (wenn wir statt der Maximierung der Gewinne unserer Worker-Task-Zuweisungen stattdessen die Kosten solcher Zuweisungen minimieren).

Glücklicherweise ist es einfach, ein maximales lineares Zuweisungsproblem in ein minimales lineares Zuweisungsproblem umzuwandeln, indem die Gewichte der Bogen a jeweils auf Ma.datum.weight werden, wobei M=max({a.datum.weight for a in G.setOfArcs}) . Die Lösung des ursprünglichen Maximierungsproblems ist identisch mit der Lösung des Minimierungsproblems, nachdem die Bogengewichte geändert wurden. Nehmen Sie also für den Rest an, dass wir diese Änderung vornehmen.

Der Kuhn-Munkres-Algorithmus löst den minimalen Gewichtungsabgleich in einem gewichteten zweiteiligen Graphen durch eine Folge maximaler Übereinstimmungen in ungewichteten zweiteiligen Graphen. Wenn wir ein perfektes Matching in der Digraph -Darstellung des linearen Zuordnungsproblems finden und wenn das Gewicht jedes Bogens im Matching Null ist, dann haben wir das Matching mit minimalem Gewicht gefunden, da dieses Matching darauf hindeutet, dass alle Knoten im Digraphen gewesen sind gepaart mit einem Bogen mit den geringstmöglichen Kosten (keine Kosten können kleiner als 0 sein, basierend auf früheren Definitionen).

Dem Matching können keine weiteren Bögen hinzugefügt werden (weil alle Knoten bereits gematcht sind) und es sollten keine Bögen aus dem Matching entfernt werden, da jeder mögliche Ersatzbogen einen mindestens ebenso großen Gewichtungswert haben wird.

Wenn wir ein maximales Matching des Teilgraphen von G finden, der nur arcs mit Nullgewicht enthält, und es kein perfektes Matching ist, haben wir keine vollständige Lösung (da das Matching nicht perfekt ist). Wir können jedoch einen neuen Digraphen H erzeugen, indem wir die Gewichte der Bögen in G.setOfArcs so ändern, dass neue Bögen mit 0-Gewicht erscheinen und die optimale Lösung von H dieselbe ist wie die optimale Lösung von G . Da wir garantieren, dass bei jeder Iteration mindestens ein Bogen mit Nullgewicht erzeugt wird, garantieren wir, dass wir in nicht mehr als |G.setOfNodes|^{2}=N^{2} solcher Iterationen zu einem perfekten Matching gelangen.

Angenommen, in bipartition bipartition enthält bipartition.firstPart Knoten , die Arbeitskräfte darstellen, und bipartition.secondPart stellt Knoten dar, die Aufgaben darstellen.

Der Algorithmus beginnt mit der Erzeugung eines neuen Digraphen H . H.setOfNodes = G.setOfNodes . Einige Bögen in H werden aus Knoten n in bipartition.firstPart generiert. Jeder solche Knoten n erzeugt einen Bogen b in H.setOfArcs für jeden Bogen a in bipartition.G.setOfArcs , wobei a.fromNode = n oder a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) wobei z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

Weitere Bögen in H werden aus den Knoten n in bipartition.secondPart generiert. Jeder solcher Knoten n erzeugt einen Bogen b in H.setOfArcs für jeden Bogen a in bipartition.G.setOfArcs , wobei a.fromNode = n oder a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) wobei z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Als nächstes bilde einen neuen Digraphen K , der nur aus den Bögen mit Nullgewicht von H und den auf diese Bögen fallenden Knoten besteht. Bilden Sie eine bipartition auf den Knoten in K und verwenden Sie dann solve_mbm( bipartition ) , um eine maximale Übereinstimmung ( matching ) auf K zu erhalten. Wenn das matching ein perfektes Matching in H ist (die Bögen beim matching H.setOfNodes auf alle Knoten in H.setOfNodes ), dann ist das matching eine optimale Lösung für das lineare Zuordnungsproblem .

Andernfalls, wenn matching nicht perfekt ist, generieren Sie die minimale Knotenabdeckung von K mit node_cover = get_min_node_cover(matching, bipartition(K)) . Definieren Sie als Nächstes z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Define nodes = H.setOfNodes , arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} , arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} , arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} . Das Symbol != im vorherigen Ausdruck fungiert als XOR-Operator. Dann arcs = arcs1.union(arcs2.union(arcs3)) . Als nächstes H=DiGraph(nodes,arcs) . Gehen Sie zurück zu das Label KMA . Der Algorithmus fährt fort, bis ein perfektes Matching erzeugt wird. Dieses Matching ist auch die Lösung des linearen Zuordnungsproblems .

 def kuhn_munkres( bipartition ): nodes = bipartition.G.setOfNodes arcs = frozenset({}) for n in bipartition.firstPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) for n in bipartition.secondPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) H = DiGraph(nodes, arcs) assignment, value = dict({}), 0 not_done = True while( not_done ): zwarcs = frozenset( {a for a in H.setOfArcs if a.datum.weight == 0} ) znodes = frozenset( {n.fromNode for n in zwarcs} ).union( frozenset( {n.toNode for n in zwarcs} ) ) K = DiGraph(znodes, zwarcs) k_bipartition = bipartition(K) matching = solve_mbm( k_bipartition ) mnodes = frozenset({a.fromNode for a in matching}).union(frozenset({a.toNode for a in matching})) if( len(mnodes) == len(H.setOfNodes) ): for a in matching: assignment[ a.fromNode.uid ] = a.toNode.uid value = sum({a.datum.weight for a in matching}) not_done = False else: node_cover = get_min_node_cover(matching, bipartition(K)) z = min( frozenset( {a.datum.weight for a in H.setOfArcs if a not in node_cover} ) ) nodes = H.setOfNodes arcs1 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} ) arcs2 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} ) arcs3 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} ) arcs = arcs1.union(arcs2.union(arcs3)) H = DiGraph(nodes,arcs) return value, assignment

Diese Implementierung ist O(N^{5}) , da sie bei jeder Iteration eine neue maximale Übereinstimmung matching ; Ähnlich wie bei den beiden vorherigen Implementierungen von Edmonds-Karp kann dieser Algorithmus so modifiziert werden, dass er den Abgleich verfolgt und ihn intelligent an jede Iteration anpasst. Wenn dies erledigt ist, wird die Komplexität O(N^{4}) . Eine fortgeschrittenere und neuere Version dieses Algorithmus (die einige fortgeschrittenere Datenstrukturen erfordert) kann in O(N^{3}) ausgeführt werden. Details sowohl zur einfacheren Implementierung oben als auch zur fortgeschritteneren Implementierung finden Sie in diesem Beitrag, der diesen Blogbeitrag motiviert hat.

Keine der Operationen an Bogengewichten ändert die endgültige Zuweisung, die vom Algorithmus zurückgegeben wird. Hier ist der Grund: Da unsere Eingabegraphen immer vollständige bipartite Graphen sind, muss eine Lösung jeden Knoten in einer Partition über den Bogen zwischen diesen beiden Knoten auf einen anderen Knoten in der zweiten Partition abbilden. Beachten Sie, dass die an den Bogengewichten durchgeführten Operationen niemals die Reihenfolge (nach Gewicht geordnet) der auf einen bestimmten Knoten einfallenden Bögen ändern.

Wenn der Algorithmus bei einer perfekten vollständigen zweiteiligen Übereinstimmung endet, wird daher jedem Knoten ein Bogen mit Nullgewichtung zugewiesen, da sich die relative Reihenfolge der Bögen von diesem Knoten während des Algorithmus nicht geändert hat und da ein Bogen mit Nullgewichtung der billigste mögliche Bogen ist und das perfekte vollständige bipartite Matching garantiert, dass für jeden Knoten ein solcher Bogen existiert. Dies bedeutet, dass die generierte Lösung tatsächlich dieselbe ist wie die Lösung aus dem ursprünglichen linearen Zuordnungsproblem ohne jegliche Änderung der Bogengewichte .

Unausgeglichene Aufgaben

Es scheint, dass der Algorithmus ziemlich begrenzt ist, da er wie beschrieben nur auf vollständigen zweigeteilten Graphen funktioniert (solche, bei denen sich die Hälfte der Knoten in einem Teil der Bipartition und die andere Hälfte im zweiten Teil befinden). Bei der Worker-Task-Motivation bedeutet dies, dass es so viele Worker wie Tasks gibt (scheint ziemlich einschränkend zu sein).

Es gibt jedoch eine einfache Transformation, die diese Einschränkung aufhebt. Angenommen, es gibt weniger Worker als Tasks, wir fügen einige Dummy-Worker hinzu (ausreichend, um den resultierenden Graphen zu einem vollständigen bipartiten Graphen zu machen). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

Suppose that there are more tasks than workers. We add some dummy tasks (enough to make the resulting graph a complete bipartite graph ). Each dummy task has an arc directed from each worker to the dummy task. Each such arc has a weight of 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any worker assigned to dummy task is not employed during the period.

A Linear Assignment Example

Finally, let's do an example with the code I've been using. I'm going to modify the example problem from here. We have 3 tasks: we need to clean the bathroom , sweep the floor , and wash the windows .

The workers available to use are Alice , Bob , Charlie , and Diane . Each of the workers gives us the wage they require per task. Here are the wages per worker:

If we want to pay the least amount of money, but still get all the tasks done, who should do what task? Start by introducing a dummy task to make the digraph representing the problem bipartite.

Supposing that the problem is encoded in a digraph , then kuhn_munkres( bipartition(G) ) will solve the problem and return the assignment. It's easy to verify that the optimal (lowest cost) assignment will cost $5.

Here's a visualization of the solution the code above generates:

That is it. You now know everything you need to know about the linear assignment problem.

You can find all of the code from this article on GitHub.

Weiterführende Literatur im Toptal Engineering Blog:

• Graph Data Science mit Python/NetworkX