Revize 2. kapitoly.

[ga.git] / 2-dinic / 2-dinic.tex

\input ../sgr.tex

\prednaska{2}{Dinicùv algoritmus a jeho varianty}{zapsal Bernard Lidický}

\h{Dinicùv algoritmus}

Dinicùv algoritmus je zalo¾en na my¹lence, ¾e ve Ford-Fulkersonovì algoritmu
není potøeba pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující
toky, nejlépe takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok
     dostateènì zlep¹ovaly. Vhodnými objekty k~tomuto úèelu jsou:

\s{Definice:} {\I Blokující tok} je tok takový, ¾e ka¾dá orientovaná $st$-cesta
obsahuje alespoò jednu nasycenou hranu. [Tj. takový tok, který by na¹el F-F algoritmus,
kdyby neuva¾oval rezervy v~protismìru.]

\s{Algoritmus (Dinic):}

\algo
\:Zaèni s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým).
\:Iterativnì vylep¹uj tok podle zlep¹ujících tokù v síti rezerv: {\I (vnìj¹í cyklus)}
\::Sestroj sí» rezerv.
\::Najdi nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèi.
\::Proèisti sí», tj. nech v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách.
\::Najdi blokující tok $f_B$:
\:::$f_B \leftarrow \<prázdný tok>$
\:::Postupnì pøidáváme $st$-cesty: {\I (vnitøní cyklus)}
\::::Najdi $st$-cestu. Napø. hladovì metodou rovnou za nosem.
\::::Po¹li co nejvíce po cestì.
\::::Sma¾ nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky,
èím¾ se zneèistí sí» a nebude fungovat metoda rovnou za nosem.)
\::::Doèisti sí».
\::Zlep¹i $f$ podle $f_B$
\endalgo

\figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.3\hsize}

\s{Slo¾itost algoritmu:}
Oznaèíme $l$ délku nejkrat¹í $st$-cesty, $n$ poèet vrcholù sítì a $m$ poèet hran sítì.

\itemize\ibull
\: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$.
\:Vnitøní cyklus se provede maximálnì $m$-krát, proto¾e se v¾dy alespoò jedna hrana nasytí
  a ze sítì vypadne, tak¾e krok~6 mimo podkroku~12 bude trvat $\O(mn)$.
\:Èi¹tìní a doèi¹»ování sítì dohromady provedeme takto:
  \itemize\ibull
  \:Rozvrstvíme vrcholy do vrstev podle vzdálenosti od $s$.
  \:Zaøízneme dlouhé cesty (del¹í, ne¾ do vrstvy obsahující $t$).
  \:Dr¾íme si frontu vrcholù, které mají $\deg^+ = 0$ èi $\deg^- = 0$.
  \:Vrcholy z~fronty vybíráme a zahazujeme vèetnì hran, které vedou do/z nich.
    A pøípadnì pøidáváme do~fronty vrcholy, kterým klesl jeden ze stupòù na 0
    pøi vyhazování hran. Vyma¾ou se tím slepé ulièky, které by vadily v podkroku~9.
  \endlist
  Tedy kroky 5 a 12 dohromady spotøebují èas $\O(m)$.
  \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$.
\endlist

\s{Vìta:}
V~ka¾dém prùchodu Dinicova algoritmu vzroste $l$ alespoò~o~1.

\s{Dùsledek:}
Vnìj¹ím cyklem projdeme $\O(n)$ krát, proto¾e nejdel¹í cesta bude mít
délku $\leq n$. Celková slo¾itost algoritmu tedy bude $\O(n^2m)$

\s{Korektnost algoritmu:}
Korektnost Dinicova algoritmu plyne z korektnosti F-F algoritmu. Kdy¾ se Dinicùv
algoritmus zastaví, musí vydat maximální tok. Pokud ne, tak podle F-F algoritmu
existuje zlep¹ující cesta, ale to je ve sporu s~krokem~4, který po¾aduje, ¾e ¾ádná
zlep¹ující cesta neexistuje.

\s{Dùkaz vìty:}
Podíváme se na~prùbìh jednoho prùchodu vnìj¹ím cyklem.
Délku aktuálnì nejkrat¹í $st$-cesty oznaème~$l$.
V¹echny pùvodní cesty délky~$l$ se bìhem prùchodu zaruèenì nasytí, proto¾e
tok~$f_B$ je blokující. Musíme v¹ak dokázat, ¾e nemohou vzniknout ¾ádné
nové cesty délky~$l$ nebo men¹í. V~síti rezerv toti¾ mohou hrany nejen
ubývat, ale i pøibývat: pokud po¹leme tok po~hranì, po~které je¹tì nic
neteklo, mù¾e se stát, ¾e v~protismìru z~dosud nulové rezervy vyrobíme
nenulovou. Rozmysleme si tedy, jaké hrany mohou pøibývat:

