Ford-Fulkerson-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Ford-Fulkerson - algoritmi ratkaisee ongelman löytää maksimivirtaus liikenneverkossa .

Algoritmin idea on seuraava. Virtausarvoksi asetetaan aluksi 0: kaikille . Virtauksen määrää lisätään sitten iteratiivisesti etsimällä lisäyspolkua (polku lähteestä nieluun, jota pitkin voidaan lähettää lisää virtausta). Prosessi toistetaan, kunnes lisäyspolku löytyy. $f(u,v)=0$ $u,v\in V$ $s$ $t$

Algoritmi

Epävirallinen kuvaus

Nollaamme kaikki streamit. Jäljellä oleva verkko on aluksi sama kuin alkuperäinen verkko.
Jäännösverkosta löydämme minkä tahansa polun lähteestä nieluon. Jos sellaista polkua ei ole, pysähdymme.
Päästämme löydetyn polun (tätä kutsutaan kasvavaksi poluksi tai kasvavaksi ketjuksi ) läpi suurimman mahdollisen virtauksen:
1. Jäännösverkon löydetyltä polulta etsimme reunaa, jonka kapasiteetti on minimi . $c_{\min }$
2. Jokaiselle löydetyn polun reunalle lisäämme virtausta :lla ja vastakkaiseen suuntaan vähennämme sitä . $c_{\min }$ $c_{\min }$
3. Muokkaamme jäännösverkkoa. Laskemme uuden kapasiteetin kaikille löydetyn polun reunoille sekä niitä vastakkaisille (vastasuuntaisille) reunoille. Jos siitä tulee nollasta poikkeava, lisäämme jäännösverkkoon reunan, ja jos siitä tulee nolla, poistamme sen.
Palaamme vaiheeseen 2.

On tärkeää, että algoritmi ei määritä tarkasti, mitä polkua etsimme vaiheessa 2 tai miten teemme sen. Tästä syystä algoritmin on taattu konvergoivan vain kokonaislukukaistanleveydillä, mutta jopa niillä suurilla kaistanleveyksillä se voi toimia hyvin pitkään. Jos kapasiteetit ovat todellisia, algoritmi voi toimia loputtomiin konvergoimatta optimaaliseen ratkaisuun (katso esimerkki alla ).

Jos et etsi mitä tahansa polkua, vaan lyhimmän, saat Edmonds-Karp- algoritmin tai Dinits-algoritmin . Nämä algoritmit konvergoivat kaikille todellisille painoille ajallisesti ja vastaavasti. $O(|V||E|^{2})$ $O(|V|^{2}|E|)$

Muodollinen kuvaus

Annettu kaavio kapasiteetilla ja virtauksella reunoille välillä - . On tarpeen löytää suurin virtaus lähteestä pesualtaaseen . Algoritmin jokaisessa vaiheessa pätevät samat ehdot kuin kaikille virroille: $G(V,E)$ $c(u,v)$ $f(u,v)=0$ $u$ $v$ $s$ $t$

$\ 0\leqslant f(u,v)\leqslant c(u,v)$ . Virtaus kohteesta kohteeseen ei ylitä läpijuoksua. $u$ $v$
$\f(u,v)=-f(v,u)$ .
$\ \sum _{v}f(u,v)=0\Pitkävasen oikea nuoli f_{{in}}(u)=f_{{out}}(u)$ kaikille solmuille paitsi ja . Virtaus ei muutu kulkiessaan solmun läpi. $u$ $s$ $t$

Jäljellä oleva verkko on verkko, jossa on kaistanleveys ja jossa ei ole virtaa. $G_{f}(V,E_{f})$ $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$

Tulokaavio kaistanleveydellä , lähteellä ja nielulla Lähtö Maksimivirtaus välillä - $G$ $c$ $s$ $t$
$f$ $s$ $t$

$f(u,v):=0$ kaikille reunoille $(u,v)$
Niin kauan kuin on polku paikasta paikkaan siten , että kaikilla reunoilla : $s$ $s$ $t$ $G_f$ $c_{f}(u,v)>0$ $(u,v)\in p$
1. löytö ${\displaystyle c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\))$
2. Jokaiselle reunalle $(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)$

