2-dinic/2-dinic.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{2}{Dinicùv algoritmus a jeho varianty}{}
   4
   5 Maximální tok v~síti u¾ umíme najít pomocí Ford-Fulkersonova algoritmu
   6 z~minulé kapitoly. Nyní pojednáme pojednáme o~efektivnìj¹ím Dinicovì algoritmu
   7 a o~rùzných jeho variantách pro sítì ve~speciálním tvaru.
   8
   9 \h{Dinicùv algoritmus}
  10
  11 Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Ford-Fulkersonovì algoritmu
  12 nemusíme pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
  13 toky. Nejlépe toky takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok
  14 dostateènì obohatily. Vhodnými objekty k~tomuto úèelu jsou blokující toky:
  15
  16 \s{Definice:} {\I Blokující tok} je tok takový, ¾e ka¾dá orientovaná $st$-cesta
  17 obsahuje alespoò jednu nasycenou hranu. [Tj. takový tok, který by na¹el F-F algoritmus,
  18 kdyby neuva¾oval rezervy v~protismìru.]
  19
  20 \s{Algoritmus (Dinic):}
  21
  22 \algo
  23 \:Zaèneme s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
  24 \:Iterativnì vylep¹ujeme tok pomocí zlep¹ujících tokù: {\I (vnìj¹í cyklus)}
  25 \::Sestrojíme sí» rezerv: vrcholy a hrany jsou tyté¾, kapacity jsou urèeny rezervami v~pùvodní síti.
  26 Dále budeme pracovat s~ní.
  27 \::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèíme.
  28 \::Proèistíme sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách.
  29 \::Najdeme v~proèi¹tìné síti blokující tok $f_B$:
  30 \:::$f_B \leftarrow \<prázdný tok>$
  31 \:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)}
  32 \::::Najdeme $st$-cestu. Napø. hladovì -- \uv{rovnou za nosem}.
  33 \::::Po¹leme co nejvíce po~nalezené cestì.
  34 \::::Sma¾eme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky,
  35 èím¾ se zneèistí sí» a nebude fungovat hladové hledání cest.)
  36 \::::Doèistíme sí».
  37 \::Zlep¹íme $f$ podle $f_B$
  38 \endalgo
  39
  40 \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\hsize}
  41
  42 \s{Slo¾itost algoritmu:}
  43 Oznaème $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì.
  44
  45 \itemize\ibull
  46 \: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$.
  47 \:Vnitøní cyklus se provede maximálnì $m$-krát, proto¾e se v¾dy alespoò jedna hrana nasytí
  48   a ze sítì vypadne, tak¾e krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
  49 \:Èi¹tìní a doèi¹»ování sítì dohromady provedeme takto:
  50   \itemize\ibull
  51   \:Rozvrstvíme vrcholy podle vzdálenosti od $s$.
  52   \:Zaøízneme dlouhé cesty (del¹í, ne¾ do vrstvy obsahující $t$).
  53   \:Dr¾íme si frontu vrcholù, které mají $\deg^+ = 0$ èi $\deg^- = 0$.
  54   \:Vrcholy z~fronty vybíráme a zahazujeme vèetnì hran, které vedou do/z nich.
  55     A pøípadnì pøidáváme do~fronty vrcholy, kterým pøi tom klesl jeden ze stupòù na 0.
  56     Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
  57   \endlist
  58   Takto kroky 5 a 12 dohromady spotøebují èas $\O(m)$.
  59   \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
  60   \:Jak za chvíli doká¾eme, ka¾dým prùchodem vnìj¹ím cyklem $l$ vzroste, tak¾e prùchodù
  61     bude maximálnì~$n$ a celý algoritmus tak pobì¾í v~èase $\O(n^2m)$.
  62 \endlist
  63
  64 \s{Korektnost algoritmu:}
  65 Kdy¾ se Dinicùv algoritmus zastaví, nemù¾e u¾ existovat ¾ádná zlep¹ující cesta
  66 (viz krok~4) a tehdy, jak u¾ víme z~analýzy F-F algoritmu, je nalezený tok maximální.
  67
  68 \s{Vìta:}
  69 V~ka¾dém prùchodu Dinicova algoritmu vzroste $l$ alespoò~o~1.
  70
  71 \proof
  72 Podíváme se na~prùbìh jednoho prùchodu vnìj¹ím cyklem.
  73 Délku aktuálnì nejkrat¹í $st$-cesty oznaème~$l$.
  74 V¹echny pùvodní cesty délky~$l$ se bìhem prùchodu zaruèenì nasytí, proto¾e
  75 tok~$f_B$ je blokující. Musíme v¹ak dokázat, ¾e nemohou vzniknout ¾ádné
  76 nové cesty délky~$l$ nebo men¹í. V~síti rezerv toti¾ mohou hrany nejen
  77 ubývat, ale i pøibývat: pokud po¹leme tok po~hranì, po~které je¹tì nic
  78 neteklo, tak v~protismìru z~dosud nulové rezervy vyrobíme nenulovou.
  79 Rozmysleme si tedy, jaké hrany mohou pøibývat:
  80
  81 Vnìj¹í cyklus zaèíná s neproèi¹tìnou sítí. Pøíklad takové sítì je na~následujícím obrázku.
  82 Po~proèi¹tìní zùstanou v~síti jen èerné hrany, tedy hrany vedoucí z~$i$-té
  83 vrstvy do~$(i+1)$-ní. Èervené a modré\foot{Modré jsou ty, které vedou v rámci jedné vrstvy,
  84 èervené vedou zpìt èi za~spotøebiè èi do~slepých ulièek. Pøi vyti¹tìní na papír není snadné
  85 je barevnì odli¹it od~èerných.} se zahodí.
  86
  87 \figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.5\hsize}
  88
  89 Nové hrany mohou vznikat výhradnì jako opaèné k~èerným hranám (hrany ostatních barev
  90 padly za obì» proèi¹tìní). Jsou to tedy v¾dy zpìtné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní.
  91 Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které pou¾ívají
  92 zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit
  93 o~vrstvu zpìt a nikdy nemù¾e skoèit o~více ne¾ jednu vrstvu dopøedu, a~proto je její
  94 délka alespoò $l+2$. Tím je vìta dokázána. \qed
  95
  96 \figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize}
  97
  98 \h{Poznámky}
  99
 100 \itemize\ibull
 101 \:Není potøeba tak puntièkáøské èi¹tìní. Vrcholy se vstupním stupnìm 0 nám
 102    nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl
 103    havarovat postup v podkroku 9.
 104 \:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e prohledáváním do~hloubky:
 105    \uv{Hrrr na nì!} a kdy¾
 106    to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí»
 107    odstraòováním slepé ulièky.
 108 \:U¾ pøi prohledáváni si rovnou udr¾ujeme  minimum z rezerv a pøi zpáteèní cestì
 109    opravujeme kapacity. Snadno zkombinujeme s~prohledáváním do~hloubky.
 110 \:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit.
 111 \:Kdy¾ budeme chtít hledat minimální øez, spustíme po~Dinicovu algoritmu je¹tì jednu iterací F-F
 112    algoritmu.
 113 \endlist
 114
 115 \h{Speciální sítì (ubíráme na obecnosti)}
 116
 117 Pøi pøevodu rùzných úloh na~hledání maximálního toku èasto dostaneme sí» v~nìjakém
 118 speciálním tvaru -- tøeba s~omezenými kapacitami èi stupni vrcholù. Podíváme se
 119 proto podrobnìji na~chování Dinicova algoritmu v~takových pøípadech a uká¾eme,
 120 ¾e èasto pracuje pøekvapivì efektivnì.
 121
 122 \s{Jednotkové kapacity:}
 123 Pokud sí» neobsahuje cykly délky~1 (dvojice navzájem opaèných hran), v¹echny rezervy
 124 jsou jen 0 nebo~1. Pokud obsahuje, mohou rezervy být i dvojky, a~proto sí» upravíme tak,
 125 ¾e ke~ka¾dé hranì pøidáme hranu opaènou s~nulovou kapacitou a rezervu proti smìru
 126 toku pøiøkneme jí. Vzniknou tím sice paralelní hrany, ale to tokovým algoritmùm
 127 nikterak nevadí.%
 128 \foot{Èasto se to implementuje tak, ¾e protismìrné hrany vùbec nevytvoøíme a kdy¾
 129 hranu nasytíme, tak v~síti rezerv prostì obrátíme její orientaci.}
 130
 131 Pøi hledání blokujícího toku tedy budou mít v¹echny hrany na~nalezené $st$-cestì
 132 stejnou, toti¾ jednotkovou, rezervu, tak¾e v¾dy z~grafu odstraníme celou cestu.
 133 Kdy¾ máme $m$ hran, poèet zlep¹ení po cestách délky $l$ bude maximálnì $m/l$.
 134 Proto slo¾itost podkrokù 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
 135 \foot{Nebo by ¹lo argumentovat, tím ¾e ka¾dou hranu pou¾ijeme jen $1\times$.}
 136 Tedy pro jednotkové kapacity dostáváme slo¾itost $\O(nm)$.
 137
 138 \s{Jednotkové kapacity znovu a lépe:}
 139 Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò lineární èas pro èi¹tìní.
 140 Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.
 141
 142 Sledujme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusme se odhadnout, kolik iterací
 143 je¹tì algoritmus udìlá. Oznaème~$l$ délku nejkrat¹í $st$-cesty.
 144 Víme, ¾e $l>k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.
 145
 146 Máme tok $f_k$ a chceme dostat maximální tok $f$. Rozdíl $f-f_k$ je tok v~síti rezerv
 147 (tok v~pùvodní síti to ov¹em být nemusí!), oznaème si ho~$f_R$.
 148 Ka¾dá iterace velkého cyklu zlep¹í $f_k$ alespoò o 1. Tedy nám zbývá je¹tì
 149 nejvý¹e $\vert f_R \vert$ iterací.
 150 Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem.
 151
 152 Najdeme v síti rezerv nìjaký dost malý øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì.
 153 Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální. {\sl (odposlechnuto na~pøedná¹ce)}}
 154 Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí alespoò $k$ rozhraní mezi
 155 vrstvami. Tedy existuje rozhraní vrstev
 156 s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}.
 157 Toto rozhraní je øez. Tedy existuje øez~$C$, pro nìj¾ $\vert C\vert \leq m/k$,
 158 a~algoritmu zbývá maximálnì $m/k$ dal¹ích krokù.
 159 Celkový poèet krokù je nejvý¹ $k + m/k$, tak¾e staèí zvolit $k = \sqrt{m}$ a získáme
 160 odhad na~poèet krokù $\O(\sqrt{m})$.
 161
 162 Tím jsme dokázali, ¾e celková slo¾itost Dinicova algoritmu pro jednotkové
 163 kapacity je $\O(m^{3/2})$. Tím jsme si pomohli pro øídké grafy.
 164
 165 \s{Jednotkové kapacity a jeden ze stupòù roven 1:}
 166 Úlohu hledání maximálního párování v~bipartitním grafu, pøípadnì hledání
 167 vrcholovì disjunktních cest v~obecném grafu lze pøevést (viz pøedchozí kapitola)
 168 na~hledání maximálního toku v~síti, v~ní¾ má ka¾dý vrchol~$v\ne s,t$ buïto vstupní
 169 nebo výstupní stupeò roven jedné.
 170 Pro takovou sí» mù¾eme pøedchozí odhad je¹tì tro¹ku upravit. Pokusíme
 171 se nalézt v síti po~$k$~krocích nìjaký malý øez. Místo rozhraní budeme hledat jednu malou
 172 vrstvu a z malé vrstvy vytvoøíme malý øez tak, ¾e pro ka¾dý vrchol z vrstvy vezmeme tu hranu,
 173 která je ve svém smìru sama.
 174
 175 \figure{dinic-vrcholrez.eps}{Øez podle vrcholù ve vrstvì}{0.2\hsize}
 176
 177 Po $k$ krocích máme alespoò $k$ vrstev, a~proto existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy.
 178 Tedy existuje øez $C$ o~velikosti $\vert C\vert \leq n/k$ (získáme z vrstvy $\delta$ vý¹e popsaným postupem).
 179 Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu, celkem tedy udìlá $k + n/k$ iterací.
 180 Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
 181 celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$.
 182
 183 \s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
 184 Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé
 185 sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.
 186 Budeme tentokrát pøedpokládat, ¾e na¹e sí» není multigraf, pøípadnì ¾e
 187 násobnost hran je alespoò omezena konstantou.
 188
 189 Oznaème $s_i$ poèet vrcholù v $i$-té vrstvì. Souèet poètu vrcholù ve dvou
 190 sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost:
 191 $$\sum_i t_i \leq 2\sum_i s_i \leq 2n.$$
 192 Podle holubníkového principu existuje $i$ takové, ¾e $t_i \leq 2n/k$, èili
 193 $s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
 194 $C$, a to je shora omezeno $s_i \cdot s_{i+1}$. Nejhor¹í pøípad nastane, kdy¾ $s_i = s_{i+1} = n/k$,
 195 a~proto $\vert C\vert \leq {(n/k)}^2$.
 196 Proto poèet iterací velkého cyklu je $\leq k + {(n/k)}^2$.
 197 Chytøe zvolíme $k = n^{2/3}$. Slo¾itost celého algoritmu pak bude $\O(n^{2/3}m)$.
 198
 199 \s{Obecný odhad pro celoèíselné kapacity:}
 200 Tento odhad je zalo¾en na velikosti
 201 maximálního toku $f$ a pøedpokladu celoèíselných kapacit.
 202 Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát,
 203 o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$.
 204 Zlep¹ující cesta se tedy hledá maximálnì  $\vert f\vert$-krát za celou dobu bìhu algoritmu.
 205 Cestu najedeme v èase $\O(n)$. Celkem na~hledání
 206 cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu.
 207
 208 Nesmíme ale zapomenout na èi¹tìní. V jedné iteraci velkého cyklu nás stojí èi¹tìní $\O(m)$ a velkých
 209 iterací je $\leq n$. Proto celková slo¾itost algoritmu èiní $\O(\vert f\vert n + nm)$
 210
 211 Pokud navíc budeme pøedpokládat, ¾e kapacita hran je nejvý¹e~$C$ a $G$ není multigraf,
 212 mù¾eme vyu¾ít toho, ¾e $\vert f\vert \le Cn$ (omezeno øezem okolo~$s$) a získat odhad
 213 $\O(Cn^2 + nm)$.
 214
 215 \h{Scaling kapacit}
 216
 217 Pokud jsou kapacity hran vìt¹í celá èísla omezená nìjakou konstantou~$C$, mù¾eme si pomoci následujícím algoritmem.
 218 Jeho základní my¹lenka je podobná, jako u~tøídìní èísel postupnì po øádech pomocí
 219 radix-sortu neboli pøihrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední
 220 (nejménì významné) cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.
 221
 222 \figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.4\hsize}
 223
 224 V na¹em pøípadì budeme postupnì budovat sítì èím dál podobnìj¹í zadané
 225 síti a v~nich poèítat toky, a¾ nakonec získáme tok pro ni.
 226
 227 Pøesnìji: Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì
 228 budeme zvìt¹ovat kapacity bit po bitu v~binárním zápisu a¾ k~jejich skuteèné kapacitì.
 229 Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus, aby dopoèítal maximální tok.
 230 Pomocí pøedchozího odhadu uká¾eme, ¾e jeden takový krok nebude pøíli¹ drahý.
 231
 232 \figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.4\hsize}
 233
 234 Oznaème $k$ index nejvy¹¹ího bitu v~zápisu kapacit v~zadané síti ($k = \lfloor \log_2C \rfloor$).
 235 Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$.
 236 $G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu rovnou nejvy¹¹ímu bitu v~binárním zápisu
 237 její skuteèné kapacity, a¾ $G_k$ je pùvodní sí» $G$.
 238
 239 $$ c_{i+1}(e) = \left\{
 240 \eqalign{
 241            2c_i(e),   &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0}  \cr
 242            2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík je 1}  \cr}
 243 \right.
 244 $$
 245
 246 \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.9\hsize}
 247
 248 Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
 249 ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace
 250 a výsledného bude malý, toti¾:
 251
 252 \s{Lemma:} $\vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$
 253
 254 \proof
 255 Vezmeme minimální øez $R$ v~$G_{i-1}$. Podle F-F vìty víme, ¾e $\vert f_{i-1}\vert = \vert R\vert$.
 256 Øez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentý¾ øez kapacitu maximálnì $2\vert R\vert+m$.
 257 Maximální tok je omezen ka¾dým øezem, tedy i øezem $R$, a~proto tok vzroste nejvý¹e o~$m$.
 258 \qed
 259
 260 Podle pøedchozího odhadu pro celoèíselné kapacity výpoèet toku $f_i$ trvá $\O(mn)$.
 261 Takový tok se bude poèítat $k$-krát, proèe¾ celková slo¾itost vyjde $\O(mn\log C)$.
 262
 263 \h{Pøehled variant Dinicova algoritmu}
 264
 265 \medskip
 266
 267 \centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr
 268 \it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip}
 269 standardní                              &$\O(n^2m)$      \cr
 270 jednotkové kapacity                     &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$   \cr
 271 jednotkové kapacity, 1 stupeò $\leq 1$  &$\O(\sqrt{n}\cdot m)$   \cr
 272 jednotkové kapacity, prostý graf        &$\O(n^{2/3}m)$    \cr
 273 celoèíselné kapacity                    &$\O(\vert f\vert\cdot n + nm)$     \cr
 274 celoèíselné kapacity $ \leq C$          &$\O(Cn^2 + mn)$   \cr
 275 celoèíselné kapacity $ \leq C$ (scaling)&$\O(mn\log C)$    \cr
 276 }}}
 277
 278 \bye