Maximaler Durchfluss mit Ford-Fulkerson und DFS

22

Diese Frage bezieht sich auf die zeitliche Komplexität des Ford-Fulkerson-Maximalflussalgorithmus, wenn DFS zum Auffinden von Erweiterungspfaden verwendet wird.

Es gibt ein bekanntes Beispiel, das zeigt, dass man mit DFS eine lineare Anzahl von Iterationen im maximalen Fluss benötigen kann, siehe zum Beispiel die oben verlinkte Wikipedia-Seite.

Dieses Beispiel überzeugt mich jedoch nicht wirklich: Eine Standard-DFS-Implementierung würde nicht das Verhalten aufweisen, zwischen B und C als erstem Knoten des Pfads zu wechseln (unter Verwendung der Scheitelpunktnamen von der Wikipedia-Seite).

Setzen wir also die sehr natürliche Bedingung auf, dass die DFS bei jedem Besuch eines Knotens die Nachbarn von in derselben Reihenfolge untersucht. Gibt es noch Beispiele, für die FF mit DFS eine große Anzahl von Iterationen verwendet?uuu

Als Variante nehmen wir an, dass wir die zusätzliche Eigenschaft haben, dass die unterschiedlichen Anordnungen der Nachbarn mit einer willkürlichen, aber festen globalen Anordnung der Eckpunkte übereinstimmen. Macht das einen Unterschied?

Dies scheint mir eine ziemlich grundlegende Frage zu sein; Ich entschuldige mich im Voraus, wenn die Antwort bekannt ist, aber ich bin kein Experte für Strömungen und ein bisschen googeln hat nichts ergeben.

Edit: Die Antwort lautet ja, es gibt noch Beispiele. Siehe Abbildung 2 dieses Dokuments . In diesen Beispielen nimmt FF mit DFS eine exponentielle (in der Anzahl der Eckpunkte) Anzahl von Iterationen an. Es scheint leicht zu beweisen, dass dies eng ist, dh dass die Anzahl der Iterationen immer durch (unabhängig von den Werten der Kapazitäten).2O(n)

Per Austrin
quelle
4
Ich habe mich über dieselbe Frage gewundert.
Luca Trevisan
1
(1) Gute Frage. (2) Ich denke, dass das schlechte Beispiel (wie das in Wikipedia) normalerweise als ein Grund eingeführt wird, warum eine Überlegung über die Besuchsreihenfolge notwendig ist, nicht als ein Grund gegen die Verwendung der Tiefensuche.
Tsuyoshi Ito
6
Ich glaube nicht, dass ich jetzt FF unterrichten kann, ohne eine Antwort auf diese Frage zu haben. Nett !!
Suresh Venkat
Ist es nicht möglich, den maximalen Fluss in einer minimalen Anzahl von NP-Complete-Iterationen zu finden?
User834

Antworten:

13

Wenn Adjazenzlisten im Voraus festgelegt wurden, endet die DFS immer (auch wenn irrationale Kapazitäten vorhanden sind).

Siehe Dean, Goemans, Immorlica - Endliche Beendigung von "Augmenting Path" -Algorithmen in Gegenwart irrationaler Problemdaten .

Ilyaraz
quelle
11
Vielen Dank. Das allein beantwortet meine Frage nicht, aber das in Abbildung 2 der Arbeit von Dean-Goemans-Immorlica gezeigte Beispiel zeigt eine rekursive Konstruktion auf der Grundlage des Standardbeispiels, die meine Frage beantwortet und zeigt, dass FF mit DFS exponentiell viele erfordern kann Iterationen.
Per Austrin