Edmonds-Karp-algoritmi

Edmonds-Karp-algoritmi ratkaisee ongelman löytää maksimivirtaus kuljetusverkossa . Algoritmi on Ford-Fulkersonin menetelmän erikoistapaus ja toimii ajassa kaaviossa . Neuvostoliiton tiedemies E. A. Dinitz julkaisi sen ensimmäisen kerran vuonna 1970 . Myöhemmin, vuonna 1972, Edmonds ja Karp löysivät sen itsenäisesti . $O(|V|\cdot |E|^{2})$ $G=(V,E)$

Algoritmi

Edmonds-Karp- algoritmi on muunnos Ford-Fulkerson-algoritmista , jossa jokaisessa vaiheessa valitaan lyhin komplementaarinen polku jäännösverkossa (olettaen, että kullakin reunalla on yksikköpituus). Lyhin polku löytyy leveyshakulla . $s$ $t$

Kuvaus

Nollaamme kaikki streamit. Jäljellä oleva verkko on aluksi sama kuin alkuperäinen verkko.
Jäännösverkosta löydämme lyhimmän 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 reunoille. Jos siitä tulee nollasta poikkeava, lisäämme jäännösverkkoon reunan, ja jos siitä tulee nolla, poistamme sen.
Palaamme vaiheeseen 2.

Löytääksemme kaavion lyhimmän polun käytämme leveys ensin -hakua :

Luomme jonon pisteistä O. Aluksi O koostuu yhdestä pisteestä s .
Merkitsemme kärjet s käydyiksi, ilman vanhempia ja kaikki loput vierailemattomiksi.
Niin kauan kuin jono ei ole tyhjä, suorita seuraavat vaiheet:
1. Poista ensimmäinen kärki jonosta u .
2. Suorita seuraavat vaiheet kaikille kaarille ( u , v ), jotka lähtevät kärjestä u ja joiden kärjessä v ei ole vielä käynyt:
  1. Merkitsemme vertexin v :n käydyksi, jossa on vanhempi u .
  2. Lisää kärkipiste v jonon loppuun.
  3. Jos v = t , sulje molemmat silmukat: olemme löytäneet lyhimmän polun.
Jos jono on tyhjä, palautetaan vastaus, että polkua ei ole ollenkaan ja pysähdymme.
Jos ei, siirrymme paikasta t paikkaan s , joka kerta menemällä vanhemman luo. Palaamme polun käänteisessä järjestyksessä.

Vaikeus

Edmonds-Karp-algoritmi löytää työn aikana jokaisen täydentävän polun ajassa . Alla todistetaan, että tämän algoritmin suorittamien virtauksen lisäysten kokonaismäärä on . Edmonds-Karp-algoritmin monimutkaisuus on siis . $O(|E|)$ $O(|V|\cdot |E|)$ $O(|V|\cdot |E|^{2})$

Todiste

Kutsutaan etäisyyttä kärjestä x kärkeen y lyhimmän polun pituudeksi x :stä y :ään residuaaliverkossa mitattuna reunojen lukumäärällä. Jos sellaista polkua ei ole, pidämme etäisyyttä äärettömänä. Sanotaan, että y on lähestynyt x :ää (poikennut x :stä ), jos etäisyys x :stä y :ään on pienentynyt (lisännyt). Sanotaan, että y on lähempänä x :ää (kauempana x :stä ) kuin z , jos etäisyys x :stä y :ään on pienempi (suurempi) kuin etäisyys x :stä z :hen .

Lemma . Algoritmin aikana mikään kärki ei koskaan lähesty lähdettä. Todiste . Älkää antako näin tapahtua, silloin kun virtaus lisääntyi, jotkut huiput lähestyivät lähdettä. Kutsutaan niitä väärin. Valitsemme yhden vääristä huipuista, joka virtauksen lisäämisen jälkeen osoittautui lähinnä lähdettä (jos niitä on enemmän kuin yksi, niin mikä tahansa). Merkitse valittu huippupiste v :llä . Tarkastellaan lyhintä polkua s :stä v :ään . Merkitse tämän polun toiseksi viimeistä kärkeä u :lla , joten polku näyttää tältä . Koska u on lähempänä s: tä kuin v ja v on lähin laiton kärki s :tä , u on säännöllinen kärki. Merkitään etäisyyksiä s :stä u :hin ja v :iin ennen virtauksen kasvua ja sen jälkeen vastaavasti , , , , , meillä on: $s-\ldots-uv$ $d_{u}\$ ${\displaystyle d_{u}^{'))$ $d_{v}\$ ${\displaystyle d_{v}^{'))$

