Die Methode von Ford-Fulkerson (genannt für L. R. Ford den Jüngeren. und D. R. Fulkerson) ist ein Algorithmus, der den maximalen Fluss in einem Fluss-Netz schätzt. Es wurde 1954 veröffentlicht. Der Name "Ford-Fulkerson" wird häufig auch für den Algorithmus von Edmonds-Karp verwendet, der eine Spezialisierung von Ford-Fulkerson ist.

Die Idee hinter dem Algorithmus ist sehr einfach. So lange es einen Pfad von der Quelle gibt (fangen Sie Knoten an) zum Becken (Endknoten), mit der verfügbaren Kapazität an allen Rändern im Pfad, senden wir Fluss entlang einem dieser Pfade. Dann finden wir einen anderen Pfad und so weiter. Ein Pfad mit der verfügbaren Kapazität wird einen sich vermehrenden Pfad genannt.

Algorithmus

Lassen Sie, ein Graph, und für jeden Rand zu sein von zu, zu lassen, die Kapazität zu sein und der Fluss zu sein. Wir wollen den maximalen Fluss von der Quelle zum Becken finden. Nach jedem Schritt im Algorithmus wird der folgende aufrechterhalten:

:

Das bedeutet, dass der Fluss das Netz ein gesetzlicher Fluss nach jeder Runde im Algorithmus ist. Wir definieren das restliche Netz, um das Netz mit der Kapazität und keinem Fluss zu sein. Bemerken Sie, dass es geschehen kann, dass einem Fluss von dazu im restlichen erlaubt wird

Netz, obwohl zurückgewiesen, im ursprünglichen Netz: wenn und dann

.

Algorithmus Ford-Fulkerson

:Inputs-Graph mit der Fluss-Kapazität, einem Quellknoten und einem Becken-Knoten

:Output Ein Fluss davon, zu dem ein Maximum ist

:# für alle Ränder

:#, Während es einen Pfad von zu in, solch dass für alle Ränder gibt:

:## finden

:## Für jeden Rand

:### (Senden Fluss entlang dem Pfad)

:### (Könnte der Fluss später "zurückgegeben" werden)

Der Pfad im Schritt 2 kann mit zum Beispiel einer Breitensuche oder einer Tiefensuche darin gefunden werden. Wenn Sie den ersteren verwenden, wird der Algorithmus Edmonds-Karp genannt.

Wenn keine Pfade mehr im Schritt 2 gefunden werden können, wird nicht im Stande sein, im restlichen zu reichen

Netz. Wenn der Satz von Knoten ist, die durch im restlichen Netz, dann der ganze erreichbar

sind

die Kapazität im ursprünglichen Netz von Rändern von zum Rest dessen ist einerseits

gleich dem Gesamtfluss haben wir von zu, gefunden

und andererseits haben Aufschläge als ein oberer für alle diese Flüsse gebunden.

Das beweist, dass der Fluss, den wir gefunden haben, maximal ist. Siehe auch Max-Fluss-Lehrsatz des Minute-geschnittenen.

Kompliziertheit

Durch das Hinzufügen des Fluss-Vergrößern-Pfads zum im Graphen bereits gegründeten Fluss wird der maximale Fluss erreicht, wenn keine Fluss-Vergrößern-Pfade mehr im Graphen gefunden werden können. Jedoch gibt es keine Gewissheit, dass diese Situation jemals erreicht wird, so ist das beste, das versichert werden kann, dass die Antwort richtig sein wird, wenn der Algorithmus endet. Im Fall, den der Algorithmus für immer führt, könnte der Fluss nicht zum maximalen Fluss sogar zusammenlaufen. Jedoch kommt diese Situation nur mit vernunftwidrigen Fluss-Werten vor. Wenn die Kapazitäten ganze Zahlen sind, wird die Durchlaufzeit von Ford-Fulkerson dadurch begrenzt (sieh große O Notation), wo die Zahl von Rändern im Graphen ist und der maximale Fluss im Graphen ist. Das ist, weil jeder sich vermehrende Pfad rechtzeitig gefunden werden kann und den Fluss durch einen Betrag der ganzen Zahl vergrößert, der mindestens ist.

Eine Schwankung des Algorithmus von Ford-Fulkerson mit der versicherten Beendigung und einem Laufzeitunabhängigen des maximalen Fluss-Werts ist der Algorithmus von Edmonds-Karp, der rechtzeitig läuft.

Integriertes Beispiel

