Algoritmul lui Dinit

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 mai 2021; verificările necesită 3 modificări .

Algoritmul Dinitz este un algoritm polinom pentru găsirea debitului maxim într-o rețea de transport , propus în 1970 de matematicianul sovietic (mai târziu israelian) Efim Dinitz . Complexitatea temporală a algoritmului este . O astfel de estimare poate fi obținută prin introducerea conceptelor de rețea auxiliară și de flux de blocare (pseudo-maximal) . În rețelele cu lățimi de bandă unitare, există o estimare a complexității timpului mai puternică: . $O(|V|^{2}|E|)$ $O(|E||V|)$

Descriere

Fie o rețea de transport , în care și sunt, respectiv, debitul și fluxul prin margine . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

Lățimea de bandă reziduală este o mapare definită ca:

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

Daca , $(u,v)\in E$ $c_{f}(u,v)=c(u,v)-f(u,v)$ $c_{f}(v,u)=f(u,v)$ În alte surse $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
$c_{f}(u,v)=0$ in caz contrar.

Rețea reziduală - grafic , unde

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

E_{f}=\{(u,v)\în V\time V\mid c_{f}(u,v)>0\)

. O cale complementară este o cale în graficul rezidual .

st

G_f

Fie lungimea celei mai scurte căi de la până la din grafic . Atunci rețeaua auxiliară a graficului este graficul , unde

\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\))

. Un flux de blocare este un flux astfel încât graficul c nu conține o cale.

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

Algoritm

Algoritmul lui Dinit

Intrare : Rețea .

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

Ieșire : debit maxim .

st

f

Instalați pentru fiecare . $f(e)=0$ $e\în E$
Creați din grafic . Dacă , opriți și ieșiți . $G_L$ $G_f$ $G$ $\operatorname {dist} (t)=\infty$ $f$
Găsiți firul de blocare în . $f'$ $G_L$
Creșteți fluxul cu fluxul și treceți la pasul 2. $f$ $f'$

Analiză

Se poate arăta că de fiecare dată numărul de muchii din calea cea mai scurtă de la sursă la chiuvetă crește cu cel puțin una, deci nu mai există fluxuri de blocare în algoritm, unde este numărul de vârfuri din rețea. Rețeaua auxiliară poate fi construită prin parcurgerea lățimii întâi în timp , iar fluxul de blocare la fiecare nivel al graficului poate fi găsit în timp . Prin urmare, timpul de rulare al algoritmului Dinits este . $n-1$ $n$ $G_L$ $O(|V|+|E|)$ $O(|V||E|)$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

Folosind structuri de date numite arbori dinamici , este posibil să găsiți fluxul de blocare pe fiecare fază în timp , apoi timpul de rulare al algoritmului lui Dinitz poate fi îmbunătățit la . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Exemplu

Mai jos este o simulare a algoritmului lui Dinitz. În rețeaua auxiliară, vârfurile cu etichete roșii sunt valorile . Firul de blocare este marcat cu albastru. $G_L$ $\operatorname {dist} (v)$

	$G$	$G_f$	$G_L$
unu.
	Un fir de blocare este format din căi: $\{s,1,3,t\)$ cu 4 unități de debit, $\{s,1,4,t\)$ cu 6 unități de debit și $\{s,2,4,t\)$ cu 4 unitati de debit. Prin urmare, fluxul de blocare conține 14 unități, iar valoarea debitului este 14. Rețineți că calea complementară are 3 margini. $\|f\|$
2.
	Un fir de blocare este format din căi: $\{s,2,4,3,t\)$ cu 5 unități de debit. Prin urmare, fluxul de blocare conține 5 unități, iar valoarea fluxului este 14 + 5 = 19. Rețineți că calea complementară are 4 margini. $\|f\|$
3.
	Stocul nu este accesibil în rețea . Prin urmare, algoritmul oprește și returnează fluxul maxim de magnitudine 19. Rețineți că în fiecare flux de blocare, numărul de muchii din calea complementară este crescut cu cel puțin una. $t$ $G_f$

Istorie

Algoritmul Dinitz a fost publicat în 1970 de fostul om de știință sovietic Efim Dinitz, care acum este membru al Facultății de Inginerie Calculatoare a Universității Ben-Gurion (Israel), mai devreme decât algoritmul Edmonds-Karp , care a fost publicat în 1972, dar creat mai devreme. Ei au arătat în mod independent că, în algoritmul Ford-Fulkerson , dacă calea complementară este cea mai scurtă, lungimea căii complementare nu scade.