d_{v}^{'}<d_{v}

{\displaystyle d_{u}^{'}\geq d_{u))

d_{v}^{'}=d_{u}^{'}+1

missä

d_{v}\geq d_{u}+2

Siksi ennen virtauksen kasvua kaari ( u , v ) puuttui jäännösverkosta. Jotta se näkyisi, lisäyspolun piti sisältää kaari ( v , u ). Mutta Edmonds-Karp-algoritmissa lisäyspolku on aina lyhin, joten

d_{v}=d_{u}-1

mikä on ristiriidassa edellisen epätasa-arvon kanssa. Joten oletuksemme oli väärä. Lemma on todistettu.

Sanotaan kriittiseksi lisäyspolun reunojen sitä, jonka jäännöskapasiteetti on minimaalinen. Arvioidaan kuinka monta kertaa jokin reuna (u, v) voi olla kriittinen. Anna sen tapahtua iteraatiossa ja seuraavan kerran iteraatiossa . Ilmaisee etäisyyden s:stä y:ään iteraatiossa t, meillä on: $t_{1}$ $t_{2}$ $D_{y}(t)$

D_{v}(t_{1})=D_{u}(t_{1})+1

D_{v}(t_{2})=D_{u}(t_{2})+1

Huomaa, että iteraatiossa kriittinen reuna katoaa jäännösverkosta. Jotta reuna (u, v) ilmestyisi siihen uudelleen iteraation aikaan mennessä, on välttämätöntä, että jossain väliiteraatiossa valitaan lisäyspolku, joka sisältää reunan (v, u). Näin ollen $t_{1}$ $t_{2}$ ${\näyttötyyli t_{3))$

D_{u}(t_{3})=D_{v}(t_{3})+1

Käyttämällä aiemmin todistettua lemmaa saamme:

D_{v}(t_{2})=D_{u}(t_{2})+1\geq D_{u}(t_{3})+1=D_{v}(t_{3} )+2\geq D_{v}(t_{1})+2

Koska aluksi (muuten v = s, mutta s:ään johtava reuna ei voi esiintyä lyhimmällä polulla s:stä t:hen) ja aina, kun tietysti se on pienempi kuin |V| (lyhyin polku ei sisällä syklejä ja siksi sisältää vähemmän |V|-reunoja), reuna voi olla kriittinen useimmissa tapauksissa. Koska jokainen lisäyspolku sisältää vähintään yhden kriittisen reunan ja niiden reunojen kokonaismäärä, joista saattaa joskus tulla kriittisiä (kaikki alkuperäisen verkon reunat ja niiden vastakkaiset reunat), voimme kasvattaa polkua enintään |E|·|V | yhden kerran. Siksi iteraatioiden määrä ei ylitä O(|E|·|V|), mikä oli todistettava. $D_{v}>0$ ${\näyttötyyli D_{v))$ ${\frac {(|V|-1)-1}{2}}+1=|V|/2$ $2|E|$

Esimerkki

Olkoon verkko, jonka lähde on kärjessä ja nielu kärjessä . Kuvassa pari kuvaa virtausta pitkin tätä reunaa ja sen läpimenoa. $A$ $G$ $f/c$

Leveys ensimmäinen haku

Kuvataan ensimmäisessä vaiheessa leveyshakua.

Jono koostuu yhdestä pisteestä A. Huippupisteessä A on vieraillut. Ei ole ylätasoa.
Jono koostuu (alusta loppuun) pisteistä B ja D. Käytetään kärkeissä A, B, D. Pisteillä B, D on vanhempi A.
Jono koostuu pisteistä D ja C. Vierailevat A, B, C, D. Vertiselillä B, D on vanhempi A, kärjessä C on pää B.
Jono koostuu pisteistä C, E, F. Vierailevat A, B, C, D, E, F. Verticeillä B, D on emo A, kärjessä C on vanhempi B, kärjeissä E, F on vanhempi D.
Vertex C poistetaan jonosta: sen reunat johtavat vain jo vierailtuihin pisteisiin.
Reuna (E,G) löytyy ja silmukka pysähtyy. Pistepisteet (F,G) ovat jonossa. Kaikki huippupisteet käyty. Pisteillä B, D on emo A, kärjessä C on emo B, kärjessä E, F on yläpäässä D ja kärjessä G on emo E.
Menemme vanhemman mukana: . Palaamme kuluneen polun käänteisessä järjestyksessä: . $G\to E\to D\to A$ $A\to D\to E\to G$

Huomaa, että jonoon lisättiin peräkkäin kärjet, jotka saavutettiin A:sta tasan 1, tasan 2 askeleen ja tasan 3 askeleen. Lisäksi jokaisen kärjen pää on se kärki, joka saavutetaan A:sta tasan 1 askeleen nopeammin.

Perusalgoritmi

Polun kapasiteetti	Polku
Polun kapasiteetti
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0.2-0.1-0)=$ $\min(3,2,1)=1$	${\näyttötyyli A,D,E,G}$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	${\näyttötyyli A,D,F,G}$

${\näyttötyyli \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f} (F,G))=}$ $\min(3-0.4-0.1-0.6-2.9-2)=$ $\min(3,4,1,4,7)=1$	${\näyttötyyli A,B,C,D,F,G}$

