From 8ddca00c8bbe52b0f200842af23293e9edf84794 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 16 Oct 2010 23:16:12 +0200 Subject: [PATCH] Cesty: Dinicuv algoritmus, potencialy, par odkazu na literaturu --- 13-dijkstra/13-dijkstra.tex | 132 ++++++++++++++++++++++++++++++++---- ga.bib | 28 ++++++++ 2 files changed, 145 insertions(+), 15 deletions(-) diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex index 1794049..3c1dfb8 100644 --- a/13-dijkstra/13-dijkstra.tex +++ b/13-dijkstra/13-dijkstra.tex @@ -58,7 +58,7 @@ grafu~$G$, zako vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou z~nejkrat¹ích cest z~$u$ do~$v$ v~grafy~$G$. -\>{\bo Pozorování:} Strom nejkrat¹ích cest v¾dy existuje. +\s{Pozorování:} Strom nejkrat¹ích cest v¾dy existuje. \proof Nech» $u=v_1,\ldots,v_n$ jsou v¹echny vrcholy grafu~$G$. Indukcí budeme @@ -128,7 +128,7 @@ v~kroku~4 nespecifikuje, podle jak ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu výbìru nezávisejí. -\>\s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak: +\s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak: \numlist\nparen \:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu -- doká¾eme indukcí podle poètu krokù algoritmu. @@ -151,7 +151,7 @@ v \>Meta-algoritmus tedy pro libovolnou implementaci kroku~4 spoèítá správné vzdálenosti. \qed -\>\s{Cvièení:} +\s{Cvièení:} \itemize\ibull \:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9 pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$u$. Doka¾te, ¾e pøedchùdci @@ -170,7 +170,7 @@ kter udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané zaøazujeme na~konec. Co toto pravidlo zpùsobí? -\>\s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$. +\s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$. \proof Bìh algoritmu rozdìlíme na~fáze. Nultá fáze sestává z~vlo¾ení vrcholu~$u$ @@ -185,7 +185,7 @@ Relaxace ka fáze probìhne v~èase $\O(m)$. \qed -\>\s{Cvièení:} +\s{Cvièení:} \itemize\ibull \:Uka¾te, ¾e asymptoticky stejné èasové slo¾itosti by dosáhl algoritmus, který by vrcholy oèísloval $v_1,\ldots,v_n$ a opakovanì by je v~tomto @@ -201,7 +201,7 @@ Pokud jsou v pro výbìr vrcholu navr¾ené Dijkstrou. To øíká, ¾e v¾dy relaxujeme ten z~otevøených vrcholù, jeho¾ ohodnocení je nejmen¹í. -\>\s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající +\s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající vzdálenosti od~$u$ a ka¾dý dosa¾itelný vrchol uzavøe právì jednou. \proof @@ -254,21 +254,21 @@ na~struktu $\O(\log n)$ [v¹e amortizovanì]. Dijkstrùv algoritmus tedy dobìhne v~èase $\O(m + n\log n)$. To je lineární pro grafy s~hustotou $\Omega(\log n)$. \:{\I Monotónní haldy} -- mù¾eme pou¾ít nìjakou jinou haldu, která vyu¾ívá toho, - ¾e posloupnost odebíraných prvkù neklesající. Pro celá èísla na~RAMu to mù¾e - být napøíklad Thorupova halda (REF) se slo¾itostí $\O(\log\log n)$ na~\ + ¾e posloupnost odebíraných prvkù neklesající. Pro celá èísla na~\hbox{RAMu} to mù¾e + být napøíklad Thorupova halda \cite{thorup:queue} se slo¾itostí $\O(\log\log n)$ u~operace \ a $\O(1)$ u~ostatních operací. Dijkstra tedy bì¾í v~$\O(m + n\log\log n)$. \:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápìtí. \endlist -\>\s{Cvièení:} +\s{Cvièení:} \itemize\ibull \:Najdìte pøíklad nìjakého grafu se zápornými hranami (ale bez záporných cyklù), na~kterém Dijkstrùv algoritmus sel¾e. \:Rozmyslete si, ¾e pokud nevyu¾ijeme nìjaké speciální vlastnosti èísel (celoèíselnost, omezený rozsah), je mez $\O(m+n\log n)$ nejlep¹í mo¾ná, proto¾e Dijkstrovým algoritmem - mù¾eme tøídit $n$-tici èísel. Thorup dokonce dokázal (REF), ¾e z~ka¾dého tøídícího algoritmu - se slo¾itostí $nT(n)$ mù¾eme odvodit monotónní haldu se slo¾itostí mazání $\O(T(n))$. + mù¾eme tøídit $n$-tici èísel. Thorup dokonce dokázal \cite{thorup:equiv}, ¾e z~ka¾dého tøídícího algoritmu + se slo¾itostí $nT(n)$ mù¾eme odvodit haldu se slo¾itostí mazání $\O(T(n))$. \:Jsou-li délky hran celoèíselné, mù¾eme se na Dijkstrùv algoritmus dívat i takto: Pøedstavme si, ¾e ka¾dou hranu nahradíme cestou tvoøenou hranami jednotkové délky a na vzniklý neohodnocený graf spustíme prohledávání do~¹íøky. To samozøejmì vydá @@ -401,7 +401,7 @@ Tehdy Dijkstra vyd \h{HOT Queue -- kombinace pøihrádek s~haldou} -Goldberg a Cherkassky (REF) si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách +Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách platíme pøíli¹ mnoho za~úrovnì, ve~kterých se za~dobu jejich existence objeví jen malé mno¾ství prvkù. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~spoleèné haldy. Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. My si pøedvedeme její upravenou @@ -420,13 +420,13 @@ m Promìnnou~$\mu$ necháme ukazovat na~místo, kde jsme se pøi hledání minima v~pøihrádkách zastavili. Souèasné globální minimum struktury tedy mù¾e být ni¾¹í, kdy¾ se minimum zrovna nachází v~haldì, ale stále je zaruèeno, ¾e pøed~$\mu$ se ji¾ nenachází ¾ádná -neprázdná pøihradka. +neprázdná pøihrádka. Operace budou fungovat takto: \>\: \algo -\:Spoèítáme, do~které úrovnì~$i$ ma prvek padnout. +\:Spoèítáme, do~které úrovnì~$i$ má prvek padnout. \:Pokud je poèítadlo této úrovnì men¹í ne¾~$K$, zvý¹íme ho, vlo¾íme prvek do~haldy a skoèíme. \:Nebyly-li je¹tì pro tuto úroveò zalo¾eny pøihrádky, vyrobíme je (prázdné). \:Vlo¾íme prvek do~pøíslu¹né pøihrádky. @@ -482,5 +482,107 @@ HOT Queue tedy zvl a ostatní operace v~èase amortizovanì konstantním. Pou¾ijeme-li tuto strukturu v~Dijkstrovì algoritmu, spoète vzdálenosti v~èase $\O(m + n\sqrt{\log L})$. -%\references +\h{Dinicùv algoritmus} + +Zajímavé vylep¹ení Dijkstrova algoritmu navrhl Dinic (REF). V¹iml si, ¾e pokud +je ka¾dá hrana dlouhá alespoò~$\delta$, pak platí, ¾e mù¾eme uzavírat nejen +vrchol s~minimálním ohodnocením~$\mu$, ale i v¹echny ostatní s~ohodnocením +men¹ím ne¾ $\mu+\delta$. + +Pro takto upravený Dijkstrùv algoritmus bude stále platit, ¾e pøi uzavírání +vrcholu odpovídá ohodnocení skuteèné vzdálenosti, tak¾e uzavøené vrcholy ji¾ +nejsou znovu otevírány. + +O~monotonii vzdáleností jsme sice pøi¹li, ale v~pøihrádkové struktuøe nebo +haldì mù¾eme klíèe nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$. +Tyto hodnoty se toti¾ chovají monotónnì a vrcholy se stejným $h'(v)$ mù¾eme +libovolnì zamìòovat. + +Libovolnou z~popsaných pøihrádkových struktur tedy mù¾eme pou¾ít, pouze +v~rozboru èasové slo¾itosti nahradíme~$L$ výrazem $L/\delta$. Tento pøístup +pøitom funguje i pro neceloèíselné kapacity, pouze potøebujeme mít pøedem +k~dispozici netriviální dolní odhad na~délky v¹ech hran. + +\s{Cvièení:} Navrhnìte úpravu tohoto algoritmu, která nepotøebuje~$\delta$ znát pøedem. + +\h{Potenciály} + +Vidìli jsme, ¾e v~grafech s~nezápornými délkami hran se nejkrat¹í cesty +hledají daleko rychleji. Nabízí se nalézt nìjakou transformaci, která by +dovedla délky upravit tak, aby byly nejkrat¹í cesty zachovány (samozøejmì +ne jejich délky, ale alespoò to, které cesty jsou nejkrat¹í). Nabízí se +následující fyzikální inspirace: + +\s{Definice:} {\I Potenciál} budeme øíkat libovolné funkci $\psi: V\rightarrow {\bb R}$. +Pro ka¾dý potenciál zavedeme {\I redukované délky} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$. +Potenciálu budeme øíkat {\I pøípustný,} pokud ¾ádná hrana nemá zápornou redukovanou délku. + +\s{Pozorování:} Pro redukovanou délku libovolné cesty~$P$ z~$u$ do~$v$ platí: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$. + +\proof +Nech» cesta~$P$ prochází pøes vrcholy $u=w_1,\ldots,w_k=v$. Potom: +$$ +\ell_\psi(P) = \sum_i \ell_\psi(w_i,w_{i+1}) = \sum_i \left( \ell(w_i,w_{i+1}) + \psi(w_i) - \psi(w_{i+1}) \right). +$$ +Tato suma je ov¹em teleskopická, tak¾e z~ní zbude: +$$ +\sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k), +$$ +co¾ je rovno $\ell(P) + \psi(u) - \psi(v)$. +\qed + +\s{Dùsledek:} Potenciálovou redukcí se tedy délky v¹ech cest mezi~$u$ a~$v$ +zmìní o~tuté¾ konstantu, tak¾e struktura nejkrat¹ích cest zùstane nezmìnìna. + +Zbývá pøijít na~to, kde si obstarat nìjaký pøípustný potenciál. Pøidejme do~grafu +nový vrchol~$z$, pøiveïme z~nìj hranu nulové délky do~v¹ech ostatních vrcholù +a~oznaème~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál +pøípustný, musí pro ka¾dou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$. +Tuto nerovnost mù¾eme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, èili +$d(z,u) + \ell(u,v) \ge d(z,v)$, co¾ je ale obyèejná trojúhelníková nerovnost +pro vzdálenost v~grafu, která jistì platí. + +Jedním výpoètem nejkrat¹ích cest v~grafu se zápornými hranami (tøeba algoritmem BFM) +tedy doká¾eme spoèítat potenciál, který nám pomù¾e k~redukci v¹ech hran na~nezáporné +délky. To nám samozøejmì nepomù¾e, chceme-li jednorázovì hledat nejkrat¹í cestu, +ale mù¾e nám to výraznì zjednodu¹it dal¹í, slo¾itìj¹í práci s~grafem. Jak uvidíme +v~pøí¹tí kapitole, mù¾eme tak napøíklad nalézt vzdálenosti mezi v¹emi dvojicemi +vrcholù v~èase $\O(nm + n^2\log n)$. + +Na~závìr tohoto oddílu doká¾eme jedno pomocné tvrzení o~potenciálech, které +nám pomù¾e v~konstrukci algoritmù typu \ppsp: + +\s{Lemma:} Pokud $f$ a~$g$ jsou pøípustné potenciály, pak jsou jimi i: +\numlist\ndotted +\:Konvexní kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolné $\alpha,\beta\ge 0, \alpha+\beta=1$, +\:$\min(f,g)$, +\:$\max(f,g)$. +\endlist + +\proof Buï $uv$ hrana. Potom z~definice pøípustnosti platí $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$. +Jednotlivé èásti tvrzení doká¾eme takto: +\numlist\ndotted +\:Pokud obì strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$ + konstantou~$\beta$ a obì nerovnosti seèteme, dostaneme: + $$ + (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)), + $$ + co¾ je pøesnì po¾adovaná nerovnost pro pøípustnost funkce $\alpha f+\beta g$. +\:Oznaème $h := \min(f,g)$. Nech» bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$, + shoduje se minimum s~funkcí~$f$ a není co dokazovat. V~opaèném pøípadì je $h(u) = f(u)$, $h(v) = g(v)$. + Tehdy si staèí v¹imnout, ¾e $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, tak¾e + potenciál~$h$ je pøípustný. +\:Doká¾eme analogicky. +\qeditem +\endlist + +\h{Algoritmy pro problém typu \ppsp} + +Zamìøme se nyní na~pøípad, kdy chceme hledat nejkrat¹í cesty mezi zadanou dvojicí +vrcholù $u$,~$v$. Obvykle se to øe¹í pomocí algoritmu typu \sssp{} (SSSP) a v~obecném +pøípadì ani není lep¹í øe¹ení známo. Existuje ov¹em velké mno¾ství heuristik, kterými +lze ve~vìt¹inì aplikací hledání cest zrychlit. Nìkteré z~nich si pøedvedeme a omezíme +se pøitom na pøípady s~nezápornými délkami. + +\references \bye diff --git a/ga.bib b/ga.bib index cc08735..edac83d 100644 --- a/ga.bib +++ b/ga.bib @@ -505,3 +505,31 @@ publisher = {ACM}, address = {New York, NY, USA}, } + +@inproceedings{ thorup:queue, + title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}}, + author={Thorup, M.}, + booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing}, + pages={149--158}, + year={2003}, +} + +@article{ thorup:equiv, + title={{Equivalence between priority queues and sorting}}, + author={Thorup, M.}, + journal={Journal of the ACM}, + volume={54}, + number={6}, + pages={28}, + year={2007}, + publisher={ACM} +} + +@conference{ cherkassky:hotq, + title={{Buckets, heaps, lists, and monotone priority queues}}, + author={Cherkassky, B.V. and Goldberg, A.V. and Silverstein, C.}, + booktitle={Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms}, + pages={83--92}, + year={1997}, + organization={Society for Industrial and Applied Mathematics} +} -- 2.39.2