Restgrafik im maximalen Durchfluss

14

Ich lese über die maximale Durchfluss Problem hier . Ich konnte die Intuition hinter dem Residual Graph nicht verstehen. Warum berücksichtigen wir Hinterkanten bei der Berechnung des Durchflusses?

Kann mir jemand helfen, das Konzept der Restgrafik zu verstehen?

Wie ändert sich der Algorithmus in ungerichteten Diagrammen?

csds
quelle

Antworten:

28

Die Intuition, die dem Residuendiagramm im Maximum-Flow-Problem entspricht liegt, wird in dieser Vorlesung sehr gut dargestellt . Die Erklärung lautet wie folgt.

Nehmen wir an , wir versuchen , die maximale Strömungsproblem für das folgende Netzwerk zu lösen (wobei jedes Etikett f e / c e bezeichnet sowohl die Strömungs f e durch eine Kante geschoben e und die Kapazität C e dieser Kante):Gfe/cefeece

Laufendes Beispiel

Ein möglicher gieriger Ansatz ist der folgende:

  1. Wähle einen beliebigen augmentierenden Pfad , der von der Quelle Eckpunkt geht s an den Senkenscheitelpunkt T , so dass ePst ); das heißt, alle Kanten ine(ePfe<ce haben eine verfügbare Kapazität.P
  2. Schieben Sie den maximal möglichen Durchfluss durch diesen Pfad. Der Wert von Δ wird durch den Engpass von P bestimmt ; das heißt, die Kante mit der minimalen verfügbaren Kapazität. Formal ist Δ = min e P ( c e - f e )ΔΔPΔ=mineP(cefe) .
  3. Fahren Sie mit Schritt 1 fort, bis keine Erweiterungspfade mehr vorhanden sind.

Suchen Sie also einen Pfad mit verfügbarer Kapazität, senden Sie den Datenfluss entlang dieses Pfads und wiederholen Sie den Vorgang.

In findet eine mögliche Ausführung der obigen Heuristik drei Erweiterungspfade P 1 , P 2 und P 3 in dieser Reihenfolge. Diese Pfade drücken jeweils 2, 2 und 1 Durchflusseinheiten für einen Gesamtdurchfluss von 5:GP1P2P3

Mögliche Ausführung des Greedy-Ansatzes für maximalen Durchfluss

Die Auswahl der Pfade in dieser Reihenfolge führt zu einer optimalen Lösung. Was passiert jedoch, wenn wir zuerst auswählen (dh vor P 1 und P 2 )?P3P1P2

Pfad blockieren

Wir erhalten einen sogenannten blockierenden Fluss : Es gibt keine zusätzlichen Pfade mehr. In diesem Fall beträgt der Gesamtdurchfluss 3, was nicht optimal ist. Dieses Problem kann behoben werden, indem Rückgängig- Vorgänge zugelassen werden (dh der Fluss kann in umgekehrter Reihenfolge gesendet werden, wodurch die Arbeit früherer Iterationen rückgängig gemacht wird): Schieben Sie einfach 2 Fluss-Einheiten wie folgt von Scheitelpunkt nach Scheitelpunkt v zurück :wv

Rückwärts fließen

Das Kodieren dieser zulässigen Rückgängig-Operationen ist das Hauptziel des Restgraphen .

Ein Restgraph eines Netzwerks G hat die gleiche Menge von Eckpunkten wie G und enthält für jede Kante e = ( u , v ) G :RGGe=(u,v)G

  • Eine Vorwärtskante mit der Kapazität c e - f e , wenn c e - f e > 0 iste=(u,v)cefecefe>0 .

  • Eine Rückwärtskante mit einer Kapazität f e , wenn f e > 0 .e=(v,u)fefe>0

Betrachten Sie zum Beispiel den Restgraphen , der nach der ersten Iteration der gierigen Heuristik erhalten wird, wenn die Heuristik zuerst P 3 auswählt (dh, wenn sie den blockierenden Fluss erhält):RP3

Restliche Grafik

Es ist zu beachten, dass die Rückgängig- Operation, die 2 Durchflusseinheiten von nach v verschiebt , als Vorwärtspfad (Aufstockungspfad) von s nach t in R codiert wird :wvstR

Augmentierungspfad im Restdiagramm

Allgemein:

Wenn ein Erweiterungspfad in dem Restgraphen R ausgewählt wird :PR

  • Jede Kante in , die einer Vorwärtskante in G entspricht, erhöht den Fluss, indem eine Kante mit verfügbarer Kapazität verwendet wird.PG
  • Jede Kante in , die einer Kante entspricht, die in G rückwärts verläuft, macht den Fluss rückgängig, der in der Vergangenheit in Vorwärtsrichtung gedrückt wurde.PG

Dies ist die Grundidee der Ford-Fulkerson-Methode .

Die Ford-Fulkerson-Methode geht genauso vor wie der oben beschriebene gierige Ansatz, stoppt jedoch nur, wenn der Restgraph keine zusätzlichen Pfade mehr enthält (nicht im ursprünglichen Netzwerk). Die Methode ist korrekt (dh sie berechnet immer einen maximalen Durchfluss), da der Restgraph die folgende Optimalitätsbedingung festlegt :

Bei gegebenem Netzwerk ist ein Fluss f in G maximal, wenn der Restgraph keinen s - t - Pfad enthält.GfGst

Mario Cervera
quelle
Gibt es ein Beispiel, in dem Pfade in der Reihenfolge der kürzesten Länge hinzugefügt werden, wie im Edmonds-Karp-Algorithmus beschrieben? In Ihrem Gegenbeispiel hat der erste Pfad die Länge 3, während ein kürzerer (dh 2) Pfad gefunden werden kann und zuerst hinzugefügt wird, wenn wir Edmonds-Karp ausführen.
Roy
Sie können einfach festlegen, dass alle - Pfade in der Originalgrafik die Länge 3 haben . Teilen Sie dazu den Scheitelpunkt v in zwei Scheitelpunkte v 1 und v 2 . Teilen Sie dann w in w 1 und w 2 auf . Addiere auch zwei Kanten ( v 1 , v 2 ) und ( w 1 , w 2 ) mit der Kapazität 2 . Die Kante, die ursprünglich von v nach w ging, geht jetzt vonst3vv1v2ww1w2(v1,v2)(w1,w2)2vw bis w 2 . Wir können die gleiche Art von Blockierungsfluss erhalten, wenn wir anfangs den Pfad wählen, der die Kante enthält ( v 1 , w 2 ) . v1w2(v1,w2)
Mario Cervera
Ihr Beispiel macht Sinn. Wir können das Diagramm jederzeit auf andere Kanten im Schnitt erweitern, damit sich die betreffende Kante auf einem der kürzesten Pfade befindet.
Roy
3

Die Intuition hinter dem verbleibenden Netzwerk ist, dass es uns ermöglicht, einen bereits zugewiesenen Fluss "abzubrechen", dh wenn wir bereits 2 Flusseinheiten von nach B zugewiesen habenABBAAB

Banach Tarski
quelle