Vnìj¹í cyklus zaèíná s neproèi¹tìnou sítí. Pøíklad takové sítì je na obrázku nìkde
okolo. Po proèi¹tìní zùstanou v~síti jen èerné hrany, tedy hrany vedoucí z~$i$-té
vrstvy do~$(i+1)$-ní. Èervené a modré\foot{Modré jsou ty, které vedou v rámci jedné vrstvy,
èervené vedou zpìt èi za~spotøebiè èi do~slepých ulièek. Pøi vyti¹tìní na papír není snadné
je barevnì odli¹it od èerných.} se zahodí.

\figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a slepé ulièky.}{0.3\hsize}

Nové hrany mohou vznikat výhradnì jako opaèné k~èerným hranám (hrany ostatních barev
padly za obì» proèi¹tìní). Jsou to tedy v¾dy zpìtné hrany vedoucí z~$i$-té vrstvy do~$(i-1)$-ní.

\figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.3\hsize}

Vznikem nových hran by proto mohly vzniknout nové $st$-cesty, které pou¾ívají
zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit zpìt
a nikdy nemù¾e skoèit dopøedu o~více ne¾ jednu vrstvu, a~proto je její délka alespoò $l+2$.
Tím je vìta dokázána. \qed

\figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.3\hsize}

\h{Implementaèní poznámky}

\itemize\ibull
\:Není potøeba tak brutální èi¹tìní. Vrcholy se vstupním stupnìm 0 nám
   nevadí -- stejnì se do nich nedostaneme. Vadí jen vrcholy s výstupním stupnìm 0, kde by mohl
   havarovat postup v podkroku 9.
\:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e metodou Hrrr na nì a kdy¾
   to nevyjde (dostaneme se do slepé ulièky), kus ustoupíme a pøi ústupu èistíme sí»
   odstraòováním slepé ulièky.
\:U¾ pøi prohledáváni si rovnou udr¾ujeme  minimum z rezerv a pøi zpáteèní cestì
   opravujeme kapacity.\foot{Jak se asi zkombinuje s pøedchozím, kde musíme ustupovat?
   V ka¾dé úrovni rekurze si zapamatujeme minimum, jaké bylo, kdy¾ jsme tam pøi¹li. Pokud
   se vracíme, recyklujeme toto minimum.}
\:V prùbìhu výpoètu udr¾ujeme jen sí» rezerv a tok vypoèteme a¾ nakonec z rezerv a kapacit.
\:Kdy¾ budeme chtít hledat minimální øez, spustíme po~Dinicovu algoritmu je¹tì jednu iterací F-F
   algoritmu.
\endlist

\h{Speciální sítì (ubíráme na obecnosti)}

Dále se budeme vìnovat modifikacím Dinicova algoritmu na speciální druhy sítí,
kde je mo¾né dostat lep¹í èasovou slo¾itost ne¾ v~obecném pøípadì.

\s{Jednotkové kapacity:}
V¹echny rezervy jsou jen 0 nebo~1. Na $st$-cestì má v¹echno kapacitu/rezervu~1.
Mù¾eme poslat~1~a rovnou celou cestu zahodit -- není potøeba si pamatovat minimum z~rezerv.
Kdy¾ máme $m$ hran, poèet zlep¹ení po cestách délky $l$ bude maximálnì $m/l$.
Proto slo¾itost podkrokù 9, 10 a 11 bude $m/l \cdot \O(l) = \O(m)$.%
\foot{Nebo by ¹lo argumentovat, ¾e ka¾dou hranu pou¾ijeme jen $1\times$.}
Tedy pro jednotkové kapacity dostáváme slo¾itost $\O(nm)$.

\s{Jednotkové kapacity znovu a lépe:}
Vnitøní cyklus lépe udìlat nepùjde. Je potøeba alespoò lineární èas pro èi¹tìní.
Mù¾eme se ale pokusit lépe odhadnout poèet iterací vnìj¹ího cyklu.

Sledujme stav sítì po $k$ iteracích vnìj¹ího cyklu a pokusme se odhadnout, kolik iterací
je¹tì algoritmus udìlá. Oznaème~$l$ délku nejkrat¹í $st$-cesty.
Víme, ¾e $l>k$, proto¾e v ka¾dé iteraci vzroste $l$ alespoò o 1.

