Kurs:Algorithmen und Datenstrukturen/Vorlesung/Flussproblem Ford-Fulkerson

Aus Wikiversity




Ford-Fulkerson[Bearbeiten]

Auf dieser Seite wird der Ford Fulkerson Algorithmus zur Berechnung des maximalen Flusses behandelt.

Berechnung des maximalen Flusses[Bearbeiten]

Der Ford-Fulkerson Algorithmus ist ein effizienter Algorithmus zur Bestimmung eines maximalen Flusses von q nach z. Dabei wird der Greedy Algorithmus mit Zufallsauswahlen gemischt. Hier wird das Prinzip "Füge so lange verfügbare Pfade zum Gesamtfluss hinzu wie möglich" verfolgt. Zuerst soll ein nutzbarere Pfad durch Tiefensuche gefunden werden. Für die Kanten werden dann drei Werte notiert. Zum einen der aktuellen Fluss entlang der Kante. Im initialisierten Graphen ist dieser Wert überall 0. Zudem wird die vorgegebene Kapazität c notiert und die abgeleitete noch verfügbare Restkapazität von c-f.

Algorithmus[Bearbeiten]

initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Ein nutzbarere Pfad ist ein zyklenfreier Pfad von der Quelle q zum Ziel z, der an allen Kanten eine verfügbare Kapazität hat. Ein nutzbarer Fluss ist das Minimum der verfügbaren Kapazitäten der einzelnen Kanten.

Der nachfolgende Pseudocode realisiert das Problem mit zusätzlichen Rückkanten.

für jede Kante(u,v) füge Kante (v,u) mit Kapazität 0 ein;
initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Beispiele[Bearbeiten]

FordFulkerson1
FordFulkerson1

Wir haben einen Graph mit Kapazitäten gegeben





FordFulkerson2
FordFulkerson2

Es wird mit dem Fluss 0 initialisiert. Notation: <aktueller Fluss f> / <Kapazität c> / <verfügbare Kapazität c-f>





FordFulkerson3
FordFulkerson3

Die Auswahl der nutzbaren Pfade geschieht zufällig oder durch geeignete Heuristik. Es gibt auch kürzere Pfade mit höheren Kapazitäten. Die Rückkanten werden mit der Kapazität 0 eingefügt. Die Auswahl eines Pfades geschieht durch Der nutzbare Fluss beträgt 4.



FordFulkerson4
FordFulkerson4


Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : . Der nutzbare Fluss beträgt 5.



Ford fulkerson5
Ford fulkerson5




Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : . Der nutzbare Fluss beträgt 3.


Ford fulkerso6
Ford fulkerso6





Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : . Der nutzbare Fluss beträgt 2.



Ford fulkerson7
Ford fulkerson7





An dieser Stelle sind keine Kapazitäten mehr über und die Berechnung wir beendet. Der maximale Fluss beträgt 14.


Der Algorithmus kann dabei auf verschiedene Ergebnisse kommen, jedoch ist der maximale Fluss immer gleich. Eine weitere Lösung ist folgende:

Zunächst wird der Pfad mit dem nutzbaren Fluss 5 ausgewählt.

Anschließend wird der Fluss aktualisiert. Im nächsten Schritt wird dann der Pfad gewählt. Ebenfalls ist hier wieder ein nutzbarer Fluss von 5.

Nach der zweiten Aktualisierung ist nur noch ein Pfad vom Start zum Ziel möglich. Also wird der Pfad ausgewählt. Dieser Fluss enthält allerdings nur noch einen nutzbaren Fluss von 4.

Nach dem Aktualisieren des Flusses ist es nicht mehr möglich einen Pfad vom Start zum Ziel zu finden. Damit ist die Berechnung beendet. Wie zuvor berechnet ist der maximale Fluss 14.

Problem: Ungünstige Pfadwahl[Bearbeiten]

Die bisher betrachtete Version des Algorithmus ist nicht immer optimal.

Wählen der Pfad ausgewählt, besitzt dieser Pfad einen nutzbaren Fluss von 5.

Nun wird der Fluss aktualisiert. Daraus folgt, dass keine weitere Pfadwahl mehr möglich ist. Dabei wäre die optimale Lösung über die Pfade und .

Das Problem ist, dass der Fluss nicht zurückgenommen werden kann. Die Lösung dazu ist, dass man entgegengesetzte Flussrichtung durch Rückkanten erlaubt. Auch hier wird wieder der ungünstige Pfad mit einem nutzbaren Fluss von 5 im ersten Schritt ausgewählt.

Anschließend wird der Fluss aktualisiert. Dabei wird der Pfad mit dem nutzbaren Fluss von 5 ausgewählt.

Beim erneuten aktualisieren des Flusses, stellt sich heraus, dass keine weiteren Pfade möglich sind. Damit ist die Berechnung, bei einem maximalen Fluss von 10, beendet.

Analyse[Bearbeiten]

Terminierungstheorem[Bearbeiten]

Sind alle Kapazitäten in G nicht-negativ und rational, dann terminiert der Algorithmus von Ford‐Fulkerson nach endlicher Zeit.

Laufzeittheorem[Bearbeiten]

Ist X der Wert eines maximales Flusses in G=(V,E) und sind alle Kapazitäten in G nicht-negativ und ganzzahlig, so hat der Algorithmus von Ford‐Fulkerson eine Laufzeit von O(|E|X). 

Korrektheitstheorem[Bearbeiten]

Sind alle Kapazitäten in G nicht‐negativ und rational, dann berechnet der Algorithmus von Ford‐Fulkerson den Wert eines maximalen Flusses.

Anmerkung[Bearbeiten]

Die Wahl des Pfades beeinflusst die Anzahl benötigter Iteratoren. Bei dem Verfahren von Edmons und Karp muss die Anzahl der Pfade die in einem Graphen G = (V,E) bis  zum Finden des maximalen Flusses verfolgt werden, kleiner sein als |V||E|, wenn jeweils der kürzeste  Pfad von Quelle q zu Ziel z gewählt wird. Daher kann die Auswahl des nächsten kürzesten Pfades basierend auf einer Variante der Breitensuche erfolgen. Dadurch wird die Laufzeit auf verbessert. 



Discussion