Dinicsův algoritmus - Dinics algorithm - Wikipedia

Dinicův algoritmus nebo Dinitzův algoritmus je silně polynomický algoritmus pro výpočet maximální průtok v toková síť, koncipovaný v roce 1970 izraelským (dříve sovětským) počítačovým vědcem Jefimem (Chaimem) A. Dinitzem.^[1] Algoritmus běží ${ displaystyle O (V ^ {2} E)}$ čas a je podobný Algoritmus Edmonds – Karp, který běží dovnitř ${ displaystyle O (VE ^ {2})}$ v tom, že používá nejkratší rozšiřující cesty. Zavedení pojmů graf úrovně a blokování toku umožnit Dinicovu algoritmu dosáhnout svého výkonu.

Dějiny

Yefim Dinitz vynalezl tento algoritmus v reakci na pre-class cvičení v Adelson-Velsky třída algoritmů. V té době nevěděl o základních skutečnostech týkajících se Algoritmus Ford-Fulkerson.^[2]

Dinitz zmiňuje vynalézání svého algoritmu v lednu 1969, který byl publikován v roce 1970 v časopise Doklady Akademii Nauk SSSR. V roce 1974 Shimon Even a (jeho tehdejší Ph.D. student) Alon Itai na Technion v Haifě byli velmi zvědaví a zaujati Dinitzovým algoritmem stejně Alexander V. Karzanov související myšlenka blokování toku. Bylo však pro ně obtížné dešifrovat tyto dva články, z nichž každý byl omezen na čtyři stránky, aby splnil omezení deníku Doklady Akademii Nauk SSSR. Ani se nevzdal a po třech dnech úsilí se podařilo oběma papírům porozumět, kromě problému vrstvené údržby sítě. V příštích několika letech dokonce přednášel o „Dinicově algoritmu“, nesprávně vyslovil jméno autora a popularizoval jej. Even a Itai také přispěli k tomuto algoritmu kombinací BFS a DFS, což je způsob, jakým je nyní algoritmus běžně prezentován.^[3]

Asi 10 let poté, co byl vynalezen Ford-Fulkersonův algoritmus, nebylo známo, zda by bylo možné provést ukončení v polynomiálním čase v obecném případě iracionálních okrajových kapacit. To způsobilo nedostatek jakéhokoli známého algoritmu polynomiálního času k vyřešení problému s maximálním tokem v obecných případech. Dinitzův algoritmus a Algoritmus Edmonds – Karp (publikováno v roce 1972) oba nezávisle ukázali, že v algoritmu Ford-Fulkerson, je-li každá rozšiřující cesta nejkratší, pak délka rozšiřujících cest neklesá a algoritmus vždy končí.

Definice

Nechat ${ displaystyle G = ((V, E), c, f, s, t)}$ být sítí s ${ displaystyle c (u, v)}$ a ${ displaystyle f (u, v)}$ kapacita a tok okraje ${ displaystyle (u, v)}$ , resp.

The zbytková kapacita je mapování

{ displaystyle c_ {f} dvojtečka V krát V až R ^ {+}}

definováno jako,

-li ${ displaystyle (u, v) v E}$ ,
${ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}$
${ displaystyle c_ {f} (u, v) = 0}$ v opačném případě.

The zbytkový graf je nevážený graf

{ displaystyle G_ {f} = ((V, E_ {f}), c_ {f} | _ {E_ {f}}, s, t)}

, kde

{ displaystyle E_ {f} = {(u, v) v V krát V tlustého střeva ; c_ {f} (u, v)> 0 }}

.

An rozšiřující cesta je

{ displaystyle s}

–

{ displaystyle t}

cesta ve zbytkovém grafu

{ displaystyle G_ {f}}

.

Definovat

{ displaystyle operatorname {dist} (v)}

být délkou nejkratší cesty od

{ displaystyle s}

na

{ displaystyle v}

v

{ displaystyle G_ {f}}

. Pak graf úrovně z

{ displaystyle G_ {f}}

je graf

{ displaystyle G_ {L} = ((V, E_ {L}), c_ {f} | _ {E_ {L}}, s, t)}

, kde

{ displaystyle E_ {L} = {(u, v) v E_ {f} dvojtečce ; operatorname {dist} (v) = operatorname {dist} (u) +1 }}

.

A blokování toku je