Das folgende Beispiel zeigt die ersten Schritte von Ford-Fulkerson in einem Fluss-Netz mit 4 Knoten, Quelle und Becken. Dieses Beispiel zeigt das Grenzfall-Verhalten des Algorithmus. In jedem Schritt wird nur ein Fluss dessen über das Netz gesandt. Wenn erste Suche der Breite statt dessen verwendet würde, wären nur zwei Schritte erforderlich.

Bemerken Sie, wie Fluss zurück" von dazu "gestoßen wird, wenn man den Pfad findet.

Das Nichtbegrenzen des Beispiels

Betrachten Sie das Fluss-Netz als gezeigt rechts, mit der Quelle, dem Becken, den Kapazitäten von Rändern, und beziehungsweise, und und der Kapazität aller anderen Ränder eine ganze Zahl. Die Konstante wurde so, das gewählt. Wir verwenden sich vermehrende Pfade gemäß dem folgenden Tisch, wo, und.

Bemerken Sie, dass nach dem Schritt 1 sowie nach dem Schritt 5, den restlichen Kapazitäten von Rändern, und in der Form, und, beziehungsweise, für einige sind. Das bedeutet, dass wir sich vermehrende Pfade, und ungeheuer oft verwenden können und restliche Kapazitäten dieser Ränder immer in derselben Form sein werden. Der Gesamtfluss im Netz nach dem Schritt 5 ist. Wenn wir fortsetzen, sich vermehrende Pfade als oben zu verwenden, läuft der Gesamtfluss dazu zusammen, während der maximale Fluss ist. In diesem Fall endet der Algorithmus nie, und der Fluss läuft zum maximalen Fluss nicht sogar zusammen.

Pythonschlange-Durchführung

Klassenrand (Gegenstand):

def __ init __ (selbst, u, v, w):

self.source = u

self.sink = v

self.capacity = w

def __ repr __ (selbst):

kehren Sie "%s-> % s zurück: % s" % (self.source, self.sink, self.capacity)

Klasse FlowNetwork (Gegenstand):

def __ init __ (selbst):

self.adj = {}\

self.flow = {}\

def add_vertex (selbst, Scheitelpunkt):

self.adj [Scheitelpunkt] = []

def get_edges (selbst, v):

geben Sie self.adj [v] zurück

def add_edge (selbst, u, v, w=0):

wenn u == v:

erziehen Sie ValueError ("u == v")

Rand = Rand (u, v, w)

redge = Rand (v, u, 0)

edge.redge = redge

redge.redge = Rand

self.adj [u].append (Rand)

self.adj [v].append (redge)

self.flow [Rand] = 0

self.flow [redge] = 0

def find_path (selbst, Quelle, Becken, Pfad):

wenn Quelle == Becken:

geben Sie Pfad zurück

für den Rand in selbst get_edges (Quelle):

restlich = edge.capacity - self.flow [Rand]

wenn restlich> 0 und nicht (Rand, restlich) im Pfad:

resultieren Sie = selbst find_path (edge.sink, Becken, Pfad + [(Rand, restlich)])

wenn Ergebnis! = Niemand:

geben Sie Ergebnis zurück

def max_flow (selbst, Quelle, Becken):

Pfad = selbst find_path (Quelle, Becken, [])

während Pfad! = Niemand:

fließen Sie = Minute (res für den Rand, res im Pfad)

für den Rand, res im Pfad:

self.flow [Rand] + = überfluten

self.flow [edge.redge] - = überfluten

Pfad = selbst find_path (Quelle, Becken, [])

geben Sie Summe (self.flow [Rand] für den Rand in selbst get_edges (Quelle)) zurück

</Quelle>

Gebrauch-Beispiel

Weil das Beispiel Netz im maximalen Fluss-Problem überflutet, tun wir den folgenden:

g=FlowNetwork

Karte (g.add_vertex, ['s', 'o', 'p', 'q', 'r', 't'])

g.add_edge ('s', 'o', 3)

g.add_edge ('s', 'p', 3)

g.add_edge ('o', 'p', 2)

g.add_edge ('o', 'q', 3)

g.add_edge ('p', 'r', 2)

g.add_edge ('r', 't', 3)

g.add_edge ('q', 'r', 4)

g.add_edge ('q', 't', 2)

drucken Sie g.max_flow ('s', 't')

</Quelle>

Produktion: 5

Zeichen

Links

• Ein anderer javanischer Zeichentrickfilm
• Javanische Webanfang-Anwendung