From ad88da86da5673488698d68e259ba75a9c0018a7 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 31 Jan 2012 09:44:17 +0100 Subject: [PATCH] Dinic: Korektury a cviceni --- 3-dinic/3-dinic.tex | 85 +++++++++++++++++++++++++-------------------- 1 file changed, 47 insertions(+), 38 deletions(-) diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index 4dc6c11..45a076f 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -2,23 +2,23 @@ \prednaska{3}{Dinicùv algoritmus}{} -Na~minulé pøedná¹ce jsme si~ukázali Fordùv-Fulkersonùv algoritmus. Tento -algoritmus hledal maximální tok tak, ¾e zaèal s~tokem nulovým a~postupnì ho -zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít {\I nenasycenou cestu,} +V~minulé kapitole jsme ukázali Fordùv-Fulkersonùv algoritmus. Tento +algoritmus hledá maximální tok tak, ¾e zaène s~tokem nulovým a~postupnì ho +zvìt¹uje. Pro~ka¾dé zvìt¹ení potøebuje v~síti najít {\I nenasycenou cestu,} tedy takovou, na~ní¾ mají v¹echny hrany kladnou rezervu. Podél takové cesty -pak tok zvìt¹il. +pak tok zlep¹í. Ukázali jsme, ¾e tato cesta existuje právì tehdy, kdy¾ tok je¹tì není -maximální. Také jsme dokázali, ¾e pro racionální kapacity je tento +maximální. Také jsme dokázali, ¾e pro racionální kapacity je algoritmus koneèný a v¾dy najde maximální tok. V~obecném pøípadì to ov¹em mù¾e trvat velice dlouho. -Nyní uká¾eme trochu slo¾itìj¹í, ale výraznì rychlej¹í algoritmus zalo¾ený +Nyní uká¾eme trochu slo¾itìj¹í, ale výraznì rychlej¹í Dinicùv algoritmus zalo¾ený na my¹lence nezlep¹ovat toky pomocí cest, ale rovnou pomocí tokù~\dots \h{Sí» rezerv a zlep¹ující toky} -\s{Definice:} {\I Sí» rezerv} k~toku~$f$ v~síti $S=(V,E,z,s,c)$ je sí» $R(S,f)=(V,E,z,s,r)$, +\s{Definice:} {\I Sí» rezerv} k~toku~$f$ v~síti $S=(V,E,z,s,c)$ je sí» $R(S,f):=(V,E,z,s,r)$, kde~$r(e)$ je rezerva hrany~$e$ pøi toku~$f$. Je dùle¾ité si~uvìdomit, ¾e sí» rezerv konstruujeme pro konkrétní tok v~pùvodní síti. @@ -49,7 +49,7 @@ $$\eqalign{ f'(vu) &:= f(vu) - \delta \cr f'(uv) &:= f(uv) + g(uv) - \delta \cr }$$ -(Jinými slovy toté¾ jako pøi zlep¹ování toku ve~Fordovì-Fulkersonovì algoritmu.) +(To je vlastnì toté¾ jako pøi zlep¹ování toku ve~Fordovì-Fulkersonovì algoritmu.) {\I Proè je to tok:} Funkce~$f'$ jistì není na ¾ádné hranì záporná. Kapacity také nepøekroèí: na hranì~$vu$ tok pouze sni¾ujeme, na hranì~$uv$ ho zvý¹íme jen @@ -60,7 +60,7 @@ Proto $f'(uv) = f(uv) + g(uv) - \delta \le f(uv) + c(uv) - f(uv) + f(vu) - f(vu) Je¹tì ovìøíme, ¾e $f'$~splòuje Kirchhoffùv zákon. Uká¾eme, ¾e pro ka¾dý vrchol~$v$ platí $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$, tak¾e pokud zákon platil pro $f$ -i~$g$, musí platit i pro~$f'$. V¹imneme si, ¾e za hranu~$uv$ na¹e konstrukce zvý¹í +i~$g$, musí platit i pro~$f'$. Staèí si v¹imnout, ¾e za hranu~$uv$ na¹e konstrukce zvý¹í $f^\Delta(u)$ o~$-g(uv)$ a~$f^\Delta(v)$ o~$g(uv)$. To je pøesnì tolik, èím tato hrana pøispívá k~$g^\Delta(u)$ a~$g^\Delta(v)$. Pro hranu~$vu$, po které neteklo nic, platí triviálnì toté¾. @@ -82,10 +82,11 @@ Dinic tok pomocí nich zlep¹ovat, a¾ se dostane k~maximálnímu toku. Poèet potøebných iterací pøitom bude záviset na tom, jak \uv{kvalitní} pomocné toky se¾ene -- na jednu stranu bychom chtìli, aby byly podobné maximálnímu toku, na druhou stranu jejich výpoètem nechceme -trávit pøíli¹ mnoho èasu. Vhodným kompromisem jsou blokující toky: +trávit pøíli¹ mnoho èasu. Vhodným kompromisem jsou tzv. blokující toky: -\s{Definice:} Tok~$f$ je {\I blokující}, jestli¾e pro~ka¾dou orientovanou -cestu~$P$ ze~$z$ do~$s$ existuje hrana~$e \in P$, pro ní¾ $f(e) = c(e)$. +\s{Definice:} Tok je {\I blokující}, jestli¾e na~ka¾dé orientované +cestì ze~zdroje do~spotøebièe existuje alespoò jedna hrana, na ní¾ je +tok roven kapacitì. \s{Definice:} Sí» je {\I vrstevnatá (proèi¹tìná)}, pokud v¹echny její vrcholy a~hrany le¾í na~nejkrat¹ích cestách ze~$z$ do~$s$. (Abychom vyhovìli na¹í definici @@ -100,32 +101,33 @@ Proto se takov \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do~vrstev}{0.4\hsize} \algo{Dinic} +\algin Sí» $(V,E,c,z,s)$. \:$f \leftarrow \hbox{nulový tok.}$ \:Opakujeme: \::Sestrojíme sí» rezerv~$R$ a~sma¾eme hrany s~nulovou rezervou. \::$\ell \leftarrow$ délka nejkrat¹í cesty ze~$z$ do~$s$ v~$R$. -\::Pokud $l = \infty$, zastavíme se~a vrátíme~$f$. +\::Pokud $l = \infty$, zastavíme se~a vrátíme výsledek~$f$. \::Proèistíme sí»~$R$. \::$g \leftarrow \hbox{blokující tok v~$R$.}$ \::Zlep¹íme tok~$f$ pomocí~$g$. +\algout Maximální tok~$f$. \endalgo \proc{Èi¹tìníSítì} \:Rozdìlíme vrcholy do~vrstev podle vzdálenosti od~$z$. -\:Odstraníme vrstvy za~$s$ (tedy vrcholy vzdálenìj¹í ne¾~$\ell$). +\:Odstraníme vrstvy za~$s$ (tedy vrcholy ve~vzdálenosti vìt¹í ne¾~$\ell$). \:Odstraníme hrany do~pøedchozích vrstev a hrany uvnitø vrstev. -\:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^{out}(v) = 0$: -opakovanì pomocí fronty~$F$: -\::$F \leftarrow \{ v\ne s \mid \deg^{out}(v) = 0 \}.$ +\:Odstraníme \uv{slepé ulièky}, tedy vrcholy s~$\deg^-(v) = 0$: +\::$F \leftarrow \{ v\ne s \mid \deg^+(v) = 0 \}.$ \cmt{fronta vrcholù ke~smazání} \::Dokud $F\ne\emptyset$, opakujeme: -\:::Vezmeme vrchol~$v$ z~$F$. -\:::Sma¾eme~$v$ i v¹echny hrany, které do nìj vedou. -\:::Pokud nìjakému vrcholu klesl $\deg^{out}$ na~0, pøidáme ho do~$F$. +\:::Odebereme vrchol~$v$ z~$F$. +\:::Sma¾eme ze sítì vrchol~$v$ i v¹echny hrany, které do nìj vedou. +\:::Pokud nìjakému vrcholu klesl $\deg^+$ na~0, pøidáme ho do~$F$. \endalgo \figure{dinic-neprocistenasit.eps}{Neproèi¹tìná sí». Obsahuje zpìtné hrany, hrany uvnitø vrstvy a~slepé ulièky.}{0.45\hsize} -\s{Hledání blokujícího toku podrobnìji:} +\s{Jak nalézt blokující tok:} Zaèneme s~nulovým tokem~$g$ a budeme ho postupnì zlep¹ovat. Poka¾dé najdeme nìjakou orientovanou cestu ze~zdroje do stoku -- to se ve~vrstevnaté síti dìlá snadno, staèí vyrazit ze~zdroje a pak následovat libovolnou hranu. A¾ cestu najdeme, @@ -144,12 +146,14 @@ Cel \nobreak \proc{BlokujícíTok} +\algin Vrstevnatá sí»~$R$ s~rezervami~$r$. \:$g \leftarrow$ nulový tok. \:Dokud v~$R$ existuje orientovaná cesta~$P$ ze~$z$ do~$s$, opakujeme: \::$\varepsilon \leftarrow \min_{e \in P} \left(r(e) - g(e)\right)$. \::Pro v¹echny $e \in P: g(e) \leftarrow g(e) + \varepsilon$. -\::Pokud $g(e) = r(e)$, sma¾eme~$e$ z~$R$. +\::Pokud pro kteroukoliv~$e$ nastalo $g(e) = r(e)$, sma¾eme~$e$ z~$R$. \::Doèistíme sí» pomocí fronty. +\algout Blokující tok~$g$. \endalgo \h{Analýza Dinicova algoritmu} @@ -165,7 +169,7 @@ a ten, jak u Nyní rozebereme èasovou slo¾itost. Rozdìlíme si k~tomu úèelu algoritmus na {\I fáze} -- tak budeme øíkat jednotlivým prùchodùm vnìj¹ím cyklem. -Také budeme pøedpokládat, ¾e graf na vstupu neobsahuje izolované vrcholy, tak¾e +Také budeme pøedpokládat, ¾e sí» na vstupu neobsahuje izolované vrcholy, tak¾e $\O(n+m) = \O(m)$. \s{Lemma S (o~slo¾itosti fází):} Ka¾dá fáze trvá $\O(nm)$. @@ -180,9 +184,9 @@ po smaz nejvý¹e jednou za~fázi. Hledání blokujícího toku projde nejvý¹e~$m$ cest, proto¾e poka¾dé ze~sítì -vypadne alespoò jedna hrana a u¾ se tam nevrátí. Nalezení cesty metodou -\uv{rovnou za nosem} pøitom trvá $\O(n)$. Celkem tedy $\O(nm)$ plus èi¹tìní, -které jsme ale u¾ zapoèítali. +vypadne alespoò jedna hrana (ta, na ní¾ se v~kroku~3 nabývalo minimum) +a u¾ se tam nevrátí. Nalezení cesty metodou \uv{rovnou za nosem} pøitom trvá +$\O(n)$. Celkem tedy $\O(nm)$ plus èi¹tìní, které jsme ale u¾ zapoèítali. Celá jedna fáze proto dobìhne v~èase $\O(m + m + nm) = \O(nm)$. \qed @@ -198,8 +202,8 @@ Ozna s~nulovou rezervou, ale je¹tì pøed proèi¹tìním. Nech» nejkrat¹í cesta ze~$z$ do~$s$ v~$R_i$ je dlouhá~$\ell$. -Jak se li¹í~$R_{i+1}$ od $R_i$? Pøedev¹ím z~ka¾dé cesty délky~$\ell$ -jsme smazali alespoò jednu hranu: ka¾dá taková cesta toti¾ byla blokujícím +Jak se li¹í~$R_{i+1}$ od $R_i$? Pøedev¹ím jsme z~ka¾dé cesty délky~$\ell$ +smazali alespoò jednu hranu: ka¾dá taková cesta toti¾ byla blokujícím tokem zablokována, tak¾e alespoò jedné její hranì klesla rezerva na nulu, èím¾ hrana vypadla. ®ádná z~pùvodních cest délky~$\ell$ tedy ji¾ v~$R_{i+1}$ neexistuje. @@ -220,31 +224,36 @@ T \figure{dinic-cestashranouzpet.eps}{Cesta u¾ívající novou zpìtnou hranu}{0.4\hsize} -V¹echna dokázaná tvrzení mù¾eme shrnout do~následující vìty: - \s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(n^2m)$. \proof Jeliko¾ ka¾dá cesta obsahuje nejvý¹e~$n$ vrcholù, z~lemmatu~C plyne, ¾e fází probìhne nejvý¹e~$n$. Ka¾dá fáze podle lemmatu~S trvá $\O(nm)$, co¾ dává celkovou slo¾itost $\O(n^2m)$. Speciálnì se tedy algoritmus v¾dy zastaví, tak¾e podle -lemmatu~K o~korektnosti vydá maximální tok. +lemmatu~K vydá maximální tok. \qed -\ss{Pár poznámek na závìr:} - +\s{Poznámka:} Na rozdíl od~Fordova-Fulkersonova algoritmu jsme tentokrát nikde nevy¾adovali racionálnost kapacit -- odhad èasové slo¾itosti se o~kapacity vùbec neopírá. Nezávisle jsme tedy dokázali, ¾e i v~sítích s~iracionálními kapacitami v¾dy existuje alespoò jeden maximální tok. -V~sítích s~malými celoèíselnými kapacitami se algoritmus chová daleko lépe, +V~sítích s~malými celoèíselnými kapacitami se navíc algoritmus chová daleko lépe, ne¾ øíká ná¹ odhad. Snadno se dá dokázat, ¾e pro jednotkové kapacity dobìhne -v~èase $\O(nm)$ (stejnì jako Fordùv-Fulkersonùv). Uveïme bez dùkazu je¹tì +v~èase $\O(mn)$ (stejnì jako Fordùv-Fulkersonùv). Uveïme bez dùkazu je¹tì jeden silnìj¹í výsledek: v~síti vzniklé pøi hledání nejvìt¹ího párování -algoritmem z~minulé pøedná¹ky je slo¾itost Dinicova algoritmu omezena $\O(\sqrt -n \cdot m)$. +algoritmem z~minulé kapitoly Dinicùv algoritmus pracuje v~èase $\O(\sqrt n \cdot m)$. + +\exercises + +\ex{Doka¾te, ¾e pro jednotkové kapacity Dinicùv algoritmus dobìhne v~èase $\O(mn)$.} + +\ex{Blokující tok lze také sestrojit pomocí prohledávání do~hloubky. +Poka¾dé, kdy¾ projdeme hranou, pøepoèítáme prùbì¾né minimum. Pokud najdeme +stok, vracíme se do~koøene a upravujeme tok na~hranách. Pokud narazíme na slepou ulièku, +vrátíme se o~krok zpìt a sma¾eme hranu, po~ní¾ jsme pøi¹li. Doplòte detaily.} -%% FIXME: Dinic pomocí DFS +\endexercises \bye -- 2.39.2