Ford-Fulkerson algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 29. april 2022; checks kræver 3 redigeringer .

Ford-Fulkerson-algoritmen løser problemet med at finde det maksimale flow i et transportnetværk .

Ideen med algoritmen er som følger. Flowværdien er oprindeligt sat til 0: for alle . Mængden af flow øges derefter iterativt ved at søge efter en forstærkende sti (en sti fra kilde til synk , langs hvilken mere flow kan sendes). Processen gentages, indtil der kan findes en forøgelsessti. $f(u,v)=0$ $u,v\in V$ $s$ $t$

Algoritme

Uformel beskrivelse

Vi nulstiller alle streams. Det resterende netværk falder i første omgang sammen med det oprindelige netværk.
I restnettet finder vi enhver vej fra kilden til vasken. Hvis der ikke er en sådan vej, stopper vi.
Vi slipper gennem den fundne vej (det kaldes stigende vej eller stigende kæde ) det maksimalt mulige flow:
1. På den fundne vej i det resterende netværk leder vi efter en kant med minimumskapacitet . $c_{\min }$
2. For hver kant på den fundne sti øger vi flowet med , og i modsat retning mindsker vi det med . $c_{\min }$ $c_{\min }$
3. Vi ændrer det resterende netværk. For alle kanter på den fundne sti, såvel som for kanterne modsat (antiparallelle) til dem, beregner vi den nye kapacitet. Hvis det bliver ikke-nul, tilføjer vi en kant til det resterende netværk, og hvis det bliver nul, sletter vi det.
Vi vender tilbage til trin 2.

Det er vigtigt, at algoritmen ikke præciserer, hvilken vej vi leder efter i trin 2, eller hvordan vi gør det. Af denne grund er algoritmen garanteret kun at konvergere for heltalsbåndbredder, men selv for dem, for store båndbredder, kan den køre i meget lang tid. Hvis kapaciteterne er reelle, kan algoritmen køre i det uendelige uden at konvergere til den optimale løsning (se eksempel nedenfor ).

Hvis du ikke leder efter nogen vej, men efter den korteste, får du Edmonds-Karp- algoritmen eller Dinits-algoritmen . Disse algoritmer konvergerer for eventuelle reelle vægte i tid og hhv. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Formel beskrivelse

Givet en graf med kapacitet og flow for kanter fra til . Det er nødvendigt at finde det maksimale flow fra kilden til vasken . Ved hvert trin i algoritmen gælder de samme betingelser som for alle flows: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ $u$ $v$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . Strømmen fra til overstiger ikke gennemløbet. $u$ $v$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Longleftrightarrow f_{{in}}(u)=f_{{out}}(u)$ for alle noder undtagen og . Strømmen ændres ikke, når den passerer gennem knudepunktet. $u$ $s$ $t$

Det resterende netværk er et netværk med båndbredde og uden flow. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Input Graph med båndbredde , source og sink Output Maksimalt flow fra til $G$ $c$ $s$ $t$
$f$ $s$ $t$

$f(u,v):=0$ til alle kanter $(u,v)$
Så længe der er en vej fra til til sådan, at for alle kanter : $s$ $s$ $t$ $G_f$ $c_{f}(u,v)>0$ $(u,v)\i s$
1. Finde ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\i p\))$
2. For hver kant $(u,v)\i s$
  1. $f(u,v):=f(u,v)+c_{f}(p)$
  2. $f(v,u):=f(v,u)-c_{f}(p)$
  3. $c_{f}(u,v)=c(u,v)-f(u,v)$
  4. $c_{f}(v,u)=f(u,v)$

Stien kan for eksempel findes ved bredde-først søgning ( Edmonds-Karp algoritme ) eller dybde-først søgning i . $G_{f}(V,E_{f})$

Sværhedsgrad

Ved hvert trin tilføjer algoritmen en forstærkende stistrøm til den eksisterende strøm. Hvis kapaciteten af alle kanter er heltal, er det let at bevise ved induktion, at strømmene gennem alle kanter altid vil være heltal. Derfor øger algoritmen ved hvert trin flowet med mindst ét, så det vil konvergere i højst trin, hvor f er det maksimale flow i grafen. Det er muligt at gennemføre hvert trin i tid , hvor er antallet af kanter i grafen, så er den samlede køretid for algoritmen begrænset . $O(|f|)$ $O(|E|)$ $|E|$ $O(|E|\max |f|)$

Hvis kapaciteten af mindst en af kanterne er et irrationelt tal, så kan algoritmen køre på ubestemt tid, uden engang nødvendigvis at konvergere til den korrekte løsning. Et eksempel er givet nedenfor.

Et eksempel på en ikke-konvergerende algoritme

Overvej netværket vist til højre med source , sink , edge capacities , , og kapaciteten af alle andre kanter lig med et heltal . Konstanten vælges således, at . Vi bruger stierne fra restgrafen i tabellen, og , og . $s$ $t$ $e_{1}=1$ $e_{2}=r=({\sqrt {5}}-1)/2$ $e_{3}=1$ $M\geq 2$ $r$ $r^{2}=1-r$ ${\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\))$ ${\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\))$ ${\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\))$

Trin	Fundet sti	Tilføjet tråd	Resterende kapaciteter
Trin	Fundet sti	Tilføjet tråd	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$en$
en	$\{s,v_{2},v_{3},t\}$	$en$	$r^{0}$	$r^{1}$	$0$
2	$p_{1}$	$r^{1}$	$r^{2}$	$0$	$r^{1}$
3	$p_{2}$	$r^{1}$	$r^{2}$	$r^{1}$	$0$
fire	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Bemærk, at efter trin 1, såvel som efter trin 5, de resterende evner af kanterne , og har formen , og , henholdsvis for nogle naturlige . Det betyder, at vi kan bruge augmenting paths , , og uendeligt mange gange, og restkapaciteten af disse kanter vil altid være i samme form. Det samlede flow efter trin 5 er . I uendelig tid vil det samlede flow konvergere til , mens det maksimale flow er . Algoritmen kører således ikke kun i det uendelige, men konvergerer ikke engang til den optimale løsning. [en] $e_{1}$ $e_{2}$ $e_{3}$ $r^{n}$ $r^{{n+1}}$ $0$ $n$ $p_{1}$ $p_{2}$ $p_{1}$ $p_{3}$ $1+2(r^{1}+r^{2})$ $\textstyle 1+2\sum _{{i=1}}^{\infty }r^{i}=3+2r$ $2M+1$

Eksempel

Følgende eksempel viser de første trin af Ford-Fulkerson-algoritmen i et transportnetværk med fire knudepunkter, kilde A og synk D. Dette eksempel viser det værste tilfælde. Når du bruger bredde-først søgning, behøver algoritmen kun 2 trin.

Sti	Båndbredde	Resultat
	Indledende transportnet
$A,B,C,D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ $\min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))=$ $\min(1000-0,1-0,1000-0)=1$
$A,C,B,D$	$\min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))=$ $\min(c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D))=$ $\min(1000-0,0-(-1),1000-0)=1$
	Efter 1998 trin...
	Destinationsnetværk

Se også

Ford-Fulkerson teorem

Litteratur

Thomas H. Kormen et al. Algoritmer: konstruktion og analyse = INTRODUKTION TIL ALGORITHMER. - 2. udg. - M. : "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Noter

↑ Zwick, Uri. De mindste netværk, hvor Ford-Fulkersons maksimale flow-procedure muligvis ikke afsluttes // Teoretisk datalogi : journal. - 1995. - 21. august ( bind 148 , nr. 1 ). - S. 165-170 . - doi : 10.1016/0304-3975(95)00022-O .