Frage zu Ford-Fulkerson und Rückflüssen

Osterlaus
BSc Spammer
BSc Spammer
Beiträge: 1263
Registriert: 23. Aug 2007 12:46
Wohnort: DA

Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Osterlaus »

Moin,
mir kam eben das Beispiel aus der englischen Wikipedia unter, das ja ähnlich auch im Buch verwendet wird (Seite 664 bzw. Abbildung 26.6). Ich geh jetzt erstmal von dem Wikipedia-Beispiel aus. Da sieht der Startgraph so aus: Bild In unserer Implementierung würden nun zunächst alle Pfade gesucht werden, die von den Quellen zu den Senken führen (das wären hier also A->B->C->D, A->B->D und A->C->D) und die werden dann nacheinander verstärkt. Jeder Pfad wird direkt soweit verstärkt, wie es geht, also um die minimale Restkapazität seiner Einzelkanten. Das ganze würde bei uns recht schnell durchlaufen: A->B->C->D wird um 1 verstärkt, anschließend A->B->D um 999 und A->C->D um 999. Wer hat aber nun recht, wenn die Wikipedia da ein totales Hickhack draus macht, weil eine Kante C->B hinzuerfunden wird? Ebenso ist mir das im Buch nicht ganz klar, warum ich mir das Leben da schwer machen soll...
Nico

Mirlix_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 188
Registriert: 3. Mär 2006 14:57

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Mirlix_ »

Das Beispiel ist schon richtig, es fliesst auch nie was wirklich von C nach B, der Algo nutzt nur diesen Trick um den maximalen Fluss leichter berrechnen zu koennen. Wenn man sich Bild 2 und 3 anschaut sieht man was eigentlich wirklich passiert. Es fliesst nichts vom C nach B sondern es wird nur umgeleitet. Die eine Einheit die von A -> B -> C -> D fliesst wird umgeleitet sodass sie nun von A -> B -> D fliesst. Nun hat man an das Prob das von C -> nach D eine Einheit fliesst ohne das eien reingeht, daher kommt von A nach C eine Einheit um das zu ersetzen. Da diese Prozess aber zu komplex waere nimmt man an das man jede Kante auch als Rueckflusskante nehmen kann, also auch in die andere Richtung etwas fliessen lassen kann. Im Endeffekt wird damit aber nur dafuer gesorgt das der Fluss ueberall erhalten bleibt und es fliesst nie was von C nach B, da nur schon vorhander Fluss umgeleitet wird.
"If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with." Edsger W. Dijkstra

Benutzeravatar
bearmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 121
Registriert: 20. Okt 2006 13:53
Wohnort: Darmstadt
Kontaktdaten:

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von bearmann »

Im deutschen Wikipedia sieht man es mMn noch besser...
Mir ist allerdings noch nicht ganz klar, inwieweit man diesen "Trick" explizit implementieren muss/sollte/kann.
Weil auch wenn ich "volle" Rückflusskanten ignoriere und sie als "tot" betrachte, komme ich auf den selben maximalen Fluss - zumindest in den beiden Beispielen.

Grüße,
bearmann

SebFreutel
Computerversteher
Computerversteher
Beiträge: 317
Registriert: 30. Okt 2006 21:54

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von SebFreutel »

bearmann hat geschrieben:Mir ist allerdings noch nicht ganz klar, inwieweit man diesen "Trick" explizit implementieren muss/sollte/kann.
Muss!
bearmann hat geschrieben:Weil auch wenn ich "volle" Rückflusskanten ignoriere und sie als "tot" betrachte, komme ich auf den selben maximalen Fluss - zumindest in den beiden Beispielen.
Dann hier ein Beispiel wo ein BFS allein versagt:
rueckfluss_noetig.png
rueckfluss_noetig.png (9.5 KiB) 1421 mal betrachtet
(Grün=Quelle, Rot=Senke, Kapazität jeder Kante gleich, z.B. 1, Blau=Weg, den ein BFS nimmt, maximaler Fluss dann 1 statt 2, da ohne Verwendung der mittleren Kante als Rückkante kein Weg mehr gefunden wird)

