Dinit algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 24-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Dinitz-algoritmus egy polinomiális algoritmus a szállítási hálózatban a maximális áramlás meghatározására , amelyet 1970-ben Efim Dinitz szovjet (később izraeli) matematikus javasolt . Az algoritmus időbonyolultsága . Ilyen becslést kaphatunk a segédhálózat és a blokkoló (pszeudo-maximális) áramlás fogalmának bevezetésével . Az egységnyi sávszélességű hálózatokban erősebb az időbonyolultsági becslés: . $O(|V|^{2}|E|)$ $O(|E||V|)$

Leírás

Legyen egy közlekedési hálózat , amelyben és az áteresztőképesség és az élen áthaladó áramlás . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

A maradék sávszélesség a következőképpen definiált leképezés :

{\displaystyle c_{f}\colon V\times V\to \mathbb {R} ^{+))

Ha , $(u,v)\in E$ $c_{f}(u,v)=c(u,v)-f(u,v)$ $c_{f}(v,u)=f(u,v)$ Más forrásokban $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
$c_{f}(u,v)=0$ másképp.

Maradékhálózat - grafikon , ahol

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

{\displaystyle E_{f}=\{(u,v)\in V\times V\mid c_{f}(u,v)>0\))

. A komplementer útvonal egy útvonal a maradék gráfban .

st

G_f

Legyen a legrövidebb út hossza -tól -ig a gráfban . Ekkor a gráf segédhálózata a gráf , ahol

\operatorname {dist} (v)

s

v

G_f

G_f

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

{\displaystyle E_{L}=\{(u,v)\in E_{f}\mid \operatorname {dist} (v)=\operatorname {dist} (u)+1\))

. A blokkoló áramlás olyan áramlás , amelyben a c gráf nem tartalmaz útvonalat.

st

f

G'=(V,E_{L}',c_{f}|_{E_{L)),s,t)

E_{L}'=\{(u,v)\mid f(u,v)<c_{f}|_{E_{L}}(u,v)\}

st

Algoritmus

Dinit algoritmusa

Bemenet : Hálózat .

G=(V,E,c,s,t)

Kimenet : maximális áramlás .

st

f

Telepítse mindegyikhez . $f(e)=0$ $e\in E$
Hozzon létre grafikonból . Ha , leállítás és kimenet . $G_L$ $G_f$ $G$ $\operatorname {dist} (t)=\infty$ $f$
Keresse meg a blokkoló szálat a következőben . $f'$ $G_L$
Növelje az áramlást áramlással, és folytassa a 2. lépéssel. $f$ $f'$

Elemzés

Megmutatható, hogy minden alkalommal, amikor a forrástól a nyelőig vezető legrövidebb úton lévő élek száma legalább eggyel nő, így nincs több blokkoló folyam az algoritmusban, ahol a hálózat csúcsainak száma. A segédhálózat szélesség-első időben történő bejárással építhető fel , és a blokkoló áramlás a gráf minden szintjén időben megtalálható . Ezért a Dinits algoritmus futási ideje . $n-1$ $n$ $G_L$ $O(|V|+|E|)$ $O(|V||E|)$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

A dinamikus fák nevű adatstruktúrák segítségével időben meg lehet találni a blokkoló áramlást az egyes fázisokon, majd a Dinitz-féle algoritmus futási idejét -re javítani . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Példa

Az alábbiakban a Dinitz-féle algoritmus szimulációja látható. A segédhálózatban a piros címkés csúcsok az értékek . A blokkolószál kék színnel van jelölve. $G_L$ $\operatorname {dist} (v)$

	$G$	$G_f$	$G_L$
egy.
	Egy blokkolószál útvonalakból áll: $\{s,1,3,t\}$ 4 áramlási egységgel, $\{s,1,4,t\}$ 6 áramlási egységgel, ill ${\megjelenítési stílus \{s,2,4,t\))$ 4 áramlási egységgel. Ezért a blokkoló áramlás 14 egységet tartalmaz, az áramlás értéke pedig 14. Vegye figyelembe, hogy a komplementer útvonalnak 3 éle van. $\|f\|$
2.
	Egy blokkolószál útvonalakból áll: $\{s,2,4,3,t\}$ 5 áramlási egységgel. Ezért a blokkoló áramlás 5 egységet tartalmaz, és az áramlás értéke 14 + 5 = 19. Vegye figyelembe, hogy a komplementer útvonalnak 4 éle van. $\|f\|$
3.
	A készlet nem érhető el a hálózaton . Ezért az algoritmus megáll, és a maximális 19 nagyságú áramlást adja vissza. Vegye figyelembe, hogy minden blokkoló folyamban a komplementer útvonal éleinek száma legalább eggyel megnövekszik. $t$ $G_f$

Történelem

