From 423a044a0c2c65155290297cf1e078fe3ce68608 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 16 Feb 2007 22:01:17 +0100 Subject: [PATCH] Pripsan algoritmus tri Indu. Bohuzel se tim dost rozpadla sazba, ale to brzy napravime. --- 2-dinic/2-dinic.tex | 62 +++++++++++++++++++++++++++++++++++++++++++++ ga.bib | 10 ++++++++ 2 files changed, 72 insertions(+) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index fb84500..11c8da4 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -264,6 +264,65 @@ Maxim Podle pøedchozího odhadu pro celoèíselné kapacity výpoèet toku $f_i$ trvá $\O(mn)$. Takový tok se bude poèítat $k$-krát, proèe¾ celková slo¾itost vyjde $\O(mn\log C)$. +\h{Algoritmus tøí Indù} + +Pøekvapení na~konec: Dinicùv algoritmus lze pomìrnì snadno zrychlit i ve~zcela obecném +pøípadì. Malhotra, Kumar a Maheshwari vymysleli efektivnìj¹í algoritmus \cite{threeinds} +na~hledání blokujícího toku ve~vrstevnaté síti, který bì¾í v~èase $\O(n^2)$ a pou¾ijeme-li +ho v~Dinicovì algoritmu, zrychlíme hledání maximálního toku na~$\O(n^3)$. +Tento algoritmus ve¹el do~dìjin pod názvem Metoda tøí Indù. + +Mìjme tedy nìjakou vrstevnatou sí». Zaèneme s~nulovým tokem a budeme ho postupnì zlep¹ovat. +Prùbì¾nì si budeme udr¾ovat rezervy hran~$r(e)$\foot{poèítáme pouze rezervu ve~smìru hrany, nebo» +nám staèí najít blokující tok, ne~nutnì maximální} a také následující rezervy vrcholù: + +\s{Definice:} $r^+(v)$ je souèet rezerv v¹ech hran vstupujících do~$v$, $r^-(v)$ souèet +rezerv hran vystupujících z~$v$ a koneènì $r(v):=\min(r^+(v),r^-(v))$. + +V~ka¾dé iteraci algoritmu nalezneme vrchol s~nejni¾¹ím~$r(v)$ a zvìt¹íme tok tak, aby se +tato rezerva vynulovala. Za~tímto úèelem nejdøíve pøepravíme $r(v)$ jednotek toku ze~zdroje +do~$v$: u~ka¾dého vrcholu~$w$ si budeme pamatovat {\I plán} $p(w)$, co¾ bude mno¾ství +tekutiny, které potøebujeme dostat ze~zdroje do~$w$. Nejdøíve budou plány v¹ude nulové +a¾ na~$p(v)=r(v)$. Pak budeme postupovat po~vrstvách smìrem ke~zdroji a plány v¹ech +vrcholù splníme tak, ¾e je pøevedeme na~plány vrcholù v~následující vrstvì, a¾ doputujeme +ke~zdroji, jeho¾ plán je splnìn triviálnì. Nakonec analogickým zpùsobem protlaèíme $r(v)$ +jednotek z~$v$ do~spotøebièe. + +Bìhem výpoètu prùbì¾nì pøepoèítáváme v¹echna $r^+$, $r^-$ a~$r$ podle toho, jak se mìní +rezervy jednotlivých hran (pøi ka¾dé úpravì rezervy to zvládneme v~konstantním èase) +a sí» èistíme stejnì jako u~Dinicova algoritmu. + +\s{Algoritmus:} (hledání blokujícího toku ve~vrstevnaté síti podle tøí Indù) + +\algo +\:$f_B\leftarrow\$. +\:Spoèítáme rezervy v¹ech hran a $r^+$, $r^-$ a $r$ v¹ech vrcholù. (Tyto hodnoty + budeme posléze udr¾ovat pøi ka¾dé zmìnì toku po~hranì.) +\:Dokud v~síti existují vrcholy s~nenulovou rezervou, vezmeme vrchol $v$ s~nejmen¹ím $r(v)$ + a provedeme pro nìj: {\I (vnìj¹í cyklus)} +\::Pøevedeme $r(v)$ jednotek toku z~$s$ do~$v$ následovnì: +\:::Polo¾íme $p(v)\leftarrow r(v)$, $p(\cdot)=0$. +\:::Procházíme vrcholy sítì po~vrstvách od~$v$ smìrem k~$s$. Pro ka¾dý vrchol~$w$ provedeme: +\::::Dokud $p(w)>0$: +\:::::Vezmeme libovolnou hranu $uw$ a tok po~ní zvý¹íme o~$\delta=\min(r(uw), p(w))$. Tím se + $p(w)$ sní¾í~o~$\delta$ a $p(u)$ zvý¹í~o~$\delta$. +\:::::Pokud se hrana~$uw$ nasytila, odstraníme jí ze sítì a sí» doèistíme. +\::Analogicky pøevedeme $r(v)$ jednotek z~$v$ do~$s$. +\endalgo + +\s{Analýza:} Nejprve si v¹imneme, ¾e cyklus v~kroku~8 opravdu doká¾e vynulovat $p(w)$. +Souèet v¹ech $p(w)$ pøes ka¾dou vrstvu je toti¾ nejvý¹e roven $r(v)$, tak¾e speciálnì ka¾dé +$p(w)\le r(v)$. Jen¾e $r(v)$ jsme vybrali jako nejmen¹í, tak¾e $p(w)\le r(v)\le r(w)\le r^+(w)$, +a~proto je plánovaný tok kudy pøivést. Proto se algoritmus zastaví a vydá blokující tok. + +Zbývá odhadnout èasovou slo¾itost: Kdy¾ oddìlíme pøevádìní plánù po~hranách (kroky 7--9), +zbytek jedné iterace vnìj¹ího cyklu trvá~$\O(n)$ a tìchto iterací je nejvý¹e~$n$. V¹echna pøevedení +plánu si rozdìlíme na~ta, kterými se nìjaká hrana nasytila, a~ta, která skonèila vynulováním $p(w)$. +Tìch prvních je $\O(m)$, proto¾e ka¾dou takovou hranu vzápìtí odstraníme a èi¹tìní, jak u¾ víme, +trvá také lineárnì dlouho. Druhý pøípad nastane pro ka¾dý vrchol nejvý¹e jednou za~iteraci. +Dohromady tedy trvají v¹echna pøevedení $\O(n^2)$, stejnì jako zbytek algoritmu. +\qed + \h{Pøehled variant Dinicova algoritmu} \medskip @@ -277,6 +336,9 @@ jednotkov 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$ (scaling)&$\O(mn\log C)$ \cr +tøi Indové &$\O(n^3)$ \cr }}} +\references + \bye diff --git a/ga.bib b/ga.bib index 792e03a..22c54fa 100644 --- a/ga.bib +++ b/ga.bib @@ -460,3 +460,13 @@ year={1997}, publisher={Elsevier} } + +@article{ threeinds, + title={{An $\O({\vert V\vert}^3)$ algorithm for finding maximum flows in networks}}, + author={Malhotra, V. and Kumar, M.P. and Maheshwari, S.N.}, + journal={Information Processing Letters}, + volume={7}, + number={6}, + pages={277--278}, + year={1978} +} -- 2.39.2