Ford-Fulkersonův algoritmus
Z Wikipedie, otevřené encyklopedie
Tento článek potřebuje úpravy. Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisuje stránka Vzhled a styl, konkrétní problémy tohoto článku mohou být specifikovány na diskusní stránce.
Obsah |
[editovat] Základní informace
Fordův-Fulkersonův algoritmus (pojmenovaný podle L. R. Forda, Jr. a D. R. Fulkersona) počítá maximální tok v síti. Název Ford-Fulkerson je také často používán pro Edmonds-Karpův algoritmus, který je specializací Ford-Fulkersonova algoritmu.
Myšlenka algoritmu je velmi jednoduchá: Dokud existuje cesta od zdroje (výchozí bod) do spotřebiče (koncový bod), taková, že jestliže je možnost ještě zvětšit její tok, neboli, že nějaká hrana, která muže ještě "propustit" vyšší tok a není ještě ve stavu saturace. Poté najdeme další takovou cestu, a tak dále. Cesta s volnou kapacitou se nazývá zlepšující cesta.
[editovat] Obrazek zobrazující postup algoritmu
[editovat] Obecná teorie k algoritmu
Velikost toku nikdy nepřekročí kapacitu (žádného) řezu sítě. Toto tvrzení pouze naznačuje, že sítí není možno "protlačit" vyšší tok než je maximální kapacita řezu sítě (toto je zkované v upozornění, že se to týká všech řezů sítě, tzn i minimálního s jeho "maximální" kapacitou.
Tok f je maximálním tokem v síti S=<G, q, s, t> je ekvivalentní s tvrzením že neexistuje (neorientovaná) cesta (tzv. zlepšující cesta P) v grafu.
P=<u0,u1,...,un>, u0=s, un=t taková, že platí: f[ui, ui+1] < q[ui, ui+1]
pro hrany [ui, ui+1] náležící H [s -> t] f[ui+1, ui] > 0
pro hrany [ui+1, ui] náležící H [s <- t]
Zlepšující cesta je zde vyjádřená jako posloupnost uzlů, kde "první" uzel u0 je zdrojem a "poslední" uzel un je spotřebičem.
[editovat] Obecná implementace v pseudokodu
Ford-Fulkerson (S) for ( Edge (u,v) in H(G) ) f(u,v) = 0; while ( NajdiCestu(S) ) ZvyšTok(S); return f;
[editovat] Obecný popis implementace metod
boolean NajdiCestu(Node s) {
1 for ( Node u in U(G) ) stav[u]=FRESH;
2 p[s] = +s; d[s] = nekonečno; stav[s] = OPEN;
3 do { u = "libovolný otevřený uzel";
4 stav[u] = CLOSED;
5 for (Node v in Nasl(u)) {
6 if ((stav[v]==FRESH) && (f(u,v)<q(u,v))) {
7 stav[v]=OPEN;p[v]=+u;d[v]=min(d[u],q(u,v)-f(u,v));
8 } }
9 for (Node v in předch(u)) {
10 if (stav[v]==FRESH) && (f(v,u)>0)) {
11 stav[v]=OPEN; p[v]=-u; d[v]=min(d[u],f(v,u));
12 } }
13 }while(( "neexistuje otevřený uzel" ) || (u == t));
14 return (u == t);
15 }
void ZvyšTok(Node s) {
1 x = t; delta= d[t];
2 do { v = x; sgn = p[v]; u = abs(sgn);
3 if (sgn>0) f(u,v) += delta;
4 else f(v,u) -= delta;
5 x = u;
6 } while ( v==s );
7 }
[editovat] Vysvětlení algoritmu
Tento algoritmus začíná tak, že všem hranám přiřadí tok hodnoty nula, neboli nic sítí na počátku neprotéká. Dále pak začne testovat nalezení zlepšující cesty, jestliže tato cesta bude nalezena tak se tok zvýší. Naopak jestliže cesta nalezená už nebude, to znamená že zlepšující cesta už neexistuje (viz. obecná teorie k algoritmu) je nalezen maximální tok.
Funkce NajdiCestu(S) na počátku své implementace přiřadí všem uzlům grafu jako stav uzlu hodnotu FRESH. To znamená, že tyto uzly jsou čisté neboli ještě nepoužité. Uzlu S se přiřadí p[s] směr kterým jde hrana a poté ještě delta s jako nekonečno jelikož je to uzel predaný parametrem a tento uzel se otevře. Poté startuje cyklus který na svém začátku vybere uzel který je otevřený (stav uzlu == otevřeno ) a uzavře ho a poté pro všechny jeho následníky zjistí že jestliže je následník, uzel fresh a jeho tok je nižsí než kapacita hrany jež spojuje uzel s tímto následníkem, tak ho otevře, přiřadí mu směr kterým je orientovaná hrana a vypočte pro něj delta. Delta se vypočítává právě pro to aby bylo možné zjistit o kolik se dá navýšit tok v hranách orientovaných směrem od zdroje k spotřebiči a snížit tok na hraně směřující od spotřebiče ke zdroji (bilance zůstává stejná). Když se takto projedou všechny následovníci tak se začnou procházet všichni předchůdci tohoto uzlu. U nich se zjištuje jestliže jsou FRESH a jestliže hrana spojující tyto dva uzly má vyšší tok než nula. Když je tato podmínka splněna nastaví se předchůdce na stav OPEN nastaví se mu orientace hrany a určí delta. A toto celé se opakuje dokud existuje alespoň nějaký otevřený uzel či dokud testovaný uzel u se nebude rovnat spotřebiči. A také na základě této naposledy zmiňované rovnosti bude funkce vracet návratovou hodnotu true nebo false.
Odpoveď na otázku jak je možné, že tok může "téci" i proti směru orientace hrany v síti?
Vysvětleme si to například na vodovodním potrubí. Existuje jedna trubka, která bude mít orientaci proti směru vodovodu to znamená od domácnosti do vodárny. Jak je možné, ze by touto trubkou tekla voda proti její orientaci? Fyzicky to možné není, ale hodnota jejího toku tomu může ukazovat. Tuto hodnotu trubka má jen proto, že jestliže mi potřebujeme touto opačně orientovanou trubkou poslat například 3 litry směrem vodárna-> domácnost, tak jestliže například 10 litru vody jí proteče ve směru domácnost->vodárna, tak ona svůj průtok zmenši třeba na 7 litrů a ty tři litry nechá protéct někde jinde..jinou trubkou..tím pádem navenek vypadá, že průtok směrem vodárna-> domácnost je 3.
[editovat] Pro zadání s určeným minimálním tokem
Ford-Fulkersonův algoritmus při startu svého běhu ohodnotí všechny hrany nulovým tokem. Tento předpoklad, ale nekoresponduje s naším zadáním (určeným minimálním tokem) a proto je nutné si síť upravit abychom mohli FF algoritmu naplno využít. Z tohoto důvodu musíme do sítě přidat některé fiktivní části sítě, abychom jakoby "nasimulovali" situaci, abychom mohli tento Ford-Fulkersonův algoritmus už správně použít. Fiktivními součástmi budou fiktivní zdroj a fiktivní spotřebič. Vytvoříme hrany (A) mezi fiktivním zdrojem a uzly do kterých směřují hrany (B) orientované směrem od uzlu S (zdroje) k uzlu t (spotřebiči). Tyto hrany (A) ohodnotíme stejnou hodnotou, jež mají hodnoty minimálního toku v hranách (B). Orientujeme je směrem od fiktivního zdroje k uzlům d kterých směřují hrany (B). Mezi fiktivním spotřebičem a uzly z kterých vychází hrany (B) vytvoříme taktéž hrany (C) a ohodnotíme je také stejně jako jsou ohodnocení minimálních toků v hranách (B). Orientujeme je směrem ke spotřebiči. Posledním co vytvoříme je hrana která bude spojovat skutečný spotřebič a skutečný zdroj s orientací od spotřebiče ke zdroji. Nyní už použijeme Ford-Fulkersonův algoritmus. Nalezneme maximální tok mezi fiktivním zdrojem a fiktivním spotřebičem. A nyní jestliže námi vytvořené hrany mezi fiktivními součástmi grafu (fik. zdroj,spotřebič) budou po průchodu v saturaci (dosáhnou ohodnocení/toku rovnajícímu se kapacity hrany) to znamená, že máme přípustný tok můžeme pokračovat v jeho "zlepšování". Hodnoty ale nesmí klesnout pod minima v hranách kde by se tak mohlo stát. V opačném případě jestliže hrany nebudou saturovat tak vyjde že úloha nemá řešení.
[editovat] Implementace
- Implementace Java: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/Maxflow.shtml
[editovat] Složitost
Složitost metody NajdiCestu : O(|U|+|H|) Složitost metody ZvyšTok : O(|U|) Složitost celého algoritmu : O(|U|*|H|^2) , O(|U|^2*|H|) nebo O(|U|^3).
[editovat] Související články
[editovat] Externí odkazy
- Toky v sítích: http://ksvi.mff.cuni.cz/~dvorak/vyuka/UIN009/Toky.pdf
- Moderní algoritmy pro hledání maximálního toku v síti: http://www.fs.vsb.cz/akce/2001/asr2001/Proceedings/papers/55.pdf
- Jakub Černý: Základní grafové algoritmy (texty v pdf)
- Interaktivní demonstrace: Interaktivní demonstrace
