Ford-Fulkersonův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 29. dubna 2022; kontroly vyžadují 3 úpravy .

Algoritmus Ford-Fulkerson řeší problém nalezení maximálního toku v dopravní síti .

Myšlenka algoritmu je následující. Hodnota průtoku je zpočátku nastavena na 0: pro všechny . Množství toku se pak iterativně zvyšuje hledáním rozšiřující cesty (cesta od zdroje k jímce, po které lze vysílat více toku). Proces se opakuje, dokud není nalezena rozšiřující cesta. $f(u,v)=0$ $u,v\in V$ $s$ $t$

Algoritmus

Neformální popis

Obnovili jsme všechny streamy. Zbytková síť se zpočátku shoduje s původní sítí.
Ve zbytkové síti najdeme libovolnou cestu od zdroje k jímce. Pokud taková cesta není, zastavíme se.
Necháme přes nalezenou cestu (říká se tomu rostoucí cesta nebo rostoucí řetězec ) maximální možný tok:
1. Na nalezené cestě ve zbytkové síti hledáme hranu s minimální kapacitou . $c_{\min }$
2. Pro každou hranu na nalezené cestě průtok zvýšíme o , v opačném směru snížíme o . $c_{\min }$ $c_{\min }$
3. Upravujeme zbytkovou síť. Pro všechny hrany na nalezené cestě a také pro hrany k nim protilehlé (antiparalelní) vypočítáme novou kapacitu. Pokud bude nenulová, přidáme do zbytkové sítě hranu, a pokud bude nulová, vymažeme ji.
Vrátíme se ke kroku 2.

Je důležité, aby algoritmus přesně neurčoval, jakou cestu hledáme v kroku 2 nebo jak to děláme. Z tohoto důvodu je zaručeno, že algoritmus bude konvergovat pouze pro celočíselné šířky pásma, ale i pro ně, pro velké šířky pásma, může běžet velmi dlouho. Pokud jsou kapacity reálné, algoritmus může běžet neomezeně dlouho, aniž by došlo k konvergování k optimálnímu řešení (viz příklad níže ).

Pokud nehledáte žádnou cestu, ale tu nejkratší, dostanete Edmonds- Karpův algoritmus nebo Dinitsův algoritmus . Tyto algoritmy konvergují pro jakékoli reálné váhy v čase , resp. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Formální popis

Daný graf s kapacitou a tokem pro hrany od do . Je potřeba najít maximální průtok ze zdroje do dřezu . V každém kroku algoritmu platí stejné podmínky jako pro všechny toky: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ $u$ $v$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . Průtok od do nepřekračuje propustnost. $u$ $proti$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Dlouhá šipka doleva f_{{in}}(u)=f_{{out}}(u)$ pro všechny uzly kromě a . Průtok se při průchodu uzlem nemění. $u$ $s$ $t$

Zbytková síť je síť s šířkou pásma a bez toku. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Vstupní graf se šířkou pásma , zdrojem a jímkou Výstup Maximální průtok od do $G$ $C$ $s$ $t$
$F$ $s$ $t$

$f(u,v):=0$ pro všechny hrany $(u,v)$
Pokud existuje cesta od do do taková, že pro všechny hrany : $p$ $s$ $t$ $G_f$ $c_{f}(u,v)>0$ $(u,v)\v p$
1. Nalézt ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\))$
2. Pro každou hranu $(u,v)\v 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)$

Cestu lze najít například prohledáváním do šířky ( algoritmus Edmonds-Karp ) nebo prohledáváním do hloubky v . $G_{f}(V,E_{f})$

Obtížnost

V každém kroku algoritmus přidá proud rozšiřující cesty k existujícímu proudu. Pokud jsou kapacity všech hran celá čísla, lze snadno indukcí dokázat, že toky přes všechny hrany budou vždy celá čísla. Proto v každém kroku algoritmus zvýší tok alespoň o jeden, takže bude konvergovat ve většině kroků, kde f je maximální tok v grafu. Každý krok je možné dokončit v čase , kde je počet hran v grafu, pak je celková doba běhu algoritmu omezena . $O(|f|)$ $O(|E|)$ $|E|$ $O(|E|\max |f|)$

Pokud je kapacita alespoň jedné z hran iracionální číslo, pak může algoritmus běžet neomezeně dlouho, aniž by dokonce nutně konvergoval ke správnému řešení. Příklad je uveden níže.

Příklad nekonvergujícího algoritmu

Uvažujme síť zobrazenou vpravo se zdrojem , sink , hranami , , a kapacitou všech ostatních hran rovnou celému číslu . Konstanta je zvolena tak, že . Použijeme cesty ze zbytkového grafu uvedené v tabulce a , a . $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\))$

Krok	Nalezená cesta	Přidáno vlákno	Zbytkové kapacity
Krok	Nalezená cesta	Přidáno vlákno	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$jeden$
jeden	$\{s,v_{2},v_{3},t\}$	$jeden$	$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$
čtyři	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Všimněte si, že po kroku 1, stejně jako po kroku 5, zbytkové schopnosti hran , a mají tvar , respektive , pro některé přirozené . To znamená, že můžeme použít rozšiřující cesty , , a nekonečně mnohokrát a zbytková kapacita těchto hran bude vždy ve stejném tvaru. Celkový průtok po kroku 5 je . V nekonečném čase bude celkový průtok konvergovat k , zatímco maximální průtok je . Algoritmus tedy nejen běží donekonečna, ale ani nekonverguje k optimálnímu řešení. [jeden] $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říklad

Následující příklad ukazuje první kroky Ford-Fulkersonova algoritmu v transportní síti se čtyřmi uzly, zdrojem A a jímkou D . Tento příklad ukazuje nejhorší případ. Při použití prohledávání do šířky potřebuje algoritmus pouze 2 kroky.

Cesta	Šířka pásma	Výsledek
	Počáteční dopravní síť
$ABECEDA$	$\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$
	Po krocích 1998...
	Cílová síť

Viz také

Fordova-Fulkersonova věta

Odkazy

Příklad řešení problému na YouTube
Vizualizér algoritmů
Implementace hledání maximálního průtoku Ford-Fulkersonovou metodou v Javě
Wikimedia Commons má média související s Ford-Fulkerson Algorithm

Literatura

Thomas H. Kormen aj. Algoritmy: konstrukce a analýza = ÚVOD DO ALGORITHMŮ. - 2. vyd. - M. : "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Poznámky

↑ Zwick, Uri. Nejmenší sítě, na kterých se Ford-Fulkersonova procedura maximálního toku nemusí podařit ukončit // Teoretická informatika : deník. - 1995. - 21. srpna ( roč. 148 , č. 1 ). - S. 165-170 . - doi : 10.1016/0304-3975(95)00022-O .