2 % Zápisek druhého semináøe z grafových algoritmù - ze dne 13.3.2006
3 % Téma Dinicùv algoritmus a v¹emo¾né jeho modifikace.
4 % Zapsal Bernard Lidický - bernard@matfyz.cz
6 % Verze z 29. dubna 2006
12 \prednaska{2}{Dinicùv algoritmus a jeho analýza}{zapsal Bernard Lidický}
14 \h{Dinicùv algoritmus}
16 Dinicùv algoritmus je zalo¾en na my¹lence, ¾e ve Ford-Fulkersonovì algoritmu
17 není potøeba pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
21 \:Zaèni s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
22 \:Iterativnì vylep¹uj tok podle zlep¹ujících tokù v síti rezerv: {\I (vnìj¹í cyklus)}
23 \::Sestroj sí» rezerv.
24 \::Najdi nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèi.
25 \::Proèisti sí», tj. nech v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách.
26 \::Najdi blokující tok $f_B$:
27 \:::$f_B \leftarrow \<prázdný tok>$
28 \:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)}
29 \::::Najdi $st$-cestu. Napø. hladovì metodou rovnou za nosem.
30 \::::Po¹li co nejvíce po cestì.
31 \::::Sma¾ nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky,
32 èím¾ se zneèistí sí» a nebude fungovat metoda rovnou za nosem.)
34 \::Zlep¹i $f$ podle $f_B$
37 \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.3\hsize}
39 \s{Slo¾itost algoritmu:}
40 Oznaèíme $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì.
43 \:Jeden prùchod vnitøním cyklem trvá $\O(l)$, co¾ mù¾eme odhadnout jako $\O(n)$, proto¾e v¾dy platí $l \leq n$.
44 \:Vnitøní cyklus se provede maximálnì $m$-krát, proto¾e se v¾dy alespoò jedna hrana nasytí
45 a ze sítì vypadne, tak¾e krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
46 \:Èi¹tìní a doèi¹»ování sítì dohromady provedeme takto:
48 \:Rozvrstvíme vrcholy do vrstev podle vzdálenosti od $s$.
49 \:Zaøízneme dlouhé cesty (del¹í, ne¾ do vrstvy obsahující $t$).
50 \:Dr¾íme si frontu vrcholù, které mají $\deg^+ = 0$ èi $\deg^- = 0$.
51 \:Vrcholy z~fronty vybíráme a zahazujeme vèetnì hran, které vedou do/z nich.
52 A pøípadnì pøidáváme do~fronty vrcholy, kterým klesl jeden ze stupòù na 0
53 pøi vyhazování hran. Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
55 Tedy kroky 5 a 12 dohromady spotøebují èas $\O(m)$\foot{Pøesnìji $\O(m+n)$, pokud by v síti byly izolované
56 vrcholy, ale ty mù¾eme zahodit úplnì u¾ na zaèátku.}.
57 \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
61 V~ka¾dém prùchodu Dinicova algoritmu vzroste $l$ alespoò~o~1.
64 Vnìj¹ím cyklem projdeme $\O(n)$ krát, proto¾e nejdel¹í cesta bude mít
65 délku $\leq n$. Celková slo¾itost algoritmu tedy bude $\O(n^2m)$
67 \s{Korektnost algoritmu:}
68 Korektnost Dinicova algoritmu plyne z korektnosti FF algoritmu. Kdy¾ se Dinicùv
69 algoritmus zastaví, musí vydat maximální tok. Pokud ne, tak podle FF algoritmu
70 existuje zlep¹ující cesta, ale to je ve sporu s~krokem~4, který po¾aduje, ¾e ¾ádná
71 zlep¹ující cesta neexistuje.
74 Podíváme se na výpoèet jednoho prùchodu vnìj¹ím cyklem.
75 Délku aktuálnì nejkrat¹í $st$-cesty oznaème~$l$.
76 Vypozorujeme, ¾e délka cest, které pøípadnì vzniknou pøi hledání a sycení
77 v¹ech cest délky $l$, musí být vìt¹í ne¾ $l$. Jinak øeèeno, nestane se,
78 ¾e by vznikaly nové krátké cesty.
80 Vnìj¹í cyklus zaèíná s neproèi¹tìnou sítí. Pøíklad takové sítì je na obrázku nìkde
81 okolo. Po proèi¹tìní zùstanou v~síti jen èerné hrany. Èervené a modré\foot{Modré jsou
82 ty, které vedou v rámci jedné vrstvy, èervené vedou zpìt èi za~spotøebiè èi do~slepých
83 ulièek. Pøi vyti¹tìní na papír není snadné je barevnì odli¹it od èerných.} se zahodí.
84 \figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.3\hsize}
85 Nové hrany tak mohou vznikat jen díky èerným hranám, proto¾e s hranami zahozenými pøi èi¹tìní algoritmus
88 Nová hrana mù¾e vzniknout zlep¹ení toku po nìjaké zlep¹ující cestì, proto¾e
89 kdy¾ po hranì po¹leme nìjaký tok, zvedne se rezerva hrany opaèné, která mohla být
90 nulová\foot{Tedy po zpìtné hranì ne¹lo nic poslat a nepoèítalo se s ní.}.
91 Tím vznikne nová zpìtná hrana. ®ádné novì dopøedné hrany pøeskakující více vrstev nevznikají.
92 \figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.3\hsize}
94 Poka¾dé, kdy¾ se zlep¹í tok podél nìjaké cesty, budou v grafu ke v¹em hranám cesty
95 existovat hrany opaèného smìru s~nenulovou rezervou. Nìkteré
96 tyto opaèné hrany u¾ v~grafu mohly být, ale tím lépe pro nás\foot{Tento odstavec
97 je spí¹e informativní a slou¾í malinko pro osvícení ètenáøe. V dùkazu nemá ¾ádný smysl.}.
99 Vznikem nových hran by mohly vzniknout nové $st$-cesty, které pou¾ívají
100 zpìtné hrany. Ale $st$-cesta, která pou¾ívá zpìtnou hranu, musí alespoò jednou skoèit zpìt.
101 Tedy její délka je alespoò $l+2$.
103 \figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.3\hsize}
105 Tedy ve vnitøním cyklu zaniknou v¹echny $st$-cesty délky $l$ a pøitom nevzniknou ¾ádné nové krat¹í $st$-cesty.
106 Proto délka nejkrat¹ích cest vzroste alespoò o 1.
109 \h{Implementaèní poznámky}
112 \:Není potøeba tak brutální èi¹tìní. Vrcholy se vstupním stupnìm 0 nám
113 nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl
114 havarovat postup v podkroku 9.
115 \:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e metodou HRRR na nì a kdy¾
116 to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí»
117 odstraòováním slepé ulièky.
118 \:U¾ pøi prohledáváni si rovnou udr¾ujeme minimum z rezerv a pøi zpáteèní cestì
119 opravujeme kapacity.\foot{Jak se asi zkombinuje s pøedchozím, kde musíme ustupovat?
120 V ka¾dé úrovni rekurze si zapamatujeme minimum, jaké bylo, kdy¾ jsme tam pøi¹li. Pokud
121 se vracíme, recyklujeme toto minimum.}
122 \:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit.
123 \:Kdy¾ budeme chtít hledat minimální øez, spustíme Dinicùv algoritmus, pak jednou iterací FF
124 algoritmu dostaneme jeden z minimálních øezù\foot{Samozøejmì získáme i maximální tok.}.
127 \s{Na pøemý¹lení:} Máme minimální øez. Jak zjistíme maximální tok?
129 \h{Speciální sítì (ubíráme na obecnosti)}
131 Dále se budeme vìnovat modifikacím algoritmu na speciální druhy sítí,
132 kde je mo¾né dostat lep¹í èasovou slo¾itost ne¾ v~obecném pøípadì.
134 \s{Jednotkové kapacity:}
135 V¹echny rezervy jsou jen 0 nebo~1. Na $st$-cestì má v¹echno kapacitu/rezervu~1.
136 Mù¾eme poslat~1~a rovnou celou cestu zahodit -- není potøeba si pamatovat minimum z~rezerv.
137 Kdy¾ máme $m$ hran, zlep¹eních po cestách délky $l$ bude maximálnì $m/l$.
138 Proto slo¾itost podkrokù 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
139 \foot{Nebo by ¹lo argumentovat, ¾e ka¾dou hranu pou¾ijeme jen $1\times$.}
140 Tedy pro jednotkové kapacity dostáváme slo¾itost $\O(nm)$.
142 \s{Jednotkové kapacity znovu a lépe:}
143 Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò $\O(m)$ pro èi¹tìní.
144 Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.
146 Sledujeme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusíme se odhadnout, kolik iterací
147 je¹tì algoritmus udìlá. Oznaème délku nejkrat¹í $st$-cesty $l$.
148 Víme, ¾e $l \geq k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.
150 Máme tok $f_k$ a chceme dostat maximální tok $f$. $f - f_k$ je tok v~síti rezerv.
151 Tedy $\exists f_R$ tok v síti rezerv takový, ¾e
152 zlep¹ení $f_k$ podle $f_R$ je $f$.
153 Ka¾dá iterace velkého cyklu zlep¹í $f_k$ alespoò o 1. Tedy nám zbývá je¹tì
154 nejvý¹e $\vert f_R \vert$ iterací.
155 Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem.
157 Najdeme v síti rezerv øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì.
158 Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální.}
159 Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí $k-1$ rozhraní mezi
160 $k$ vrstvami. Tedy existuje rozhraní vrstev
161 s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}.
162 Toto rozhraní je øez. Tedy existuje øez $C$, ¾e $\vert C\vert \leq m/k$
163 Algoritmu tedy zbývá maximálnì $m/k$ krokù.
164 Celkový poèet krokù je nejvý¹ $k + m/k$. Staèí zvolit $k = \sqrt{m}$. Poèet krokù
165 pak bude $\O(\sqrt{m})$.
167 Celkovì slo¾itost Dinicova algoritmu pro jednotkové kapacity znovu a lépe
168 je $\O(\sqrt{m} m) = \O(m^{3/2})$. Pomohli jsme si pro øídké grafy.
170 \s{Jednotkové kapacity a jeden ze stupòù roven 1:}
171 Úlohu hledání maximálního párování v bipartitním grafu lze
172 hezky pøevést na hledání maximálního toku. Z grafu se vytvoøí
173 sí» tak, ¾e v¹echny vrcholy jedné partity se napojí na $s$ a v¹echny
174 vrcholy druhé partity se napojí na $t$.\foot{$s,t$ jsou novì pøidané vrcholy.}
175 Na v¹echny hrany se dají jednotkové kapacity a orientace ka¾dé bude smìrem\foot{%
176 V¹echny hrany v bipartitním grafu se zorientují smìrem ke komponentì, kde je napojený
177 vrchol $t$. Hrany obsahující vrchol $t$ se zorientují smìrem do $t$. Hrany obsahující vrchol
178 $s$ se zorientují smìrem od $s$. Snad je to intuitivnì vidìt. Pro jistotu je nìkde okolo
179 obrázek popisované sítì.} k~$t$.
180 Najde se maximální tok a hrany v~toku tvoøí maximální párování. Proto mù¾e být
181 u¾iteèné zkoumat tento speciální pøípad sítí.
183 \figure{dinic-bipartitni.eps}{Sí» vzniklá z bipartitního grafu}{0.4\hsize}
185 Sí» se vyznaèuje tím, ¾e ka¾dý vrchol krom $s$ a $t$ má vstupní nebo výstupní stupeò 1.
186 Pro takovou sí» mù¾eme odhad je¹tì tro¹ku upravit. My¹lenka je stejná jako minule. Pokusíme
187 se nalézt v síti po $k$ krocích nìjaký malý øez. Místo rozhraní budeme hledat jednu malou
188 vrstvu a z malé vrstvy vytvoøíme malý øez. Pro ka¾dý vrchol z vrstvy vezmeme tu hranu,
189 která je ve svém smìru sama, a tím získáme øez.
191 \figure{dinic-vrcholrez.eps}{Øez podle vrcholù ve vrstvì}{0.2\hsize}
193 Tedy $\forall v \neq s,t: \min(\deg^-(v), \deg^+(v)) \leq 1$.
194 Po $k$ krocích máme $k$ vrstev. Tedy existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy\foot{Holubníkový princip.}.
195 Tedy existuje øez $C$, ¾e $\vert C\vert \leq n/k$, který získáme z vrstvy $\delta$ vý¹e popsaným postupem.
196 Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu. Algoritmus celkem udìlá $k + n/k$ krokù%
197 \foot{Mo¾ná chybí nìjaké $\pm1$, ale to nehraje roli.}. Staèí zvolit $k = \sqrt{n}$ a slo¾itost
198 celého algoritmu vyjde $\O(\sqrt{n}m)$\foot{Poèet iterací vnìj¹ího cyklu je $\O(\sqrt{n})$ a
199 vnitøní cyklus má $\O(m)$.}.
201 \s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
202 Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé\foot{Co do souètu
203 poètu vrcholù v obou vrstvách.} sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
205 Oznaème $s_i$ poèet vrcholù v $i$-té vrstvì. Souèet poètu vrcholù ve dvou
206 sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost
207 $$\sum_i t_i \leq 2\sum_i s_i \leq 2n {\rm .}$$
209 Tedy existuje $i$, ¾e $t_i \leq 2n/k$\foot{Holubníkový princip. Zase.}.
210 Tedy $\exists i: s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
211 $C$ a to je men¹í ne¾ $s_i \cdot s_{i+1}$.
212 Nejhor¹í pøípad je, kdy¾ $s_i = s_{i+1} = n/k$. Tedy $\vert C\vert \leq {(n/k)}^2$.
213 Pro jistotu je¹tì jednou v celku jako dlouhá nerovnost:
214 $$ \<\# hran mezi>\ s_i, s_{i+1} = \vert C\vert \leq s_i\cdot s_{i+1} \leq {(n/k)}^2 {\rm .}$$
215 Proto poèet iterací velkého cyklu je $\leq \<konstanta> + k + {(n/k)}^2$.
216 Chytøe zvolíme $k = n^{2/3}$. Slo¾itost celého algoritmu pak bude $\O(n^{2/3}m)$.
218 \s{Poslední odhad pro celoèíselné kapacity:}
219 Poslední\foot{Samozøejmì následuje je¹tì jeden algoritmus i s odhadem pro celoèíselné kapacity.
220 Ale to u¾ není pøímo Dinicùv algoritmus. Jen Dinice pou¾ívá jako podprogram.} odhad je zalo¾en na velikosti
221 maximálního toku $f$ a pøedpokladu celoèíselných kapacit.
222 Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát,
223 o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$.
224 Zlep¹ující cesta se tedy hledá maximálnì $\vert f\vert$ krát za celou dobu bìhu algoritmu.
225 Cestu najedeme v èase $\O(n)$. Celkem na hledání
226 cest spotøebujeme $\O(\vert f\vert n)$ za celou dobu bìhu algoritmu.
228 Nesmíme ale zapomenout na cleanupy. V jedné iteraci velkého cyklu stojí cleanupy $\O(m)$ a velkých
229 iterací je $\leq n$. Proto celková slo¾itost algoritmu je $\O(\vert f\vert n + nm)$
231 Pokud navíc budeme pøedpokládat omezení na maximální kapacitu hran $ \leq C$,
232 lze získat je¹tì jeden odhad tím, ¾e odhadneme maximální velikost toku jako $ \leq Cn$.
233 Co¾ lze odùvodnit napøíklad tak, ¾e z $s$ jde maximálnì $n$~hran\foot{Nepøedpokládáme multigraf.}
234 a kapacita ka¾dé je $ \leq C$. Proto celkový tok musí být $ \leq Cn$.
235 Dostaneme odhad $\O(Cn^2 + nm)$.
239 Základní my¹lenka je podobná, jako u algoritmu pro tøídìní dlouhých èísel postupnì po øádech pomocí
240 radix-sortu. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední%
241 \foot{Poslední cifrou myslíme nejménì významnou cifru.}
242 cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.
244 \figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.2\hsize}
246 V na¹em pøípadì budeme postupnì budovat sítì a v nich poèítat toky, a¾ nakonec získáme tok pro celou sí».
248 Pøedpokládejme celoèíselné kapacity. Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì
249 budeme zvìt¹ovat kapacity bit po bitu v binárním zápisu, a¾ k jejich skuteèné kapacitì.
250 Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus. Pomocí pøedchozího odhadu uká¾eme, ¾e jedno
251 volání Dinice nebude pøíli¹ drahé.
253 \figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.2\hsize}
255 Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lceil \log_2C \rceil$.
256 Postupnì budeme budovat sítì $G_i$ s kapacitami $C_i(e) = \lfloor {C(e) / 2^{k-i}} \rfloor$.
257 $G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu jako je nejvy¹¹í bit v binárním zápisu
258 její skuteèné kapacity. $G_k$ je pùvodní sí» $G$.
260 $$ C_{i+1}(e) = \left\{
262 2C_i(e), &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0} \cr
263 2C_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík je 1} \cr}
267 \figure{dinic-scaling-g.eps}{Sítì $G_0$, $G_1$ a $G_2$, jak vyjdou pro sí» z~pøedchozího obrázku}{0.8\hsize}
269 Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
270 ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace
271 a výsledného bude malý.
274 $$ \vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$$
277 Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{Minimaxová vìta.}.
278 Øez $R$ obsahuje $\leq m$ hran. V $G_{i}$ má øez $R$ kapacitu maximálnì $2\vert R\vert+m$.
279 Maximální tok je omezen ka¾dým øezem. Tedy i øezem $R$. Proto tok vzroste o $\leq m$.
281 Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Tok se bude poèítat $k$-krát.
282 Celková slo¾itost bude $\O(mn\log C)$.
287 $$\vbox{\halign{# \hfil \quad &# \hfil \cr
288 \it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip}
289 standardní &$\O(n^2m)$ \cr
290 jednotkové kapacity &$\O(nm)$ \cr
291 jednotkové kapacity podruhé &$\O(\sqrt{m}m) = \O(m^{3/2})$ \cr
292 jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}m)$ \cr
293 jednotkové kapacity veseleji &$\O(n^{2/3}m)$ \cr
294 celoèíselné kapacity &$\O(\vert f\vert n + nm)$ \cr
295 celoèíselné kapacity $ \leq C$ &$\O(Cn^2 + mn)$ \cr
296 celoèíselné kapacity $ \leq C$ &$\O(mn\log C)$ \cr
projects / ga.git / blob