Netzwerk-Algorithmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo allerseits,
Ich sitze nun mittlerweile schon einige Tage an diesem Algorithmus und komme nicht voran.
Es ist mir auch schwierig eine konkrete Frage dazu zu stellen, weil ich ab folgendem Punkt die Theorie nicht mehr nachvollziehen kann:
Zitat aus dem Skript:
[..] Ein $f$-augmentierender Pfad $P$ eines Netzwerks [mm] $\left(G,c,s,t\right)$ [/mm] bzgl. eines Flusses $f$ ist ein [mm] $s-t-\text{Pfad}$ [/mm] in dem Residualgraphen [mm] $G_f$. [/mm] Wir sagen $f$ wird durch $P$ um [mm] $\gamma \in \IR_{+}$ [/mm] augmentiert, falls für jede Kante $e'$ von $P$ folgende Operation ausgeführt wird: Ist $e' [mm] \in [/mm] E$, so wird [mm] $f\left(e\right)$ [/mm] um [mm] $\gamma$ [/mm] erhöht. Ist dagegen $e' = [mm] \overleftarrow{e}$ [/mm] für ein $e [mm] \in [/mm] E$, so wird [mm] $f\left(e\right)$ [/mm] um [mm] $\gamma$ [/mm] erniedrigt. [..]
Später dann, steht im Skript folgender Algorithmus:
[mm]
\paragraph{FordFulkerson$\left(G = \left(V, E\right),c,s,t\right)$:}
\mbox{}\par\nobreak\vspace{-\parskip}\nobreak\noindent
\begin{tabular}{ll}
1.) & for all $e \in E$ do $f\left(e\right) = 0$; \\
2.) & Konstruiere einen $f$-augmentierenden Pfad $P$. Falls es einen Solchen nicht gibt, so gib $f$ aus und \textbf{Stop!} \\
3.) & Setze $\gamma := \min_{e}c_{f}\left(e\right)$, wobei $e$ die Kanten von $P$ durchläuft. \\
4.) & Augmentiere $f$ durch $P$ um $\gamma$. \\
5.) & goto step 2.
\end{tabular}
[/mm]
Ich habe unter Anderem versucht das Ganze am folgenden Netzwerk nachzuvollziehen:
[Dateianhang nicht öffentlich]
Wenn ich's richtig verstehe, müßte der Residualgraph dafür genauso aussehen, weil hier (noch) nichts fließt, oder? Wenn das stimmt, habe ich Punkt 1 des Algorithmus bereits erfüllt. Bei Punkt 2 bin ich mir nicht sicher. Kann ich mir einen beliebigen Pfad aussuchen? Was spräche z.B. gegen den Pfad $s [mm] \to v_1 \to v_2 \to v_5 \to [/mm] t$? So und jetzt setze ich z.B. [mm] $\gamma [/mm] := 1$. Danach starte ich bei $s$, gehe den Pfad entlang und erhöhe bei jeder Kante den Fluß um 1, soweit richtig? Und was passiert, wenn ich bei $t$ angekommen bin? Bisher nehme ich an, daß ich dann wieder bei $s$ starte, und das Ganze solange wiederhole bis die maximale Kapazität einer Kante erreicht ist; Und was dann? Soll ich mir einen neuen Pfad auswählen? Und wie entscheide ich welcher Pfad mir nun den maximalen Fluß bringt; Ist das die Verbindung vom Algorithmus zum minimalen Schnitt? Und was geschieht eigentlich mit dem Residualgraphen während ich diese "Augmentierungen(?)" durchführe? Fragen über Fragen ...
Jedenfalls wäre es schön, wenn mir jemand diesen Algorithmus nochmal mit eigenen Worten deuten könnte.
Vielen Dank!
Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:37 Do 15.09.2005 | | Autor: | Frank05 |
> Ich sitze nun mittlerweile schon einige Tage an diesem
> Algorithmus und komme nicht voran.
Ja der ist huebsch nicht wahr? Hat man auf jeden Fall gut was zum dran rumkauen 
> Es ist mir auch schwierig eine konkrete Frage dazu zu
> stellen, weil ich ab folgendem Punkt die Theorie nicht mehr
> nachvollziehen kann:
>
> Zitat aus dem Skript:
>
>
> [..] Ein [mm]f[/mm]-augmentierender Pfad [mm]P[/mm] eines Netzwerks
> [mm]\left(G,c,s,t\right)[/mm] bzgl. eines Flusses [mm]f[/mm] ist ein
> [mm]s-t-\text{Pfad}[/mm] in dem Residualgraphen [mm]G_f[/mm]. Wir sagen [mm]f[/mm]
> wird durch [mm]P[/mm] um [mm]\gamma \in \IR_{+}[/mm] augmentiert, falls für
> jede Kante [mm]e'[/mm] von [mm]P[/mm] folgende Operation ausgeführt wird: Ist
> [mm]e' \in E[/mm], so wird [mm]f\left(e\right)[/mm] um [mm]\gamma[/mm] erhöht. Ist
> dagegen [mm]e' = \overleftarrow{e}[/mm] für ein [mm]e \in E[/mm], so wird
> [mm]f\left(e\right)[/mm] um [mm]\gamma[/mm] erniedrigt. [..]
>
>
> Später dann, steht im Skript folgender Algorithmus:
>
>
> [mm]
\paragraph{FordFulkerson$\left(G = \left(V, E\right),c,s,t\right)$:}
\mbox{}\par\nobreak\vspace{-\parskip}\nobreak\noindent
\begin{tabular}{ll}
1.) & for all $e \in E$ do $f\left(e\right) = 0$; \\
2.) & Konstruiere einen $f$-augmentierenden Pfad $P$. Falls es einen Solchen nicht gibt, so gib $f$ aus und \textbf{Stop!} \\
3.) & Setze $\gamma := \min_{e}c_{f}\left(e\right)$, wobei $e$ die Kanten von $P$ durchläuft. \\
4.) & Augmentiere $f$ durch $P$ um $\gamma$. \\
5.) & goto step 2.
\end{tabular}
[/mm]
>
Soweit so gut..
> Ich habe unter Anderem versucht das Ganze am folgenden
> Netzwerk nachzuvollziehen:
>
>
> [Dateianhang nicht öffentlich]
>
>
> Wenn ich's richtig verstehe, müßte der Residualgraph dafür
> genauso aussehen, weil hier (noch) nichts fließt, oder?
Fast richtig ausser, dass im Res.graph eine Kante eigentlich keine solche Doppelmarkierung hat. Du haettest dann nur die Markierungen != 0 dort (also auf jeder Kante noch die ganze Kapazitaet frei) und falls du es so willst (Def.sache) Rueckkanten mit Markierung 0.
> Wenn das stimmt, habe ich Punkt 1 des Algorithmus bereits
> erfüllt.
richtig.. klappt ja schon richtig gut 
> Bei Punkt 2 bin ich mir nicht sicher. Kann ich mir
> einen beliebigen Pfad aussuchen?
Ein Hoch auf die Logik: Steht da was von einem bestimmten Pfad? Nein? Na dann tuts jeder Pfad, der die Bedingungen erfuellt.
> Was spräche z.B. gegen den
> Pfad [mm]s \to v_1 \to v_2 \to v_5 \to t[/mm]?
Dass er dem 13ten Betrachter nicht gefaellt.. wie gesagt: jeder gueltige Pfad tuts.
> So und jetzt setze
> ich z.B. [mm]\gamma := 1[/mm].
Du setzt es besser so wie Schritt 3 des Algorithmus es vorgibt. Sonst wirds arg ineffizient (Quizfrage: Warum bleibt der Worst-Case trotzdem gleich?)
Also [mm]\gamma = min.... = 9[/mm].
> Danach starte ich bei [mm]s[/mm], gehe den
> Pfad entlang und erhöhe bei jeder Kante den Fluß um 1,
> soweit richtig?
Du erhoehst um [mm]\gamma[/mm] bzw. erniedrigst. Je nachdem ob du die Kante in der Richtung durchlaeufst wie sie im Graph existiert, oder in der umgekehrten Richtung (was im Residualgraphen ja auch ein moeglicher Pfad sein kann). Sprich du machst das, was in deinem Skript-Zitat die letzten beiden Saetze besagen.
> Und was passiert, wenn ich bei [mm]t[/mm] angekommen
> bin?
Dann hast du Schritt 4 geschafft, klopfst dir auf die Schulter und machst bei Schritt 5 weiter. Dann freust du dich gleich nochmal weils so schnell vorwaerts geht und du machst wieder bei 2 weiter mit dem naechsten Pfad.. bis es eben keinen mehr gibt weil der Fluss schon maximal ist.
> Bisher nehme ich an, daß ich dann wieder bei [mm]s[/mm] starte,
> und das Ganze solange wiederhole bis die maximale Kapazität
> einer Kante erreicht ist; Und was dann?
Nicht nur einer Kante.. das erreichst du mit jedem Pfad, weil du [mm]\gamma[/mm] gerade so waehlst, dass du die Engstelle in dem Pfad zur Gaenze auffuellst.
> Soll ich mir einen
> neuen Pfad auswählen?
Ganz genau.
> Und wie entscheide ich welcher Pfad
> mir nun den maximalen Fluß bringt;
Vorsicht: Fluss != Pfad
Der 'Fluss' ist erstmal fuer jedes Paar von Knoten definiert als der Wert, mit dem die inzidente Kante markiert ist. Der Fluss auf dem ganzen Graphen, an dem du interessiert bist, ist aber alles, was du von s nach t schleussen kannst. Da aber bei diesem Algorithmus die folgende Invariante gilt erhaeltst du den Fluss einfach durch Addition aller Kantenmarkierungen der Kanten die von s ausgehen (oder auch derer die in t enden): [mm]\forall v \in V-\{s,t\}: c_{in}(v) = c_{out}(v)[/mm], d.h. was in einen Knoten reinfliesst fliesst auch vollstaendig wieder raus. Ausser eben bei s und t, wobei es da auch die Variante gibt einfach eine fiktive Kante von t nach s hinzuzufuegen. Dann ist der maximale Fluss direkt auf dieser Kante ablesbar.
(Hier ist noch ein bisschen Vorsicht geboten, was bei euch jetzt genau unter dem Wort 'Fluss' definiert ist. Es kann die finale Markierung der Kanten sein, oder auch die maximale Menge die durch das Netz transportiert werden kann.. oder beides.. oder eben gerade immer so wie mans braucht )
Wie du diesen maximalen Fluss dann tatsaechlich durch den Graphen bekommst liefert dir der Algorithmus ja konstruktiv. Jede Kante ist mit der entsprechenden Menge markiert wenn du fertig bist.
> Und was geschieht
> eigentlich mit dem Residualgraphen während ich diese
> "Augmentierungen(?)" durchführe?
Das Augmentieren bezieht sich eigentlich auf den normalen Kapazitaetsgraphen. Der Residualgraph zeigt dir durch seine beiden Kanten im Prinzip nur an wieviel noch frei ist (in der Richtung der urspruenglichen Kante) und wieviel schon ueber die Kante geleitet wurde (in der Gegenrichtung). Wenn du direkt auf dem Res.graph augmentierst musst du beide Kanten entsprechend anpassen. Die Alternative ist einfach auf dem Kapazitaetsgraphen zu augmentieren und den Res.graph dann neu bilden. Die Kante bekommt dann in ihrer richtigen Richtung (Kapazitaet - Auslastung) und in der Gegenrichtung (Auslastung) als Markierung.
> Jedenfalls wäre es schön, wenn mir jemand diesen
> Algorithmus nochmal mit eigenen Worten deuten könnte.
Eine gute Beschreibung des F.-F. Algorithmus findest du sonst auch in Cormen, et.al. Insbesondere der Unterschied zw. deinem gegebenen Kapazitaetsgraph und dem Res.graph wird dort gut veranschaulicht.
> Vielen Dank!
hth
|
|
|
| |
|
Hallo Frank!
Tut mir leid, daß ich dir nicht schon früher geantwortet habe, aber ich habe mich in der Zwischenzeit noch mit anderen Algorithmen rumgeschlagen. Den Ford-Fulkerson habe ich heute morgen erst versucht:
[Dateianhang nicht öffentlich]
[Dateianhang nicht öffentlich]
Nur was ich hierbei nicht verstehe, ist, wie ich weiter vorgehen soll, wenn sich Pfade im Ausgangsnetzwerk überschneiden? Und der Residualgraph scheint mir eher eine Last als eine Nützlichkeit zu sein. Im Grunde genommen muß ich bei jedem Schritt doppelte Arbeit leisten, indem ich den Graphen nochmal abzeichnen muß, und wozu? Na ja, aber vielleicht bin ich ja schon auf dem richtigen Weg ... ähh Pfad ?
Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
Anhang Nr. 2 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:22 So 18.09.2005 | | Autor: | bazzzty |
Da scheint mir, hast Du die Definition des Residualgraphen noch nicht ganz verstanden. Ich skizziere mal die wichtigen Punkte:
* Du hast ein Netzwerk und einen zulässigen Fluß (den Du erhöhen möchtest.
* Der Residualgraph enthält für jede Kante des Netzwerkes eine oder zwei Kanten, nämlich eine gleich gerichtete Kante, wenn der aktuelle Fluß die Kante noch nicht auslastet (markiert mit der noch möglichen Erhöhung, in deinem Beispiel: für [mm]v_5\to t[/mm] enthält der Residualgraph die Kante [mm]v_5\to t[/mm] mit der Markierung 15!), und eine gegensätzlich gerichtete Kante, wenn die Kante Fluß transportiert (den man ja wieder verringern könnte) (markiert mit dem aktuellen Fluß, im Beispiel wird also im Residualgraphen auch [mm] t\to v_5[/mm] mit der Markierung 9 eingefügt).
Die Idee: Man kann 'Fluß' von [mm]t[/mm] nach [mm]v_5[/mm] fließen lassen, indem man den bestehenden verringert.
Ist eine Kante an der Kapazitätsgrenze, trägt sie nur eine Rückkante bei (die Kante [mm]v_1\to v_2[/mm] wird nur als [mm]v_2\to v_1[/mm] mit der Markierung 9 in den Residualgraphen eingetragen), hat eine Kante noch keinen Fluß, trägt sie nur eine Vorwärtskante bei.
Die Idee hinter dem ganzen:
Auf Kanten, die noch eine Erhöhung zulassen, ist es noch möglich, weiteren Fluß zu transportieren. Kanten, die eine Erniedrigung zulassen, ist es quasi möglich 'Fluß' auf einem entgegengerichteten Pfad zu erhöhen. Man muß so im Residualgraphen nur nach einem beliebigen Pfad suchen, der von s nach t geht, um einen augmentierenden Pfad zu finden.
> Nur was ich hierbei nicht verstehe, ist, wie ich weiter
> vorgehen soll, wenn sich Pfade im Ausgangsnetzwerk
> überschneiden?
Jeder Erhöhungsschritt ist von den vorhergehenden unabhängig. Nach jedem Schritt ist der Fluß wieder zulässig.
> Und der Residualgraph scheint mir eher eine
> Last als eine Nützlichkeit zu sein.
Wenn man ihn richtig aufstellt nicht, siehe oben.
> Im Grunde genommen muß
> ich bei jedem Schritt doppelte Arbeit leisten, indem ich
> den Graphen nochmal abzeichnen muß, und wozu? Na ja, aber
> vielleicht bin ich ja schon auf dem richtigen Weg ... ähh
> Pfad ?
Bleib dran, ist ein schöner Algo.
|
|
|
|