Máme tok $f_k$ a chceme dostat maximální tok $f$. Rozdíl $f-f_k$ je tok v~síti rezerv
(tok v~pùvodní síti to ov¹em být nemusí!), oznaème si ho~$f_R$.
Ka¾dá iterace velkého cyklu zlep¹í $f_k$ alespoò o 1. Tedy nám zbývá je¹tì
nejvý¹e $\vert f_R \vert$ iterací.
Proto bychom chtìli omezit velikost toku $f_R$. Napøíklad øezem.

Najdeme v síti rezerv øez $C$. Kde ho vzít?\foot{Pøeci v øeznictví. Kdepak, spí¹e v cukrárnì.
Myslíte, ¾e v cukrárnì mají Dinicovy øezy? Myslím, ¾e v cukrárnì je vìt¹ina øezù minimální.}
Poèítejme jen hrany zleva doprava. Tìch je jistì nejvý¹e $m$ a tvoøí alespoò $k$ rozhraní mezi
vrstvami. Tedy existuje rozhraní vrstev
s~nejvý¹e $m/k$ hranami\foot{Princip holubníku a nìjaká ta $\pm1$.}.
Toto rozhraní je øez. Tedy existuje øez $C$, pro nìj¾ $\vert C\vert \leq m/k$,
a~algoritmu zbývá maximálnì $m/k$ dal¹ích krokù.
Celkový poèet krokù je nejvý¹ $k + m/k$, tak¾e staèí zvolit $k = \sqrt{m}$ a získáme
odhad na~poèet krokù $\O(\sqrt{m})$.

Celkovì slo¾itost Dinicova algoritmu pro jednotkové kapacity znovu a lépe
je $\O(\sqrt{m} \cdot m) = \O(m^{3/2})$. Pomohli jsme si pro øídké grafy.

\s{Jednotkové kapacity a jeden ze stupòù roven 1:}
Úlohu hledání maximálního párování v~bipartitním grafu, pøípadnì hledání
vrcholovì disjunktních cest v~obecném grafu lze pøevést (viz pøedchozí kapitola)
na~hledání maximálního toku v~síti, v~ní¾ $\forall v \neq s,t: \min(\deg^-(v), \deg^+(v)) \leq 1$.
Pro takovou sí» mù¾eme odhad je¹tì tro¹ku upravit. My¹lenka je stejná jako minule. Pokusíme
se nalézt v síti po $k$ krocích nìjaký malý øez. Místo rozhraní budeme hledat jednu malou
vrstvu a z malé vrstvy vytvoøíme malý øez: Pro ka¾dý vrchol z vrstvy vezmeme tu hranu,
která je ve svém smìru sama.

\figure{dinic-vrcholrez.eps}{Øez podle vrcholù ve vrstvì}{0.2\hsize}

Po $k$ krocích máme alespoò $k$ vrstev. Tedy existuje vrstva $\delta$ s nejvý¹e $n/k$ vrcholy.
Tedy existuje øez $C$ o~velikosti $\vert C\vert \leq n/k$ (získáme z vrstvy $\delta$ vý¹e popsaným postupem).
Algoritmu zbývá do konce $\leq n/k$ iterací vnìj¹ího cyklu, celkem tedy udìlá $k + n/k$ krokù.
Nyní staèí zvolit $k = \sqrt{n}$ a slo¾itost
celého algoritmu vyjde $\O(\sqrt{n}\cdot m)$\foot{Poèet iterací vnìj¹ího cyklu je $\O(\sqrt{n})$ a
vnitøní cyklus má $\O(m)$.}.

\s{Tøetí pokus pro jednotkové kapacity bez omezení na stupnì vrcholù v síti:}
Hlavní my¹lenkou je opìt po $k$ krocích najít nìjaký malý øez. Najdeme dvì malé
sousední vrstvy a v¹echny hrany mezi nimi budou tvoøit námi hledaný malý øez.

