Finden negativer Zyklen für den Algorithmus zum Aufheben des Zyklus

Ich implementiere den Algorithmus zum Aufheben des Zyklus, um eine optimale Lösung für das Problem des minimalen Kostenflusses zu finden. Durch das Auffinden und Entfernen negativer Kostenzyklen im Restnetz werden die Gesamtkosten in jeder Runde gesenkt. Um einen negativen Zyklus zu finden, verwende ich den Bellman-Ford-Algorithmus.

Mein Problem ist: Bellman-ford findet nur Zyklen, die von der Quelle aus erreichbar sind, aber ich muss auch Zyklen finden, die nicht erreichbar sind.

Beispiel: Im folgenden Netzwerk haben wir bereits einen maximalen Fluss angewendet. Die Kante macht es sehr teuer. Im Restnetz haben wir einen negativen Kostenzyklus mit Kapazität . Wenn wir es entfernen, erhalten wir eine billigere Lösung mit den Kanten und , aber wir können es nicht von der Quelle . $(A, B)$ $1$ $(A, C)$ $(C, T)$ $S$

Etiketten: Durchfluss / Kapazität, Kosten

Geben Sie hier die Bildbeschreibung ein

Natürlich könnte ich Bellman-ford wiederholt mit jedem Knoten als Quelle ausführen, aber das klingt nicht nach einer guten Lösung. Ich bin ein wenig verwirrt, weil alle Papiere, die ich lese, diesen Schritt zu überspringen scheinen.

Können Sie mir sagen, wie man mit Bellman-Ford jeden negativen Zyklus findet (erreichbar oder nicht)? Und wenn nicht möglich, welchen anderen Algorithmus schlagen Sie vor?

algorithms graph-theory shortest-path network-flow Patrick Schmidt
quelle

Wenn ein Zyklus nicht über die Quelle erreicht werden kann, wie kann er den Gesamtfluss beeinflussen?

Nicholas Mancuso

Dies hat keinen Einfluss auf den Durchflusswert, sondern auf die Gesamtkosten. Siehe das neue Beispiel.

Patrick Schmidt

Ich denke, Sie sollten Bellman-Ford aus der Spüle laufen lassen, nein? Wenn Sie einen maximalen Durchfluss

, gibt es unter dem Restgraphen

keinen Pfad von

nach

. Daher sollte Bellman-Ford mit

auf

gefahren werden .

f

$f$

G_{f}

$G_f$

s

$s$

t

$t$

G_{f}

$G_f$

t

$t$

Nicholas Mancuso

Antworten:

Um meinen Kommentar zu erweitern, denken Sie daran, dass dieser Algorithmus zum Ermitteln des Min-Cost-Flow auf der Tatsache beruht, dass maximal ist. Mit dem ersten zu finden Ford-Fulkerson laufen und das resultierende Restnetz , die Kosten wird dann durch Auffinden negative Zyklen in reduzierten . Das heißt, indem wir negative Zyklen in , ändern wir nicht die Durchflussmenge , sondern lediglich die Kosten. $f$ $f$ $G_f$ $f$ $G_f$ $G_f$ $f$

Wenn wir nun Bellman-Ford von in ausführen, können wir Kanten mit nicht negativem Fluss (per Definition von ) rückwärts verfolgen . Wenn Zyklen an Kanten in diesen Pfaden angrenzen, können wir eine gewisse Menge an Fluss auf andere Kanten im Zyklus "übertragen". Mit anderen Worten, wir halten den Nettofluss für einige Zyklen gleich, können aber die Kosten ändern. $t$ $G_f$ $G_f$

Beachten Sie, dass ein nicht erreichbarer Zyklus von einen Nullfluss haben muss. Andernfalls hätten wir einen Widerspruch darin, dass maximal ist. $t$ $f$

^{Ich entschuldige mich für die "Handwelligkeit" dieser Erklärung. Ich werde versuchen, formeller zu sein, wenn ich heute Abend Zeit habe.}

Nicholas Mancuso
quelle

T

$T$

Mein Vorschlag: Sie müssen den Algorithmus von T aus starten, um einen negativen Zyklus in Ihrem Restnetzwerk zu finden. Das Ergebnis sollte das gleiche sein, aber dann können Sie den Kreis erreichen

Sven Jung
quelle

Dies funktioniert für dieses Diagramm, aber Sie können negative Zyklen haben, die weder mit S noch mit T verbunden sind. Ich vermute, dass das OP eine Lösung wünscht, die im Allgemeinen funktioniert.

Peter Shor

Ja, im Allgemeinen können Sie nicht jeden negativen Zyklus finden, aber das OP möchte sein verbleibendes Netzwerk verbessern, indem es die Kosten überprüft. Dann spielen unerreichbare negative Kreise keine Rolle

Sven Jung

Ich möchte dies nutzen, um einen minimalen Kostenfluss zu erhalten. Die neue Frage wäre also: Reicht es aus, jeden Zyklus zu eliminieren, der von der Spüle

aus erreichbar ist

T

$T$ (im Restnetz). Im Moment kann ich kein Gegenbeispiel finden

Patrick Schmidt

Sie können einen Fluss so anzeigen, dass er entweder von

ausgeht und zu

, oder jede Kante umkehren und ihn so anzeigen, dass er von

ausgeht und zu

. Wenn das Eliminieren jedes Zyklus, der von der Quelle

aus erreichbar ist, nicht funktioniert, dann eliminiert das Eliminieren jedes Zyklus, der von der Senke

aus erreichbar ist

S

$S$

T

$T$

T

$T$

S

$S$

S

$S$

T

$T$ nicht. Die Quelle und die Senke verhalten sich symmetrisch.

Peter Shor

Natürlich ist es dasselbe, wenn Sie jede Kante umkehren und von T ausgehen, weil sich nichts geändert hat. Aber warum nicht bei T beginnen, ohne die Kanten umzukehren? Dann sollten Sie einen erreichbaren negativen Zyklus finden, falls vorhanden. Die Frage ist, ob die nicht erreichbaren negativen Zyklen wirklich keine Rolle spielen

Sven Jung

Ich denke, es reicht nicht aus, Bellman-Ford von T oder S aus zu betreiben. Betrachten Sie ein Beispiel, bei dem es eine Kante von S nach T und einen Zyklus mit negativen Kosten gibt, der weder von S noch von T erreichbar ist.

Eine Lösung besteht darin, ein Hilfs-S 'hinzuzufügen und eine Kante von S' zu jedem anderen Scheitelpunkt mit 0 Kosten hinzuzufügen. Dann fahren Sie Bellman-Ford von S '. Auf diese Weise sind alle negativen Zyklen von S 'aus erreichbar.

Darüber hinaus müssen Sie diesen Hilfsscheitelpunkt S 'in Ihrer Implementierung nicht wirklich hinzufügen. Initialisieren Sie einfach d (v) = 0 für einen beliebigen Scheitelpunkt v.

Sehen Sie, wie Boost Graph Library es implementiert.

Hongjie Chen
quelle