{ displaystyle s}

–

{ displaystyle t}

tok

{ displaystyle f}

takový, že graf

{ displaystyle G '= ((V, E_ {L}'), s, t)}

s

{ displaystyle E_ {L} '= {(u, v) colon ; f (u, v)

obsahuje č

{ displaystyle s}

–

{ displaystyle t}

cesta.^[4]^[5]

Algoritmus

Dinicův algoritmus

Vstup: Síť

{ displaystyle G = ((V, E), c, s, t)}

.

Výstup: An

{ displaystyle s}

–

{ displaystyle t}

tok

{ displaystyle f}

maximální hodnoty.

Soubor ${ displaystyle f (e) = 0}$ pro každého ${ displaystyle e v E}$ .
Postavit ${ displaystyle G_ {L}}$ z ${ displaystyle G_ {f}}$ z ${ displaystyle G}$ . Li ${ displaystyle operatorname {dist} (t) = infty}$ , stop a výstup ${ displaystyle f}$ .
Najděte blokující tok ${ displaystyle f '}$ v ${ displaystyle G_ {L}}$ .
Přidejte rozšířený tok ${ displaystyle f}$ podle ${ displaystyle f '}$ a vraťte se ke kroku 2.

Analýza

Je možné ukázat, že počet vrstev v každém blokujícím toku se pokaždé zvýší alespoň o 1, a proto jich je nanejvýš ${ displaystyle | V | -1}$ blokování toků v algoritmu. Pro každého z nich:

graf úrovně ${ displaystyle G_ {L}}$ může být vytvořen vyhledávání na šířku v ${ displaystyle O (E)}$ čas
blokovací tok v grafu úrovně ${ displaystyle G_ {L}}$ najdete v ${ displaystyle O (VE)}$ čas

s celkovou dobou chodu ${ displaystyle O (E + VE) = O (VE)}$ pro každou vrstvu. V důsledku toho je doba běhu Dinicova algoritmu ${ displaystyle O (V ^ {2} E)}$ .^[6]

Pomocí datové struktury s názvem dynamické stromy, lze dobu běhu hledání blokovacího toku v každé fázi zkrátit na ${ displaystyle O (E log V)}$ a proto lze dobu běhu Dinicova algoritmu zlepšit na ${ displaystyle O (VE log V)}$ .

Speciální případy

V sítích s jednotkovými kapacitami platí mnohem silnější časová vazba. Každý blokující tok najdete v ${ displaystyle O (E)}$ času a lze ukázat, že počet fází nepřesahuje ${ displaystyle O ({ sqrt {E}})}$ a ${ displaystyle O (V ^ {2/3})}$ . Algoritmus tedy běží ${ displaystyle O ( min {V ^ {2/3}, E ^ {1/2} } E)}$ čas.^[7]

V sítích, které vznikají z bipartitní shoda problém, počet fází je omezen ${ displaystyle O ({ sqrt {V}})}$ , což vede k ${ displaystyle O ({ sqrt {V}} E)}$ časově omezené. Výsledný algoritmus je také známý jako Algoritmus Hopcroft – Karp. Obecněji platí, že tato vazba platí pro všechny jednotková síť - síť, ve které každý vrchol, s výjimkou zdroje a jímky, má buď jedinou vstupní hranu kapacity jedna, nebo jednu výstupní hranu kapacity jedna a všechny ostatní kapacity jsou libovolná celá čísla.^[5]

Příklad

Následuje simulace Dinicova algoritmu. V grafu úrovně ${ displaystyle G_ {L}}$ , vrcholy se štítky červeně jsou hodnoty ${ displaystyle operatorname {dist} (v)}$ . Cesty v modré barvě tvoří blokující tok.

	${ displaystyle G}$	${ displaystyle G_ {f}}$	${ displaystyle G_ {L}}$
1.
	Blokovací tok se skládá z ${ displaystyle {s, 1,3, t }}$ se 4 jednotkami průtoku, ${ displaystyle {s, 1,4, t }}$ se 6 jednotkami průtoku a ${ displaystyle {s, 2,4, t }}$ se 4 jednotkami průtoku. Blokovací tok má tedy 14 jednotek a hodnotu toku ${ displaystyle \| f \|}$ je 14. Všimněte si, že každá rozšiřující cesta v blokujícím toku má 3 hrany.
2.
	Blokovací tok se skládá z ${ displaystyle {s, 2,4,3, t }}$ s 5 jednotkami průtoku. Blokovací tok má tedy 5 jednotek a hodnotu toku ${ displaystyle \| f \|}$ je 14 + 5 = 19. Pamatujte, že každá rozšiřující cesta má 4 hrany.
3.
	Od té doby ${ displaystyle t}$ nelze dosáhnout v ${ displaystyle G_ {f}}$ , algoritmus ukončí a vrátí tok s maximální hodnotou 19. Všimněte si, že v každém blokujícím toku se počet okrajů v rozšiřující cestě zvýší alespoň o 1.

Viz také

Poznámky

^ Jefim Dinitz (1970). "Algoritmus pro řešení problému maximálního toku v síti s odhadem výkonu" (PDF). Doklady Akademii Nauk SSSR. 11: 1277–1280.
^ Ilan Kadar; Sivan Albagli (2009-11-27). „Dinitzův algoritmus pro nalezení maximálního toku v síti“.
^ Jefim Dinitz. „Dinitzův algoritmus: původní verze a sudá verze“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
^ To znamená, že podgraf vyplývá z odstranění všech nasycených okrajů (tj. Všech okrajů ${ displaystyle (u, v)}$ takhle ${ displaystyle f (u, v) = c_ {f} | _ {E_ {L}} (u, v)}$ ) neobsahuje žádnou cestu z ${ displaystyle s}$ na ${ displaystyle t}$ . Jinými slovy blokování toku je taková, že každá možná cesta z ${ displaystyle s}$ na ${ displaystyle t}$ obsahuje nasycenou hranu.
^ ^A ^b Tarjan 1983, str. 102.
^ Yefim Dinitz (2006). „Dinitzův algoritmus: původní verze a sudá verze“ (PDF). v Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (eds.). Teoretická informatika: Pokusy o paměť Shimon Even. Springer. 218–240. ISBN 978-3-540-32880-3.
^ Dokonce, Šimon; Tarjan, R. Endre (1975). "Tok sítě a testování připojení grafu". SIAM Journal on Computing. 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397.

Reference

Yefim Dinitz (2006). „Dinitzův algoritmus: původní verze a sudá verze“ (PDF). v Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (eds.). Teoretická informatika: Pokusy o paměť Shimon Even. Springer. 218–240. ISBN 978-3-540-32880-3.
Tarjan, R. E. (1983). Datové struktury a síťové algoritmy.CS1 maint: ref = harv (odkaz)
B. H. Korte; Jens Vygen (2008). „8.4 Blokování toků a Fujishigeův algoritmus“. Kombinatorická optimalizace: Teorie a algoritmy (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. 174–176. ISBN 978-3-540-71844-4.

[1] Jefim Dinitz (1970). "Algoritmus pro řešení problému maximálního toku v síti s odhadem výkonu" (PDF). Doklady Akademii Nauk SSSR. 11: 1277–1280.

[2] Ilan Kadar; Sivan Albagli (2009-11-27). „Dinitzův algoritmus pro nalezení maximálního toku v síti“.

[3] Jefim Dinitz. „Dinitzův algoritmus: původní verze a sudá verze“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)

[4] To znamená, že podgraf vyplývá z odstranění všech nasycených okrajů (tj. Všech okrajů ${ displaystyle (u, v)}$ takhle ${ displaystyle f (u, v) = c_ {f} | _ {E_ {L}} (u, v)}$ ) neobsahuje žádnou cestu z ${ displaystyle s}$ na ${ displaystyle t}$ . Jinými slovy blokování toku je taková, že každá možná cesta z ${ displaystyle s}$ na ${ displaystyle t}$ obsahuje nasycenou hranu.

[FOOTNOTETarjan1983102-5] A ^b Tarjan 1983, str. 102.

[6] Yefim Dinitz (2006). „Dinitzův algoritmus: původní verze a sudá verze“ (PDF). v Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman (eds.). Teoretická informatika: Pokusy o paměť Shimon Even. Springer. 218–240. ISBN 978-3-540-32880-3.

[Even1975-7] Dokonce, Šimon; Tarjan, R. Endre (1975). "Tok sítě a testování připojení grafu". SIAM Journal on Computing. 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397.

[1]

[2]

[3]

[4]

[5]

[6]

[7]