Dinits algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. maj 2021; checks kræver 3 redigeringer .

Dinitz-algoritmen er en polynomiel algoritme til at finde det maksimale flow i et transportnetværk , foreslået i 1970 af den sovjetiske (senere israelske) matematiker Efim Dinitz . Algoritmens tidskompleksitet er . Et sådant estimat kan opnås ved at introducere begreberne et hjælpenetværk og et blokerende (pseudo-maksimalt) flow . I netværk med enhedsbåndbredder er der et stærkere tidskompleksitetsestimat: . $O(|V|^{2}|E|)$ $O(|E||V|)$

Beskrivelse

Lade være et transportnetværk , hvori og er henholdsvis gennemstrømningen og strømmen gennem kanten . $G=(V,E,c,s,t)$ $c(u,v)$ $f(u,v)$ $(u,v)$

Den resterende båndbredde er en kortlægning defineret som:

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

hvis , $(u,v)\in E$ $c_{f}(u,v)=c(u,v)-f(u,v)$ $c_{f}(v,u)=f(u,v)$ I andre kilder $c_{f}(u,v)=c(u,v)-f(u,v)+f(v,u)$
$c_{f}(u,v)=0$ Ellers.

Restnetværk - graf , hvor

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

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

. En komplementær sti er en sti i restgrafen .

st

G_f

Lad være længden af den korteste vej fra til i grafen . Så er grafens hjælpenetværk grafen , hvor

\operatørnavn {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}\midt \operatørnavn {dist} (v)=\operatørnavn {dist} (u)+1\))

. Et blokerende flow er et flow , således at graf c ikke indeholder en sti.

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

Algoritme

Dinits algoritme

Input : Netværk .

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

Udgang : maksimalt flow .

st

f

Installer for hver . $f(e)=0$ $e\i E$
Opret fra graf . Hvis , stop og output . $G_L$ $G_f$ $G$ $\operatørnavn {dist} (t)=\infty$ $f$
Find blokerende tråd i . $f'$ $G_L$
Forøg flow med flow og gå til trin 2. $f$ $f'$

Analyse

Det kan vises, at hver gang antallet af kanter i den korteste vej fra kilden til synken stiger med mindst én, så der ikke er flere blokerende flows i algoritmen, hvor er antallet af toppunkter i netværket. Hjælpenetværket kan bygges ved bredde-først gennemløb i tid , og blokeringsflowet på hvert niveau af grafen kan findes i tid . Derfor er køretiden for Dinits-algoritmen . $n-1$ $n$ $G_L$ $O(|V|+|E|)$ $O(|V||E|)$ $O(|V|)\cdot (O(|V|+|E|)+O(|V||E|))=O(|V|^{2}|E|)$

Ved at bruge datastrukturer kaldet dynamiske træer er det muligt at finde blokeringsflowet på hver fase i tid , så kan køretiden for Dinitz's algoritme forbedres til . $O(|E|\log |V|)$ $O(|V||E|\log |V|)$

Eksempel

Nedenfor er en simulering af Dinitz's algoritme. I hjælpenetværket er hjørnerne med røde etiketter værdierne . Spærretråden er markeret med blåt. $G_L$ $\operatørnavn {dist} (v)$

	$G$	$G_f$	$G_L$
en.
	En blokerende tråd består af stier: ${\displaystyle \{s,1,3,t\))$ med 4 flowenheder, ${\displaystyle \{s,1,4,t\))$ med 6 flowenheder, og ${\displaystyle \{s,2,4,t\))$ med 4 flowenheder. Derfor indeholder det blokerende flow 14 enheder, og flowværdien er 14. Bemærk at den komplementære bane har 3 kanter. $\|f\|$
2.
	En blokerende tråd består af stier: ${\displaystyle \{s,2,4,3,t\))$ med 5 flowenheder. Derfor indeholder det blokerende flow 5 enheder, og værdien af flowet er 14 + 5 = 19. Bemærk at den komplementære vej har 4 kanter. $\|f\|$
3.
	Aktien er ikke tilgængelig på netværket . Derfor stopper algoritmen og returnerer det maksimale flow af størrelsesorden 19. Bemærk, at i hvert blokeringsflow øges antallet af kanter i den komplementære bane med mindst én. $t$ $G_f$

Historie

Dinitz-algoritmen blev udgivet i 1970 af den tidligere sovjetiske videnskabsmand Efim Dinitz, som nu er medlem af fakultetet for datateknik ved Ben-Gurion University (Israel), tidligere end Edmonds-Karp-algoritmen , som blev offentliggjort i 1972, men oprettet tidligere. De viste uafhængigt, at i Ford-Fulkerson-algoritmen , hvis den komplementære vej er den korteste, falder længden af den komplementære vej ikke.