Oznaème $s_i$ poèet vrcholù v $i$-té vrstvì. Souèet poètu vrcholù ve dvou
sousedních vrstvách oznaèíme $t_i = s_i + s_{i+1}$. Bude tedy platit nerovnost:
$$\sum_i t_i \leq 2\sum_i s_i \leq 2n.$$
Podle holubníkového principu existuje $i$ takové, ¾e $t_i \leq 2n/k$, èili
$s_i + s_{i+1} \leq 2n/k$. Poèet hran mezi $s_i$ a $s_{i+1}$ je velikost øezu
$C$, a to je shora omezeno $s_i \cdot s_{i+1}$. Nejhor¹í pøípad nastane, kdy¾ $s_i = s_{i+1} = n/k$,
a~proto $\vert C\vert \leq {(n/k)}^2$.
Proto poèet iterací velkého cyklu je $\leq k + {(n/k)}^2$.
Chytøe zvolíme $k = n^{2/3}$. Slo¾itost celého algoritmu pak bude $\O(n^{2/3}m)$.

\s{Obecný odhad pro celoèíselné kapacity:}
Tento odhad je zalo¾en na velikosti
maximálního toku $f$ a pøedpokladu celoèíselných kapacit.
Za jednu iteraci velkého cyklu projdeme malým cyklem maximálnì tolikrát,
o kolik se v nìm zvedl tok, proto¾e ka¾dá zlep¹ující cesta ho zvedne alespoò o $1$.
Zlep¹ující cesta se tedy hledá maximálnì  $\vert f\vert$-krát za celou dobu bìhu algoritmu.
Cestu najedeme v èase $\O(n)$. Celkem na hledání
cest spotøebujeme $\O(\vert f\vert\cdot n)$ za celou dobu bìhu algoritmu.

Nesmíme ale zapomenout na cleanupy. V jedné iteraci velkého cyklu stojí cleanupy $\O(m)$ a velkých
iterací je $\leq n$. Proto celková slo¾itost algoritmu èiní $\O(\vert f\vert n + nm)$

Pokud navíc budeme pøedpokládat, ¾e kapacita hran je nejvý¹e~$C$ a $G$ není multigraf,
mù¾eme vyu¾ít toho, ¾e $\vert f\vert \le Cn$ (omezeno øezem okolo~$s$) a získat odhad
$\O(Cn^2 + nm)$.

\h{Scaling kapacit}

Základní my¹lenka je podobná, jako u algoritmu pro tøídìní dlouhých èísel postupnì po øádech pomocí
radix-sortu. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední%
\foot{Poslední cifrou myslíme nejménì významnou cifru.}
cifry, poté podle pøedposlední, pøedpøedposlední a tak dále.

\figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.2\hsize}

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í».

Pøedpokládejme celoèíselné kapacity. Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì
budeme zvìt¹ovat kapacity bit po bitu v binárním zápisu a¾ k jejich skuteèné kapacitì.
Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus. Pomocí pøedchozího odhadu uká¾eme, ¾e jedno
volání Dinice nebude pøíli¹ drahé.

\figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.2\hsize}

Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lfloor \log_2C \rfloor$.
Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$.
$G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu rovnou nejvy¹¹ímu bitu v~binárním zápisu
její skuteèné kapacity. $G_k$ je pùvodní sí» $G$.

$$ c_{i+1}(e) = \left\{
\eqalign{
           2c_i(e),   &\hbox{\quad pokud $(k-i-1)$-tý bitík je 0}  \cr
           2c_i(e)+1, &\hbox{\quad pokud $(k-i-1)$-tý bitík je 1}  \cr}
\right.
$$

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

Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus,
ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace
a výsledného bude malý, toti¾:
$$ \vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$$

\s{Dùkaz:}
Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{F-F vìta.}.
Øez $R$ obsahuje $\leq m$ hran. V $G_{i}$ má øez $R$ kapacitu maximálnì $2\vert R\vert+m$.
Maximální tok je omezen ka¾dým øezem. Tedy i øezem $R$. Proto tok vzroste o $\leq m$.
\qed

Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Takový tok se bude poèítat $k$-krát,
tak¾e celková slo¾itost vyjde $\O(mn\log C)$.

\h{Dinicova tabulka}

$$\vbox{\halign{# \hfil \quad &# \hfil \cr
\it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip}
standardní                              &$\O(n^2m)$      \cr
jednotkové kapacity                     &$\O(nm)$        \cr
jednotkové kapacity podruhé             &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$   \cr
jednotkové kapacity, 1 stupeò $\leq 1$  &$\O(\sqrt{n}\cdot m)$   \cr
jednotkové kapacity veseleji            &$\O(n^{2/3}m)$    \cr
celoèíselné kapacity                    &$\O(\vert f\vert\cdot n + nm)$     \cr
celoèíselné kapacity $ \leq C$          &$\O(Cn^2 + mn)$   \cr
celoèíselné kapacity $ \leq C$          &$\O(mn\log C)$    \cr
}}$$

\bye