Polku voidaan löytää esimerkiksi leveyshaulla ( Edmonds-Karp -algoritmi ) tai syvyyshaulla . $G_{f}(V,E_{f})$

Vaikeus

Algoritmi lisää jokaisessa vaiheessa täydentävän polkuvirran olemassa olevaan virtaan. Jos kaikkien reunojen kapasiteetit ovat kokonaislukuja, on helppo osoittaa induktiolla, että kaikkien reunojen läpi kulkevat virrat ovat aina kokonaislukuja. Siksi jokaisessa vaiheessa algoritmi lisää virtausta vähintään yhdellä, joten se konvergoi korkeintaan vaiheissa, missä f on kaavion maksimivirtaus. Jokainen vaihe on mahdollista suorittaa ajassa , missä on graafin reunojen määrä, jolloin algoritmin kokonaisajoaika on rajoitettu . $O(|f|)$ $O(|E|)$ $|E|$ $O(|E|\max |f|)$

Jos ainakin yhden reunan kapasiteetti on irrationaalinen luku, niin algoritmi voi toimia loputtomiin, ilman että se välttämättä konvergoi oikeaan ratkaisuun. Alla on esimerkki.

Esimerkki ei-konvergoivasta algoritmista

Tarkastellaan oikealla näkyvää verkkoa, jossa lähde , nielu , reunakapasiteetit , ja kaikkien muiden reunojen kapasiteetti on yhtä suuri kuin kokonaisluku . Vakio valitaan siten, että . Käytämme polkuja taulukossa esitetystä jäännöskaaviosta ja , ja . $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\))$

Vaihe	Löytyi polku	Lanka lisätty	Jäljellä olevat kapasiteetit
Vaihe	Löytyi polku	Lanka lisätty	$e_{1}$	$e_{2}$	$e_{3}$
0			$r^{0}=1$	$r$	$yksi$
yksi	$\{s,v_{2},v_{3},t\}$	$yksi$	$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$
neljä	$p_{1}$	$r^{2}$	$0$	$r^{3}$	$r^{2}$
5	$p_{3}$	$r^{2}$	$r^{2}$	$r^{3}$	$0$

Huomaa, että vaiheen 1 jälkeen sekä vaiheen 5 jälkeen reunojen jäännöskyvyt , ja niillä on muoto , ja vastaavasti joillekin luonnollisille . Tämä tarkoittaa, että voimme käyttää lisäyspolkuja , , ja äärettömän monta kertaa, ja näiden reunojen jäännöskapasiteetti on aina samassa muodossa. Kokonaisvirtaus vaiheen 5 jälkeen on . Äärettömässä ajassa kokonaisvirtaus konvergoi arvoon , kun taas maksimivirtaus on . Siten algoritmi ei vain toimi loputtomiin, vaan ei edes konvergoi optimaaliseen ratkaisuun. [yksi] $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$

Esimerkki

Seuraava esimerkki näyttää Ford-Fulkerson-algoritmin ensimmäiset vaiheet kuljetusverkossa, jossa on neljä solmua, lähde A ja nielu D. Tämä esimerkki osoittaa pahimman tapauksen. Käytettäessä leveyshakua algoritmi tarvitsee vain 2 vaihetta.

Polku	Kaistanleveys	Tulos
	Alkuperäinen liikenneverkko
$A, B, C, D$	$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))=$ ${\näyttötyyli \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 askeleen jälkeen...
	Kohdeverkko

Katso myös

Ford-Fulkersonin lause

Linkit

Esimerkki ongelman ratkaisemisesta YouTubessa
Algoritmin visualisointityökalu
Maksimivirtauksen haun toteutus Ford-Fulkerson-menetelmällä Javassa
Wikimedia Commonsissa on Ford-Fulkerson-algoritmiin liittyvää mediaa

Kirjallisuus

Thomas H. Kormen ym. Algoritmit: rakentaminen ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M. : "Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .

Muistiinpanot

↑ Zwick, Uri. Pienimmät verkot, joissa Ford- Fulkersonin maksimivirtausproseduuri ei välttämättä pääty // Tietojenkäsittelyteoria : päiväkirja. - 1995. - 21. elokuuta ( nide 148 , nro 1 ). - s. 165-170 . - doi : 10.1016/0304-3975(95)00022-O .