Benutzeravatar
Maeher
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 282
Registriert: 14. Okt 2007 23:02
Kontaktdaten:

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Maeher »

In den Testfällen die mitgeliefert werden, werden die Rückkanten nicht benötigt. Auch in den meisten anderen Fällen ist es möglich den Fluss korrekt ohne Rückkanten zu berechnen. Allerdings führt der Algorithmus dann nicht in jedem Fall zum Ziel, da es in vielen Fällen davon abhängt, in welcher Reihenfolge man die Pfade versucht auszulasten. Ein Beispiel ist folgendes:

Code: Alles auswählen

Digraph {
W -> A [label="5"];
W -> B [label="11"];
W -> C [label="7"];
A -> D [label="5"];
A -> E [label="7"];
B -> D [label="7"];
B -> E [label="3"];
B -> F [label="3"];
C -> E [label="3"];
C -> F [label="3"];
D -> 23 [label="5"];
E -> 23 [label="11"];
F -> 23 [label="7"];
}
Der korrekte Fluss ist von "W" nach "23" ist 22.
graph.png
graph.png (38.66 KiB) 1414 mal betrachtet
Wenn man das ganze ohne Rückkanten implementiert kann es sein, dass man die Pfade in einer Reihenfolge benutzt, dass zB nur 17 rauskommt. Das Problem tritt auf, wenn man zB zuerst den linken Pfad über W->A->D->23 auslastet. Da das nicht mehr rückgängig gemacht werden kann, lässt sich die 11er Kante in der Mitte nicht mehr voll auslasten. Mit Rückwärtskanten, wird die "Fehlentscheidung jedoch korrigiert, und die Reihenfolge der Abarbeitung ist irrelevant.


(Und ich sehe, ich war mal wieder zu langsam :) )

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Mspringer »

Muss Mäher da zustimmen. Man kann alle Standardtests auch ohne Rückkanten schaffen. Man braucht nur seeeehr viel Glück. Bei uns hats z.B. auch geklappt, und es war ne richtige Fricklerrei, einen Testfall zu schreiben, dass er Rückkanten gehen muss. Jetzt haben wir sie auch drin. Aber es würde mich brennend interessieren, ob auch die Extratestfälle damit laufen. Ich wette für ja, unsere alte implementierung hat bestimmt son dussel ;D

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von s!mon »

Also es wird ja mit Iksburg4 getestet, insofern kannst du dir ja selber ein paar Testfälle basteln. Bei mir sind zb heute trotz Rückkanten Tests durchgefallen. Ich hatte vergessen, dass man eine Rückkante ja nur durchlaufen darf, wenn sie einen Fluss != 0 hat, also schon etwas über die normale Kante läuft. Bei den Standardtestfällen hatte das keinen Unterschied gemacht..

Telefonjoker
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 161
Registriert: 19. Apr 2008 21:02

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Telefonjoker »

ich tu mir mit den Rückkanten total schwer.

Also, cf(u,v) = c(u,v) - f(u,v)
Stimmt das so? Das reicht doch noch nicht, oder?

Da gibt's doch noch diesen Fall, dass man "ein bißchen Fluss" auf die Rückkante abwälzen kann.
Gilt das nur für richtige Kante (u,v); (v,u), oder auch für die von mir erstellten Rückkanten?

Scheiße, das verwirrt mich...

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Mspringer »

Denk doch mal scharf nach. Bei Rückkanten machst du genau das gegenteil von vorwärtskanten. Anstatt dein Restnetzwerk zu veringern und den Rückfluss zu erhöhen, musst du bei Rückkanten natürlich den Rückfluss veringern und das Restnetzwerk wieder erhöhen.

Außerdem, ne Rückkante von ner Rückkante wäre ja irgendwie wieder die Vorwärtskante.

Benutzeravatar
Rinderhack
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 151
Registriert: 17. Okt 2005 20:13
Wohnort: Großostheim
Kontaktdaten:

Re: Frage zu Ford-Fulkerson und Rückflüssen

Beitrag von Rinderhack »

möchte jemand seine Rückkantentestfälle veröffentlichen?

edit: schade dann halt nicht....

Antworten

Zurück zu „Archiv“