${\näyttötyyli \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f} (D,F),c_{f}(F,G))=}$ $\min(3-1.4-1.2-0.0--1.6-3.9-3)=$ $\min(2,3,2,1,3,6)=1$	${\näyttötyyli A,B,C,E,D,F,G}$

Huomaa, että algoritmin suorituksen aikana komplementaaristen polkujen pituudet (merkitty punaisella kuvissa) eivät pienene. Tämä ominaisuus täyttyy, koska etsimme lyhintä täydentävää polkua .

Dinitzin algoritmi

Edmonds-Karp-algoritmin parannettu versio on Dinitz-algoritmi, joka vaatii operaatioita. $O(|V|^{2}|E|)$

Kutsutaan graafin G apuääriviivatonta verkkoa , jonka lähde on s, sen aligraafia, joka sisältää vain ne reunat (u, v), joiden minimietäisyys s:stä v:ään on yhtä suurempi kuin minimietäisyys s:stä u:han.

Dinitin algoritmi:

Rakennamme jäännösgraafista minimaalisen ääriviivattoman verkon.
Niin kauan kuin verkossa on polku pisteestä s paikkaan t, suorita seuraavat vaiheet:
1. Etsi lyhin polku s:stä t:hen. Jos sitä ei ole, poistu silmukasta.
2. Jäännösverkon löydetyltä polulta etsimme reunaa, jonka kapasiteetti on minimi . $c_{\min }$
3. Jokaiselle löydetyn polun reunalle lisäämme virtausta :lla ja vastakkaiseen suuntaan vähennämme sitä . $c_{\min }$ $c_{\min }$
4. Poistamme kaikki reunat, jotka ovat saavuttaneet kylläisyyden.
5. Poistamme kaikki umpikujat (eli kärjet, paitsi nielu, josta ei kulje reunat, ja kärjet, paitsi lähteen, johon ei tule kulmia) sekä kaikki niihin liittyvät reunat.
6. Toista edellinen vaihe niin kauan kuin on jotain poistettavaa.
Jos löydetty virta ei ole nolla, lisää se kokonaisvirtaan ja palaa vaiheeseen 1.

Linkit

Kirjallisuus

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

Kaavion hakualgoritmit
Tietämättömät menetelmät	Kaksisuuntainen haku Säteen haku Leksikografinen leveys ensimmäinen haku Leveys ensimmäinen haku Hae kustannuskriteerin mukaan Ensimmäinen syvyyshaku Peruutushaku Hae kiipeämällä huipulle Syvyysrajoitettu haku Syvyys-ensin haku iteratiivisella syventämisellä
Tietoon perustuvat menetelmät	Alfa beta leikkaus Haara- ja sidontamenetelmä Hae ensimmäisen parhaan osuman perusteella A* B* D* Siirtymäkohdan löytäminen IDA* Rekursiivinen haku ensimmäisen parhaan osuman perusteella SMA*
Pikanäppäimet	Aalto-algoritmi Bellman-Ford-algoritmi Dijkstran algoritmi Johnsonin algoritmi Levitin algoritmi Floyd-Warshall-algoritmi Reunahaku
Vähintään ulottuva puu	Boruvkan algoritmi Primin algoritmi Kruskalin algoritmi
Muut	British Museum Algorithm Edmondsin algoritmi Puun läpikulku Lähin naapuri -algoritmi matkustavan myyjän ongelmassa