From 5ca3fe2ae5c77bc5326598db4e3c207152c6c63f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 23 Jan 2007 00:44:25 +0100 Subject: [PATCH] Revize prvni pulky Dinicova algoritmu. Jen kosmeticke zmeny. --- 2-dinic/2-dinic.tex | 80 ++++++++++++++++++++++----------------------- 1 file changed, 40 insertions(+), 40 deletions(-) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 62016ce..58cba61 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -2,15 +2,16 @@ \prednaska{2}{Dinicùv algoritmus a jeho varianty}{} -V~této kapitole pojednáme o~Dinicovì algoritmu na~výpoèet maximálního -toku a o~rùzných jeho variantách pro sítì ve~speciálním tvaru. +Maximální tok v~síti u¾ umíme najít pomocí Ford-Fulkersonova algoritmu +z~minulé kapitoly. Nyní pojednáme pojednáme o~efektivnìj¹ím Dinicovì algoritmu +a o~rùzných jeho variantách pro sítì ve~speciálním tvaru. \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: +Dinicùv algoritmus je zalo¾en na~následující my¹lence: Ve~Ford-Fulkersonovì algoritmu +nemusíme pøièítat jen zlep¹ující cesty, ale je mo¾né pøièítat rovnou zlep¹ující +toky. Nejlépe toky takové, aby je nebylo obtí¾né najít, a~pøitom aby pùvodní tok +dostateènì obohatily. Vhodnými objekty k~tomuto úèelu jsou blokující toky: \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, @@ -19,26 +20,26 @@ kdyby neuva \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 v~proèi¹tìné síti blokující tok $f_B$: +\:Zaèneme s~libovolným tokem~$f$, napøíklad prázdným (v¹ude nulovým). +\:Iterativnì vylep¹ujeme tok pomocí zlep¹ujících tokù: {\I (vnìj¹í cyklus)} +\::Sestrojíme sí» rezerv: vrcholy a hrany jsou tyté¾, kapacity jsou urèeny rezervami v~pùvodní síti. +\::Najdeme nejkrat¹í $st$-cestu. Kdy¾ ¾ádná neexistuje, skonèime. +\::Proèistime sí», tj. ponecháme v ní pouze vrcholy a hrany na nejkrat¹ích $st$-cestách. +\::Najdeme v~proèi¹tìné síti blokující tok $f_B$: \:::$f_B \leftarrow \$ \:::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$ +\::::Najdeme $st$-cestu. Napø. hladovì -- \uv{rovnou za nosem}. +\::::Po¹leme co nejvíce po~nalezené cestì. +\::::Sma¾eme nasycené hrany. (Pozor, smazáním hran mohou vzniknout slepé ulièky, +èím¾ se zneèistí sí» a nebude fungovat hladové hledání cest.) +\::::Doèistíme sí». +\::Zlep¹ime $f$ podle $f_B$ \endalgo \figure{dinic-cistasit.eps}{Proèi¹tìná sí» rozdìlená do vrstev}{0.4\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ì. +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$. @@ -46,14 +47,14 @@ Ozna 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$. + \:Rozvrstvíme vrcholy 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. + A pøípadnì pøidáváme do~fronty vrcholy, kterým pøi tom klesl jeden ze stupòù na 0. + 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)$. + Takto kroky 5 a 12 dohromady spotøebují èas $\O(m)$. \:Jeden prùchod vnìj¹ím cyklem tedy trvá $\O(mn)$. \endlist @@ -61,14 +62,14 @@ Ozna 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)$ +Vnìj¹ím cyklem projdeme $\O(n)$-krát, proto¾e nejdel¹í cesta bude mít +délku $\leq n$. Celková slo¾itost celého algoritmu proto bude $\O(n^2m)$ -\s{Korektnost algoritmu:} -Korektnost Dinicova algoritmu plyne z korektnosti F-F algoritmu. Kdy¾ se Dinicùv +\s{Korektnost 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. +existuje zlep¹ující cesta, ale to je ve sporu s~krokem~4, který po¾aduje, aby ¾ádná +taková cesta neexistovala. \s{Dùkaz vìty:} Podíváme se na~prùbìh jednoho prùchodu vnìj¹ím cyklem. @@ -80,11 +81,11 @@ ub 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é +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. +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í. +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.5\hsize} @@ -94,25 +95,24 @@ padly za ob \figure{dinic-zpetnahrana.eps}{Vznik nové zpìtné hrany}{0.4\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 +zpìtné hrany. Jen¾e $st$-cesta, která pou¾ije zpìtnou hranu, musí alespoò jednou skoèit +o~vrstvu zpìt a nikdy nemù¾e skoèit o~více ne¾ jednu vrstvu dopøedu, 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.4\hsize} -\h{Implementaèní poznámky} +\h{Poznámky} \itemize\ibull \:Není potøeba tak puntíèkáøské è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¾ +\:Je mo¾né dìlat prohledávání a èi¹tìní souèasnì. Jednodu¹e prohledáváním do~hloubky: + \uv{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.} + opravujeme kapacity. Snadno skombinujeme s~prohledáváním do~hloubky. \: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. -- 2.39.2