Algoritmul lui Dinitz cu propagare

Complexitatea de timp a algoritmului poate fi redusă prin optimizarea procesului de găsire a unui fir de blocare. Pentru a face acest lucru, este necesar să introduceți conceptul de potențial . Potențialul muchiei este , iar potențialul vârfului este . După aceeași logică , a . Ideea îmbunătățirii este de a căuta un vârf cu potențial pozitiv minim în rețeaua auxiliară și de a construi un flux de blocare prin el folosind cozi . $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)}\operatorname {pot} (e)\}$ $\operatorname {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatorname {pot} (e)$ $\operatorname {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatorname {pot} (e)$

Intrare : Rețea .

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

Ieșire : debit maxim .

st

f

Instalați pentru fiecare . $f(e)=0$ $e\în E$
Creați din grafic . Dacă , opriți și ieșiți . $G_L$ $G_f$ $G$ $\operatorname {dist} (s,t)=\infty$ $f$
Instalați pentru fiecare . $f'(e)=0$ $e\în E$
Determinați potențialul fiecărui vârf.
Atâta timp cât există un vârf astfel încât : $v\în V$ $\operatorname {pot} (v)>0$
1. Definiți fluxul utilizând propagarea directă de la . $f''$ $v$
2. Determinați debitul utilizând propagarea inversă din . $f'''$ $v$
3. Completați fluxul cu fluxuri și . $f'$ $f''$ $f'''$
Creșteți fluxul cu fluxul și treceți la pasul 2. $f$ $f'$

Algoritmii de propagare înainte și înapoi servesc pentru a găsi căi de la la și , respectiv, de la la. Un exemplu de algoritm de propagare directă folosind cozi: $v$ $t$ $s$ $v$

Intrare : Rețea auxiliară , vârf astfel încât .

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

v\în V

\operatorname {pot} (v)>0

Ieșire : un flux de la sursă la vârf care face parte dintr-un flux de blocare.

f''

s

v

Instalați pentru toți : . $w\in V\setminus \{v\}$ $U(w)=0$
Instalați și . $U(v)=\operatorname {pot} (v)$ $\operatorname {pot} (v)=0$
Adăugați la coadă . $v$ $Q$
Atâta timp cât coada nu este goală: $Q$
1. Setați valoarea ultimului element al cozii. $v$
2. pa : $U(v)>0$
  1. Pentru fiecare margine : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\operatorname {pot} (e), U(v)\))$ .
  3. Actualizare . $U(v)=U(v)-f''(e)$
  4. Actualizare . $U(w)=U(w)+f''(e)$
  5. Instalați . $\operatorname {pot} (w)=\operatorname {pot} (w)-\operatorname {pot} (e)$
  6. Dacă și scoateți din coadă ._ $w\neq t$ $U(w)=f''(e)$ $w$ $Q$

Datorită faptului că cel puțin un vârf este „saturat” în fiecare iterație a căutării unui flux de blocare, acesta este finalizat în iterații din cel mai rău caz, fiecare dintre acestea având în vedere maximul de vârfuri. Fie numărul de margini „saturate” în fiecare -a iterație a căutării unui fir de blocare. Apoi complexitatea sa asimptotică este , unde este numărul de vârfuri și numărul de muchii din grafic. Astfel, complexitatea asimptotică a algoritmului de răspândire al lui Dinitz este egală cu , deoarece fluxul de blocare poate trece cel mult prin vârfuri. $|V|-1$ $|V|$ $l_{i}$ $i$ $\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|$

Literatură

Yefim Dinitz. Algoritmul lui Dinitz: versiunea originală și versiunea lui Even // Informatică teoretică: eseuri în memoria lui Shimon Even (engleză) / Oded Goldreich, Arnold L. Rosenberg și Alan L. Selman. - Springer, 2006. - P. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4 Blocarea fluxurilor și algoritmul lui Fujishige // Optimizarea combinatorie: teorie și algoritmi (Algoritmi și combinatorice, 21 ) . - Springer Berlin Heidelberg , 2008. - P. 174-176 . — ISBN 978-3-540-71844-4 .

Link -uri

Algoritmul lui Dinit pe e-maxx.ru: Descriere, dovezi, implementare în C++