Ford-Fulkerson algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 29-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Ford-Fulkerson algoritmus megoldja a szállítási hálózatban a maximális áramlás megtalálásának problémáját .

Az algoritmus ötlete a következő. Az áramlási érték kezdetben 0: for all . Az áramlás mennyiségét ezután iteratív módon növeljük egy növelő útvonal keresésével (az út a forrástól a nyelőig , amelyen több áramlást lehet továbbítani). A folyamatot addig ismételjük, amíg meg nem találjuk a bővítési útvonalat. $f(u,v)=0$ $u,v\in V$ $s$ $t$

Algoritmus

Informális leírás

Az összes adatfolyamot visszaállítjuk. A maradék hálózat kezdetben egybeesik az eredeti hálózattal.
A maradék hálózatban bármilyen utat megtalálunk a forrástól a nyelőig. Ha nincs ilyen út, megállunk.
A talált úton (ezt növekvő útnak vagy növekvő láncnak nevezik ) átengedjük a lehetséges maximális áramlást:
1. A maradék hálózatban megtalált útvonalon minimális kapacitású élt keresünk . $c_{\min }$
2. A talált út minden élére növeljük az áramlást -vel , ellenkező irányban pedig -kal csökkentjük . $c_{\min }$ $c_{\min }$
3. Módosítjuk a maradék hálózatot. A talált útvonalon lévő összes élre, valamint a velük szemben lévő (antipárhuzamos) élekre kiszámítjuk az új kapacitást. Ha nem nulla lesz, akkor egy élt adunk a maradék hálózathoz, ha pedig nulla lesz, akkor töröljük.
Visszatérünk a 2. lépéshez.

Fontos, hogy az algoritmus ne adja meg pontosan, hogy a 2. lépésben melyik útvonalat keressük, vagy azt hogyan tegyük. Emiatt az algoritmus garantáltan csak egész számú sávszélesség esetén konvergál, de még ezeknél is, nagy sávszélességeknél is nagyon sokáig futhat. Ha a kapacitások valósak, az algoritmus korlátlan ideig futhat anélkül, hogy konvergálna az optimális megoldáshoz (lásd a lenti példát ).

Ha nem bármelyik utat keresed, hanem a legrövidebbet, akkor az Edmonds-Karp algoritmust vagy a Dinits algoritmust kapod . Ezek az algoritmusok konvergálnak bármely valós súlyhoz időben , ill. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Formai leírás

Adott egy gráf kapacitással és áramlással a -tól ig terjedő élekhez . Meg kell találni a maximális áramlást a forrástól a mosogatóig . Az algoritmus minden lépésére ugyanazok a feltételek vonatkoznak, mint az összes folyamra: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ $u$ $v$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . Az áramlás tól ig nem haladja meg az áteresztőképességet. $u$ $v$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Hosszú balra nyíl f_{{in}}(u)=f_{{out}}(u)$ minden csomóponthoz, kivéve és . Az áramlás nem változik, ahogy áthalad a csomóponton. $u$ $s$ $t$

A maradék hálózat sávszélességű és áramlás nélküli hálózat. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Bemeneti grafikon sávszélességgel , forrással és nyelővel Kimenet Maximális áramlás tól ig $G$ $c$ $s$ $t$
$f$ $s$ $t$

$f(u,v):=0$ minden élhez $(u,v)$
Mindaddig, amíg van egy olyan útvonal , amely minden élre vonatkozik : $p$ $s$ $t$ $G_f$ $c_{f}(u,v)>0$ $(u,v)\in p$
1. megtalálja ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\))$
2. Minden élhez $(u,v)\in p$
  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)$

Az útvonalat például szélesség-első kereséssel ( Edmonds-Karp algoritmus ) vagy mélység-első kereséssel lehet megtalálni a -ban . $G_{f}(V,E_{f})$

Nehézség

Az algoritmus minden lépésben hozzáad egy bővítő útvonaladatfolyamot a meglévő adatfolyamhoz. Ha az összes él kapacitása egész szám, akkor indukcióval könnyen igazolható, hogy az összes élen áthaladó áramlás mindig egész szám lesz. Ezért minden lépésben az algoritmus legalább eggyel növeli az áramlást, tehát legfeljebb lépésenként fog konvergálni, ahol f a maximális áramlás a grafikonon. Lehetőség van minden lépés végrehajtására időben , ahol a gráf éleinek száma, ekkor az algoritmus teljes futási ideje korlátozott . $O(|f|)$ $O(|E|)$ $|E|$ $O(|E|\max |f|)$

Ha legalább az egyik él kapacitása irracionális szám, akkor az algoritmus korlátlan ideig futhat anélkül, hogy szükségszerűen konvergálna a helyes megoldáshoz. Az alábbiakban egy példa látható.

Példa egy nem konvergáló algoritmusra

Tekintsük a jobb oldalon látható hálózatot, amelynek forrása , nyelője , élkapacitása , és az összes többi él kapacitása egyenlő egész számmal . Az állandót úgy választjuk meg, hogy . A táblázatban megadott maradék gráf útvonalait használjuk, és , és . $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\))$

Lépés	Talált út	Hozzáadott szál	Maradék kapacitások
Lépés	Talált út	Hozzáadott szál	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$egy$
egy	$\{s,v_{2},v_{3},t\}$	$egy$	$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$
négy	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Vegye figyelembe, hogy az 1. lépés után, valamint az 5. lépés után az élek maradványképességei , és alakja , illetve bizonyos természetes . Ez azt jelenti, hogy , , és végtelenül sokszor használhatjuk, és ezeknek az éleknek a maradék kapacitása mindig azonos formában lesz. A teljes áramlás az 5. lépés után . Végtelen idő alatt a teljes áramlás a -hoz konvergál , míg a maximális áramlás . Így az algoritmus nemcsak korlátlan ideig fut, de még csak nem is konvergál az optimális megoldáshoz. [egy] $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$

Példa

A következő példa a Ford-Fulkerson algoritmus első lépéseit mutatja be egy négy csomóponttal, A forrással és D nyelővel rendelkező közlekedési hálózatban . Ez a példa a legrosszabb esetet mutatja be. Szélesség szerinti keresés esetén az algoritmusnak csak 2 lépésre van szüksége.

Pálya	Sávszélesség	Eredmény
	Kezdeti közlekedési hálózat
$A,B,C,D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ ${\megjelenítési stílus \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$
	1998-as lépések után...
	Célhálózat

Lásd még

Ford-Fulkerson tétel

Linkek

Példa egy probléma megoldására a YouTube -on
Algoritmus megjelenítő
A maximális áramlás keresésének megvalósítása Ford-Fulkerson módszerrel Java nyelven
A Wikimedia Commons rendelkezik a Ford-Fulkerson algoritmushoz kapcsolódó médiával

Irodalom

Thomas H. Kormen et al. Algoritmusok: konstrukció és elemzés = BEVEZETÉS AZ ALGORITMUSOKBA. - 2. kiadás - M. : "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Jegyzetek

↑ Zwick, Uri. A legkisebb hálózatok, amelyeken a Ford-Fulkerson maximális áramlási eljárás nem fejeződik be // Theoretical Computer Science : folyóirat. - 1995. - augusztus 21. ( 148. évf. , 1. sz.). - 165-170 . o . - doi : 10.1016/0304-3975(95)00022-O .