From 56542b0a58413ecc4b55c3688ae67e44d94edb1b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 30 Jan 2011 23:20:17 +0100 Subject: [PATCH] APSP: Korektury a odkazy na literaturu --- 14-floyd/14-floyd.tex | 105 ++++++++++++++++++++++-------------------- ga.bib | 15 ++++++ 2 files changed, 70 insertions(+), 50 deletions(-) diff --git a/14-floyd/14-floyd.tex b/14-floyd/14-floyd.tex index 122cce9..9560c54 100644 --- a/14-floyd/14-floyd.tex +++ b/14-floyd/14-floyd.tex @@ -2,23 +2,22 @@ \prednaska{13}{Nejkrat¹í cesty: Maticové metody}{} -{\bf POZOR: Pracovní verze. Zacházet opatrnì.} - V~pøedchozí kapitole jsme se zabývali algoritmy pro hledání nejkrat¹ích cest z~daného poèáteèního vrcholu. Nyní se zamìøíme na výpoèet celé metriky grafu, tedy matice vzdáleností, která pro ka¾dou dvojici vrcholù obsahuje délku nejkrat¹í cesty mezi nimi. Jeden zpùsob se ihned nabízí: postupnì spustit Dijkstrùv algoritmus pro v¹echny -mo¾né volby poèáteèního vrcholu, pøípadnì se pøed tím je¹tì pomocí potenciálù -zbavit záporných hran. Tak dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$, -co¾ je pro øídké grafy nejlep¹í známý výsledek -- jen $\O(\log n)$-krát +mo¾né volby poèáteèního vrcholu, pøípadnì se pøed tím je¹tì zbavit záporných +hran pomocí potenciálù. Tak dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$. +To je pro øídké grafy nejlep¹í známý výsledek -- jen $\O(\log n)$-krát pomalej¹í, ne¾ je velikost výstupu. -Pro husté grafy obvykle pracují rychleji algoritmy zalo¾ené na maticích a zejména -na jejich násobení. Nìkolik takových si nyní pøedvedeme. Vrcholy grafu budou -v¾dy oèíslované èísly 1 a¾~$n$ a graf doplníme na úplný, pøièem¾ hrany, které -pùvodnì neexistovaly, obdr¾í délku $+\infty$. +Je-li graf hustý pracují obvykle rychleji algoritmy zalo¾ené na maticích, zejména +na jejich násobení. Nìkolik algoritmù tohoto druhu si nyní pøedvedeme. Graf budeme +v¾dy popisovat maticí délek hran -- to je matice $n\times n$, její¾ øádky i sloupce +jsou indexované vrcholy a na pozici $(i,j)$ se nachází délka hrany $ij$; pøípadné +chybìjící hrany doplníme s~délkou~$+\infty$. \h{Floydùv-Warshallùv algoritmus} @@ -31,10 +30,10 @@ Jako obvykle polo Pak platí: $$\eqalign{ D^0_{ij} &= \hbox{délka hrany $ij$,} \cr -D^n_{ij} &= \hbox{vzdálenost z~$i$ do~$j$,} \cr +D^n_{ij} &= \hbox{hledaná vzdálenost z~$i$ do~$j$,} \cr D^k_{ij} &= \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} ). \cr }$$ -První dvì rovnosti dostaneme pøímo z~definice. Tøetí rovnost dostaneme rozdìlením +První dvì rovnosti plynou pøímo z~definice. Tøetí rovnost dostaneme rozdìlením cest z~$i$ do~$j$ pøes 1 a¾~$k$ na ty, které se vrcholu~$k$ vyhnou (a~jsou tedy cestami pøes 1 a¾~$k-1$), a ty, které ho pou¾ijí -- ka¾dou takovou mù¾eme slo¾it z~cesty z~$i$ do~$k$ a cesty z~$k$ do~$j$, obojí pøes 1 a¾~$k-1$. @@ -45,15 +44,15 @@ bez z tak¾e tím fale¹né øe¹ení nevyrobíme. (Pøesnìji: ze sledu $i\alpha v\beta k\gamma v\delta j$, kde $v\not\in\beta,\gamma$, mù¾eme vypu¹tìním èásti $v\beta k\gamma v$ nezáporné délky získat sled z~$i$ do~$j$ pøes 1 a¾~$k-1$, jeho¾ délka nemù¾e být men¹í -ne¾~$D^{k-1}{ij}$.) +ne¾~$D^{k-1}_{ij}$.) -Samotný algoritmus pak postupnì poèítá matice $D^0, D^1, \ldots, D^n$: +Samotný algoritmus postupnì poèítá matice $D^0, D^1, \ldots, D^n$ podle uvedeného pøedpisu: \algo -\:$D^0 \leftarrow \hbox{matice délek hran}$ +\:$D^0 \leftarrow \hbox{matice délek hran}$. \:Pro $k=1,\ldots,n$: \::Pro $i,j=1,\ldots,n$: -\:::$D^k_{ij} = \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} )$. +\:::$D^k_{ij} \leftarrow \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} )$. \:$\hbox{Matice vzdáleností} \leftarrow D^n.$ \endalgo @@ -62,21 +61,22 @@ slo okam¾iku potøebujeme jen aktuální matici~$D^k$ a pøedchozí~$D^{k-1}$. Anebo nahlédneme, ¾e mù¾eme $D^{k-1}$ na~$D^k$ pøepisovat na místì. U~hodnot $D_{ik}$ a~$D_{kj}$ je toti¾ podle definice stará i nová hodnota stejná. Algoritmu tedy -staèí $\Theta(n^2)$ pamìti. +staèí jediné pole velikosti $n\times n$, které na~poèátku výpoètu obsahuje +vstup a na~konci výstup. \h{Regulární výrazy} Pøedchozí algoritmus lze zajímavì zobecnit, toti¾ tak, aby pro ka¾dou dvojici -vrcholù sestrojil vhodnou reprezentaci mno¾iny v¹ech sledù vedoucích mezi touto -dvojicí. Tato reprezentace bude velice podobná regulárním výrazùm známým -z~teorie automatù. Zadaný orientovaný graf pøitom mù¾e obsahovat i smyèky -a násobné hrany. +vrcholù sestrojil vhodnou reprezentaci mno¾iny v¹ech sledù vedoucích mezi nimi. +Tato reprezentace bude velice podobná regulárním výrazùm známým z~UNIXu +a z~teorie automatù. Budeme pøipou¹tìt orientované multigrafy se smyèkami +a násobnými hranami. \s{Definice:} {\I Svazek} je mno¾ina sledù, které mají spoleèný poèáteèní a koncový vrchol. {\I Typem} svazku nazveme uspoøádanou dvojici tìchto vrcholù. Místo \uv{svazek typu $(u,v)$} budeme obvykle øíkat prostì {\I $uv$-svazek.} -Triviálními pøípady svazkù jsou prázdná mno¾ina~$\emptyset$, hrana~$uv$ a pro +Triviálními pøípady svazkù jsou prázdná mno¾ina~$\emptyset$, samotná hrana~$uv$ a pro $u=v$ také sled~$\varepsilon$ nulové délky. Svazky mù¾eme kombinovat následujícími operacemi: @@ -94,7 +94,7 @@ jsou asociativn ni¾¹í prioritu ne¾ zøetìzení. \>Svazky budeme obvykle reprezentovat {\I sledovými výrazy,} co¾ jsou -výrazy koneèné délky sestávající se z~triviálních svazkù a vý¹e uvedených +výrazy koneèné délky sestávající z~triviálních svazkù a vý¹e uvedených operací. \s{Pozorování:} Sledy mù¾eme reprezentovat øetìzci nad abecedou, její¾ @@ -110,20 +110,20 @@ R^0_{ij} &= \hbox{mno R^n_{ij} &= \hbox{hledané $R_{ij}$}, \cr R^k_{ij} &= R^{k-1}_{ij} \cup R^{k-1}_{ik}(R^{k-1}_{kk})^*R^{k-1}_{kj}. \cr }$$ -První dvì rovnosti opìt dostaneme pøímo z~definice (mno¾inu v¹ech hran zapí¹eme +První dvì rovnosti opìt plynou pøímo z~definice (mno¾inu v¹ech hran zapí¹eme buï jako prázdnou nebo ji vytvoøíme sjednocováním z~jednoprvkových mno¾in). Tøetí rovnost vychází z~toho, ¾e ka¾dý sled z~$i$ do~$j$ buï neobsahuje~$k$, nebo ho mù¾eme rozdìlit na~èásti mezi jednotlivými náv¹tìvami vrcholu~$k$. Algoritmus tedy bude postupnì budovat matice $R^0, R^1, \ldots, R^n$ podle tìchto pravidel. Provedeme pøi tom $\Theta(n^3)$ operací, ov¹em s~výrazy, jejich¾ délka -mù¾e být a¾ øádovì~$4^n$. Radìji ne¾ jako øetìzce je budeme ukládat v~podobì +mù¾e být a¾ øádovì~$4^n$. Radìji ne¾ jako øetìzce je proto budeme ukládat v~podobì acyklických orientovaných grafù: vrcholy budou operace, hrany je budou pøipojovat k~operandùm. K~pøímému pou¾ití se takový exponenciálnì dlouhý výraz hodí málokdy, ale mù¾e nám pomoci odpovídat na rùzné otázky týkající se sledù s~danými koncovými vrcholy. -Máme-li nìjakou funkci~$f$ pøiøazující hodnoty mno¾inám sledù kódovaným sledovými +Máme-li nìjakou funkci~$f$ ohodnocující mno¾iny sledù kódované sledovými výrazy, staèí umìt vyhodnotit: \itemize\ibull \:výsledek pro triviální výrazy $f(\emptyset)$, $f(\varepsilon)$ a $f(e)$ pro hranu~$e$, @@ -146,7 +146,7 @@ pracuj $$\eqalign{ f(\emptyset)&=+\infty \cr f(\varepsilon)&=0 \cr -f(e)&=\ell(e) \hbox{\quad (délka hrany)} \cr +f(e)&=\ell(e) \hbox{\quad (délka hrany~$e$)} \cr f(\alpha\cup\beta) &= \min(f(\alpha),f(\beta)) \cr f(\alpha\beta) &= f(\alpha) + f(\beta) \cr f(\alpha^*) &= \cases{0 & \hbox{pro $f(\alpha)\ge 0$} \cr -\infty & \hbox{pro $f(\alpha)<0$} \cr} \cr @@ -158,7 +158,7 @@ a dostaneme p $$\eqalign{ f(\emptyset)&=0 \cr f(\varepsilon)&=\infty \cr -f(e)&=w(e) \hbox{\quad (¹íøka hrany)} \cr +f(e)&=w(e) \hbox{\quad (¹íøka hrany~$e$)} \cr f(\alpha\cup\beta) &= \max(f(\alpha),f(\beta)) \cr f(\alpha\beta) &= \min(f(\alpha),f(\beta)) \cr f(\alpha^*) &= \infty \cr @@ -175,7 +175,7 @@ odpov Øe¹íme-li grafové problémy pomocí matic, nabízí se pou¾ít známé subkubické algoritmy pro lineárnì algebraické úlohy. Ty jsou obvykle zalo¾eny na efektivním násobení -matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase $\O(n^2.808)$ Strassenovým +matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase $\O(n^{2.808})$ Strassenovým algoritmem~\cite{strassen:matmult}, pøípadnì asymptoticky nejrychlej¹ím známým algoritmem od Coppersmithe a Winograda~\cite{coppersmith:matmult} v~èase $\O(n^{2.376})$. Slavná hypotéza øíká, ¾e pro ka¾dé $\omega>2$ existuje algoritmus násobící matice se slo¾itostí $\O(n^\omega)$ @@ -192,8 +192,7 @@ To n je 1 nebo~0 podle toho, zda z~$i$ do~$j$ vede cesta). Do~matice~$A$ doplníme na diagonálu jednièky a poté ji $\lceil \log_2 n\rceil$-krát umocníme na~druhou. Abychom se vyhnuli velkým èíslùm, nahradíme po ka¾dém umocnìní nenuly jednièkami. -Celkem tedy provedeme $\O(\log n)$ násobení matic obsahující polynomiálnì velká -èísla, co¾ trvá $\O(n^\omega\log n)$. +Celkem tedy provedeme $\O(\log n)$ násobení matic, co¾ trvá $\O(n^\omega\log n)$. Na~tento postup se mù¾eme dívat i~obecnìji: @@ -239,16 +238,16 @@ celou \h{Rozdìl a panuj} Pøedchozí pøevod je ov¹em trochu marnotratný. ©ikovným pou¾itím metody Rozdìl a panuj -mù¾eme èasovou slo¾itost podstatnì sní¾it. Postup pøedvedeme pro dosa¾itelnost: na vstupu +mù¾eme èasovou slo¾itost je¹tì sní¾it. Postup pøedvedeme pro dosa¾itelnost: na vstupu tedy dostaneme matici sousednosti~$A$, výstupem má být její transitivní uzávìr~$A^*$ (matice dosa¾itelnosti). V¹echny souèiny matic v~tomto oddílu budou typu $(\lor,\land)$. Vrcholy grafu rozdìlíme na dvì mno¾iny $X$ a~$Y$ pøibli¾nì stejné velikosti, bez újmy na obecnosti tak, aby matice~$A$ mìla následující blokový tvar: -$$A = \pmatrix{ P & Q \cr R & S \cr }.$$ -Zde podmatice~$P$ popisuje hrany z~$X$ do~$X$, podmatice~$Q$ hrany z~$X$ do~$Y$, atd. +$$A = \pmatrix{ P & Q \cr R & S \cr },$$ +kde podmatice~$P$ popisuje hrany z~$X$ do~$X$, podmatice~$Q$ hrany z~$X$ do~$Y$, atd. -Pokud matici~$A^*$ zapí¹eme rovnì¾ v~blokovém tvaru: +\s{Vìta:} Pokud matici~$A^*$ zapí¹eme rovnì¾ v~blokovém tvaru: $$A^* = \pmatrix{ I & J \cr K & L \cr },$$ bude platit: $$\eqalign{ @@ -257,6 +256,8 @@ J &= IQS^*, \cr K &= S^*RI, \cr L &= S^* \lor S^*RIQS^*. }$$ + +\proof Jednotlivé rovnosti mù¾eme èíst takto: \def\nIJKL{\count0=`H\advance\count0 by\itemcount{\bf\char\count0:}} \numlist\nIJKL @@ -266,25 +267,29 @@ uvnit \:Sled z~$X$ do~$Y$ mù¾eme rozdìlit v~místì, kdy naposledy pøechází po~hranì z~$X$ do~$Y$. První èást pøitom bude sled z~$X$ do~$X$, druhá sled uvnitø~$Y$. -\:Se sledem z~$Y$ do~$X$ nalo¾íme obdobnì. +\:Se sledem z~$Y$ do~$X$ nalo¾íme symetricky. \:Sled z~$Y$ do~$Y$ vede buïto celý uvnitø~$Y$, nebo ho mù¾eme rozdìlit -na èást pøed prvním pøechodem z~$Y$ do~$X$, tento pøechod, sled z~$X$ do~$Y$, -pøechod zpìt a sled uvnitø~$Y$. +na~prvním pøechodu z~$Y$ do~$X$ a posledním pøechodu z~$X$ do~$Y$. +Èást pøed prvním pøechodem povede celá uvnitø~$Y$, èást mezi pøechody +bude tvoøit sled z~$X$ do~$X$ a koneènì èást za~posledním pøechodem zùstane +opìt uvnitø~$Y$. +\qeditem \endlist -K~výpoètu matice~$A^*$ nám tedy staèí spoèítat 3~tranzitivní uzávìry -matic polovièní velikosti (k~èemu¾ pou¾ijeme rekurzi), dále pak $\O(1)$ -$(\lor,\land)$-souèinù a $\O(1)$ souètù matic. +\s{Algoritmus:} +Výpoèet matice~$A^*$ provedeme podle pøedchozí vìty. Spoèítáme 3~tranzitivní uzávìry +matic polovièní velikosti rekurzivním voláním, dále pak $\O(1)$ $(\lor,\land)$-souèinù +a $\O(1)$ souètù matic. -Èasovou slo¾itost $t(n)$ mù¾eme popsat následující rekurencí: -$$t(n) = 3t(n/2) + \Theta(1)\cdot\mu(n/2) + \Theta(n^2),$$ +Èasová slo¾itost $t(n)$ tohoto algoritmu bude splòovat následující rekurenci: +$$t(1)=\Theta(1), \quad t(n) = 3t(n/2) + \Theta(1)\cdot\mu(n/2) + \Theta(n^2),$$ kde $\mu(k)$ znaèí èas potøebný na jeden $(\lor,\land)$-souèin matic $k\times k$. Jeliko¾ jistì platí $\mu(n/2)=\Omega(n^2)$, má tato rekurence podle kuchaøkové vìty øe¹ení $t(n) = \mu(n)$. Ukázali jsme tedy, ¾e výpoèet transitivního uzávìru je nejvý¹e stejnì -nároèný jako $(\lor,\land)$-násobení matic -- mù¾eme ho tedy provést -v~èase $\O(n^\omega)$. Dokonce mù¾eme snadno nalézt i opaèný pøevod, +nároèný jako $(\lor,\land)$-násobení matic -- mù¾eme ho proto provést +v~èase $\O(n^\omega)$. Dokonce existuje pøímoèarý pøevod v~opaèném smìru, tak¾e oba problémy jsou asymptoticky stejnì tì¾ké. Podobnì nalézt matici vzdáleností je stejnì tì¾ké jako $(\min,+)$-souèin, @@ -294,7 +299,7 @@ tak Pro neorientované neohodnocené grafy mù¾eme dosáhnout je¹tì lep¹ích výsledkù. Matici vzdáleností lze spoèítat v~èase $\O(n^\omega\log n)$ -Seidelovým algoritmem (FIXME: odkaz). Ten funguje následovnì: +Seidelovým algoritmem~\cite{seidel:unitlength}. Ten funguje následovnì: \s{Definice:} {\I Druhá mocnina grafu~$G$} je graf~$G^2$ na té¾e mno¾inì vrcholù, v~nìm¾ jsou vrcholy~$i$ a~$j$ spojeny hranou právì tehdy, existuje-li v~$G$ sled @@ -305,8 +310,8 @@ grafu~$G$ jedn Seidelùv algoritmus bude postupovat rekurzivnì: Sestrojí graf~$G^2$, rekurzí spoèítá jeho matici vzdáleností~$D'$ a z~ní pak rekonstruuje matici vzdáleností~$D$ -zadaného grafu. Rekurze konèí, pokud $G^2=G$ -- tehdy u¾ je ka¾dá komponenta -souvislosti zahu¹tìna na~úplný graf, tak¾e matice vzdálenosti je rovna matici sousednosti. +zadaného grafu. Rekurze konèí, pokud $G^2=G$ -- tehdy je ka¾dá komponenta +souvislosti zahu¹tìna na~úplný graf, tak¾e matice vzdáleností je rovna matici sousednosti. Zbývá ukázat, jak z~matice~$D'$ spoèítat matici~$D$. Zvolme pevnì~$i$ a zamìøme se na funkce $d(v)=D_{iv}$ a $d'(v)=D'_{iv}$. Jistì platí $d'(v) = \lfloor d(v)/2 \rfloor$, @@ -317,14 +322,14 @@ Jak vypad $d(u) = d(v)-1$ (to platí pro sousedy, kteøí le¾í na nìkteré z~nejkrat¹ích cest z~$v$ do~$i$). Pro v¹echny ostatní sousedy je $d(u)=d(v)$ nebo $d(u)=d(v)+1$. -Pokud $d(v)$ je liché, vyjde pro sousedy le¾ící na nejkrat¹ích cestách $d'(u)=d'(v)$ +Pokud je $d(v)$ liché, vyjde pro sousedy le¾ící na nejkrat¹ích cestách $d'(u)=d'(v)$ a pro ostatní sousedy $d'(u)\ge d'(v)$, tak¾e prùmìr z~$d'(u)$ pøes sousedy je alespoò~$d'(v)$. Je-li naopak $d(v)$ sudé, musí být pro sousedy na nejkrat¹ích cestách $d'(u) < d(v)$ a pro v¹echny ostatní $d'(u) = d(v)$, tak¾e prùmìr klesne pod~$d'(v)$. Prùmìry pøes sousedy pøitom mù¾eme spoèítat násobením matic: vynásobíme matici -sousednosti grafu~$G$ maticí vzdáleností~$D'$. Na pozici~$i,j$ se objeví souèet -hodnot $D_{ik}$ pøes v¹echny sousedy vrcholu~$j$. Ten staèí vydìlit stupòem +vzdáleností~$D'$ maticí sousednosti grafu~$G$. Na pozici~$i,j$ se objeví souèet +hodnot $D_{ik}$ pøes v¹echny sousedy~$k$ vrcholu~$j$. Ten staèí vydìlit stupòem vrcholu~$j$ a hledaný prùmìr je na svìtì. Po~provedení jednoho násobení matic tedy dovedeme pro ka¾dou dvojici vrcholù diff --git a/ga.bib b/ga.bib index 5a09f3a..74bc27e 100644 --- a/ga.bib +++ b/ga.bib @@ -685,3 +685,18 @@ year={2002}, publisher={ACM} } + +@inproceedings{ seidel:unitlength, + author = {Seidel, Raimund}, + title = {On the all-pairs-shortest-path problem}, + booktitle = {Proceedings of the twenty-fourth annual ACM symposium on Theory of computing}, + year = {1992}, + isbn = {0-89791-511-9}, + location = {Victoria, British Columbia, Canada}, + pages = {745--749}, + numpages = {5}, + url = {http://doi.acm.org/10.1145/129712.129784}, + doi = {http://doi.acm.org/10.1145/129712.129784}, + acmid = {129784}, + publisher = {ACM}, +} -- 2.39.2