A Dinitz-algoritmust 1970-ben az egykori szovjet tudós, Efim Dinitz tette közzé, aki ma a Ben-Gurion Egyetem (Izrael) Számítógép-mérnöki Karának tagja, korábban, mint az 1972-ben megjelent Edmonds-Karp algoritmust , de korábban létrehozott. Önállóan kimutatták, hogy a Ford-Fulkerson algoritmusban , ha a komplementer út a legrövidebb, a komplementer út hossza nem csökken.

Dinitz-algoritmus terjedéssel

Az algoritmus időbeli összetettsége csökkenthető a blokkoló szál keresési folyamatának optimalizálásával. Ehhez be kell vezetni a potenciál fogalmát . Az élpotenciál , a csúcspotenciál pedig . Ugyanezen logika szerint a . A fejlesztés ötlete az, hogy a segédhálózatban egy minimális pozitív potenciállal rendelkező csúcsot keressünk, és sorok segítségével blokkoló áramlást építsünk ki rajta . $e\in E$ $\operatorname {pot} (e)=c_{f}(e)$ $v\in V\setminus \{s,t\}$ $\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e),\sum _{e\in \ delta ^{-}(v)}\operátornév {pot} (e)\}$ $\operatorname {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e)$ $\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$

Bemenet : Hálózat .

G=(V,E,c,s,t)

Kimenet : maximális áramlás .

st

f

Telepítse mindegyikhez . $f(e)=0$ $e\in E$
Hozzon létre grafikonból . Ha , leállítás és kimenet . $G_L$ $G_f$ $G$ $\operatorname {dist} (s,t)=\infty$ $f$
Telepítse mindegyikhez . $f'(e)=0$ $e\in E$
Határozza meg az egyes csúcsok potenciálját!
Mindaddig, amíg van egy olyan csúcs , amely : $v\in V$ $\operatorname {pot} (v)>0$
1. Határozza meg az áramlást a -tól való előrehaladás segítségével . $f''$ $v$
2. Határozza meg az áramlást a visszaszaporítás segítségével . $f'''$ $v$
3. Egészítse ki az adatfolyamot streamekkel és . $f'$ $f''$ $f'''$
Növelje az áramlást áramlással, és folytassa a 2. lépéssel. $f$ $f'$

Az előre, illetve a visszaszaporító algoritmusok arra szolgálnak, hogy megtalálják az oda és onnan tartó útvonalakat . Példa a közvetlen terjesztési algoritmusra sorokat használva: $v$ $t$ $s$ $v$

Bemenet : Segédhálózat , olyan csúcspont , hogy .

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

v\in V

\operatorname {pot} (v)>0

Kimenet : egy áramlás a forrástól a csúcsig , amely egy blokkoló folyam része.

f''

s

v

Telepítés mindenkinek : . ${\displaystyle w\in V\setminus \{v\))$ $U(w)=0$
Telepítse és . $U(v)=\operátornév {pot} (v)$ $\operatorname {pot} (v)=0$
Hozzáadás a sorhoz . $v$ $K$
Amíg a sor nem üres: $K$
1. Állítsa be az értéket a sor utolsó elemére. $v$
2. Viszlát : $U(v)>0$
  1. Minden élhez : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\operátornév {pot} (e),U(v)\))$ .
  3. Frissítés . $U(v)=U(v)-f''(e)$
  4. Frissítés . $U(w)=U(w)+f''(e)$
  5. Telepítse . $\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$
  6. Ha és dequeue . _ $w\neq t$ $U(w)=f''(e)$ $w$ $K$

Tekintettel arra, hogy a blokkoló folyam keresésének minden iterációjában legalább egy csúcs "telített", ez a legrosszabb eset iterációival fejeződik be, amelyek mindegyike a csúcsok maximális számát veszi figyelembe. Legyen a "telített" élek száma a blokkoló szál keresésének minden -edik iterációjában. Ekkor az aszimptotikus komplexitása , ahol a csúcsok száma és a gráf éleinek száma. Így a Dinitz-féle szórási algoritmus aszimptotikus komplexitása egyenlő -val , mivel a blokkoló áramlás legfeljebb csúcsokon haladhat át . $|V|-1$ $|V|$ $l_{i}$ $én$ $\sum _{i=1}^{n-1}O(n+l_{i})=O(n^{2}+\sum _{i=1}^{n-1}l_ {i})=O(n^{2}+m)$ $n$ $m$ $O(|V|^{3})$ $|V|$

Irodalom

Jefim Dinitz. Dinitz algoritmusa: Az eredeti verzió és az Even verziója // Elméleti számítástechnika: Esszék Shimon Even emlékére (angol) / Oded Goldreich, Arnold L. Rosenberg és Alan L. Selman. - Springer, 2006. - P. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4. Az áramlások blokkolása és a Fujishige-algoritmus // Kombinatorikus optimalizálás: elmélet és algoritmusok (Algoritmusok és kombinatorika, 21 ) . - Springer Berlin Heidelberg , 2008. - P. 174-176 . — ISBN 978-3-540-71844-4 .

Linkek

Dinit algoritmusa az e-maxx.ru oldalon: Leírás, bizonyítások, implementáció C++ nyelven