Dinitz's algoritme med udbredelse

Algoritmens tidskompleksitet kan reduceres ved at optimere processen med at finde en blokerende tråd. For at gøre dette er det nødvendigt at introducere begrebet potentiale . Kantpotentialet er , og toppunktspotentialet er . Af samme logik er en . Ideen med forbedringen er at lede efter et toppunkt med det mindste positive potentiale i hjælpenetværket og bygge et blokerende flow gennem det ved hjælp af køer . $e\in E$ $\operatørnavn {pot} (e)=c_{f}(e)$ ${\displaystyle v\in V\setminus \{s,t\))$ $\operatorname {pot} (v)=\min\{\sum _{e\in \delta ^{+}(v)}\operatørnavn {pot} (e),\sum _{e\in \ delta ^{-}(v)}\operatørnavn {pot} (e)\}$ $\operatørnavn {pot} (s)=\sum _{e\in \delta ^{+}(v)}\operatørnavn {pot} (e)$ $\operatørnavn {pot} (t)=\sum _{e\in \delta ^{-}(v)}\operatørnavn {pot} (e)$

Input : Netværk .

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

Udgang : maksimalt flow .

st

f

Installer for hver . $f(e)=0$ $e\i E$
Opret fra graf . Hvis , stop og output . $G_L$ $G_f$ $G$ $\operatørnavn {dist} (s,t)=\infty$ $f$
Installer for hver . $f'(e)=0$ $e\i E$
Bestem potentialet for hvert toppunkt.
Så længe der er et toppunkt , sådan at : $v\in V$ $\operatørnavn {pot} (v)>0$
1. Definer flowet ved at bruge fremadgående udbredelse fra . $f''$ $v$
2. Bestem flow ved hjælp af backpropagation fra . $f'''$ $v$
3. Fuldfør streamen med streams og . $f'$ $f''$ $f'''$
Forøg flow med flow og gå til trin 2. $f$ $f'$

Fremadgående og tilbagegående algoritmer tjener til at finde stier fra henholdsvis til og fra til . Et eksempel på den direkte udbredelsesalgoritme ved brug af køer: $v$ $t$ $s$ $v$

Input : Hjælpe netværk , toppunkt således .

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

v\in V

\operatørnavn {pot} (v)>0

Output : Et flow fra kilde til toppunkt , der er en del af et blokerende flow.

f''

s

v

Installer for alle : . $w\in V\setminus \{v\}$ $U(w)=0$
Installer og . $U(v)=\operatørnavn {pot} (v)$ $\operatørnavn {pot} (v)=0$
Tilføj til kø . $v$ $Q$
Så længe køen ikke er tom: $Q$
1. Indstil værdien til det sidste element i køen. $v$
2. farvel : $U(v)>0$
  1. For hver kant : $e=(v,w)\in \delta ^{+}(v)$
  2. ${\displaystyle f''(e)=\min\{\operatørnavn {pot} (e),U(v)\))$ .
  3. Opdatering . $U(v)=U(v)-f''(e)$
  4. Opdatering . $U(w)=U(w)+f''(e)$
  5. Installer . $\operatørnavn {pot} (w)=\operatørnavn {pot} (w)-\operatørnavn {pot} (e)$
  6. Hvis og afkø . _ $w\neq t$ $U(w)=f''(e)$ $w$ $Q$

På grund af det faktum, at mindst et toppunkt er "mættet" i hver iteration af søgningen efter et blokerende flow, fuldføres det i worst-case iterationer, som hver især tager højde for maksimum af toppunkter. Lad være antallet af "mættede" kanter i hver -te iteration af søgningen efter en blokerende tråd. Så er dens asymptotiske kompleksitet , hvor er antallet af hjørner og er antallet af kanter i grafen. Således er den asymptotiske kompleksitet af Dinitz's spredningsalgoritme lig med , da den blokerende strøm højst kan passere gennem hjørner. $|V|-1$ $|V|$ $l_{i}$ $jeg$ $\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|$

Litteratur

Yefim Dinitz. Dinitz' Algorithm: The Original Version and Even's Version // Theoretical Computer Science: Essays in Memory of Shimon Even (engelsk) / Oded Goldreich, Arnold L. Rosenberg og Alan L. Selman. - Springer, 2006. - S. 218-240. — ISBN 978-3540328803 .
BH Korte, Jens Vygen. 8.4 Blokering af strømme og Fujishiges algoritme // Kombinatorisk optimering: Teori og algoritmer (Algorithms and Combinatorics, 21 ) . - Springer Berlin Heidelberg , 2008. - S. 174-176 . — ISBN 978-3-540-71844-4 .

Dinits algoritme

Beskrivelse

Algoritme

Analyse

Eksempel

Historie

Dinitz's algoritme med udbredelse

Litteratur

Links