14-floyd/14-floyd.tex

   1 \input ../sgr.tex
   2
   3 \def\alt{\mathop{\vert}}
   4
   5 \prednaska{13}{Nejkrat¹í cesty: Maticové metody}{}
   6
   7 V~pøedchozí kapitole jsme se zabývali algoritmy pro hledání nejkrat¹ích
   8 cest z~daného poèáteèního vrcholu. Nyní se zamìøíme na výpoèet celé
   9 metriky grafu, tedy matice vzdáleností, která pro ka¾dou dvojici vrcholù
  10 obsahuje délku nejkrat¹í cesty mezi nimi.
  11
  12 Jeden zpùsob se ihned nabízí: postupnì spustit Dijkstrùv algoritmus pro v¹echny
  13 mo¾né volby poèáteèního vrcholu, pøípadnì se pøed tím je¹tì pomocí potenciálù
  14 zbavit záporných hran. Tak dosáhneme èasové slo¾itosti $\O(mn + n^2\log n)$,
  15 co¾ je pro øídké grafy nejlep¹í známý výsledek -- jen $\O(\log n)$-krát
  16 pomalej¹í, ne¾ je velikost výstupu.
  17
  18 Pro husté grafy obvykle pracují rychleji algoritmy zalo¾ené na maticích a zejména
  19 na jejich násobení. Nìkolik takových si nyní pøedvedeme. Vrcholy grafu budou
  20 v¾dy oèíslované èísly 1 a¾~$n$ a graf doplníme na úplný, pøièem¾ hrany, které
  21 pùvodnì neexistovaly, obdr¾í délku $+\infty$.
  22
  23 \h{Floydùv-Warshallùv algoritmus}
  24
  25 Zaènìme algoritmem, který nezávisle na sobì objevili Floyd a Warshall.
  26 Funguje pro libovolný orientovaný graf bez záporných cyklù.
  27
  28 Oznaème $D^k_{ij}$ délku nejkrat¹í cesty z~vrcholu~$i$ do vrcholu~$j$ pøes
  29 vrcholy 1 a¾~$k$ (tím myslíme, ¾e v¹echny vnitøní vrcholy cesty le¾í v~mno¾inì $\{1,\ldots,k\}$).
  30 Jako obvykle polo¾íme $D^k_{ij}=+\infty$, pokud ¾ádná taková cesta neexistuje.
  31 Pak platí:
  32 $$\eqalign{
  33 D^0_{ij} &= \hbox{délka hrany $ij$,} \cr
  34 D^n_{ij} &= \hbox{vzdálenost z~$i$ do~$j$,} \cr
  35 D^k_{ij} &= \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} ). \cr
  36 }$$
  37 První dvì rovnosti dostaneme pøímo z~definice. Tøetí rovnost dostaneme rozdìlením
  38 cest z~$i$ do~$j$ pøes 1 a¾~$k$ na ty, které se vrcholu~$k$ vyhnou (a~jsou tedy
  39 cestami pøes 1 a¾~$k-1$), a ty, které ho pou¾ijí -- ka¾dou takovou mù¾eme slo¾it
  40 z~cesty z~$i$ do~$k$ a cesty z~$k$ do~$j$, obojí pøes 1 a¾~$k-1$.
  41
  42 Zbývá vyøe¹it jednu malièkost: slo¾ením cesty z~$i$ do~$k$ s~cestou z~$k$ do~$j$
  43 nemusí nutnì vzniknout cesta, proto¾e se nìjaký vrchol mù¾e opakovat. V~grafech
  44 bez záporných cyklù nicménì takový sled nemù¾e být krat¹í ne¾ nejkrat¹í cesta,
  45 tak¾e tím fale¹né øe¹ení nevyrobíme. (Pøesnìji: ze sledu $i\alpha v\beta k\gamma v\delta j$,
  46 kde $v\not\in\beta,\gamma$, mù¾eme vypu¹tìním èásti $v\beta k\gamma v$ nezáporné
  47 délky získat sled z~$i$ do~$j$ pøes 1 a¾~$k-1$, jeho¾ délka nemù¾e být men¹í
  48 ne¾~$D^{k-1}{ij}$.)
  49
  50 Samotný algoritmus pak postupnì poèítá matice $D^0, D^1, \ldots, D^n$:
  51
  52 \algo
  53 \:$D^0 \leftarrow \hbox{matice délek hran}$
  54 \:Pro $k=1,\ldots,n$:
  55 \::Pro $i,j=1,\ldots,n$:
  56 \:::$D^k_{ij} = \min( D^{k-1}_ij, D^{k-1}_{ik} + D^{k-1}_{kj} )$.
  57 \:$\hbox{Matice vzdáleností} \leftarrow D^n.$
  58 \endalgo
  59
  60 Èasová slo¾itost tohoto algoritmu èiní $\Theta(n^3)$. Kubickou prostorovou
  61 slo¾itost mù¾eme snadno sní¾it na~kvadratickou: Buï si uvìdomíme, ¾e v~ka¾dém
  62 okam¾iku potøebujeme jen aktuální matici~$D^k$ a pøedchozí~$D^{k-1}$. Anebo
  63 nahlédneme, ¾e mù¾eme $D^{k-1}$ na~$D^k$ pøepisovat na místì. U~hodnot $D_{ik}$
  64 a~$D_{kj}$ je toti¾ podle definice stará i nová hodnota stejná. Algoritmu tedy
  65 staèí $\Theta(n^2)$ pamìti.
  66
  67 \h{Regulární výrazy}
  68
  69 Pøedchozí algoritmus lze zajímavì zobecnit, toti¾ tak, aby pro ka¾dou dvojici
  70 vrcholù sestrojil vhodnou reprezentaci mno¾iny v¹ech sledù vedoucích mezi touto
  71 dvojicí. Tato reprezentace bude velice podobná regulárním výrazùm známým
  72 z~teorie automatù. Zadaný orientovaný graf pøitom mù¾e obsahovat i smyèky
  73 a násobné hrany.
  74
  75 \s{Definice:} {\I Sledový regulární výraz} pro vrcholy $u$ a~$v$ (zkrácenì
  76 {\I $uv$-výraz}) kóduje mno¾inu sledù z~vrcholu~$u$ do vrcholu~$v$. Mno¾inu
  77 kódovanou výrazem~$\psi$ budeme znaèit $S(\psi)$. Ka¾dý $uv$-výraz má jeden
  78 z~tìchto tvarù:
  79
  80 \itemize\ibull
  81 \:$\emptyset$ -- prázdná mno¾ina sledù,
  82 \:$e$ -- identifikátor nìkteré hrany z~$u$ do~$v$,
  83 \:$\alpha\alt\beta$ (kde $\alpha$ i $\beta$ jsou $uv$-výrazy) --
  84 {\I sjednocení:} $S(\alpha\alt\beta) = S(\alpha) \cup S(\beta)$,
  85 \:$\alpha\beta$ (kde $\alpha$ je $uw$-výraz a $\beta$ je $wv$-výraz pro nìjaké~$w$) --
  86 {\I zøetìzení:} $S(\alpha\beta)$ je mno¾ina v¹ech sledù, které vzniknou
  87 napojením nìjakého sledu z~$S(\beta)$ za nìjaký sled z~$S(\alpha)$,
  88 \endlist
  89
  90 \>Pokud $u=v$, pak navíc:
  91 \itemize\ibull
  92 \:$\varepsilon$ -- mno¾ina obsahující pouze sled nulové délky,
  93 \:$\alpha^*$ (kde $\alpha$ je $uu$-výraz) -- {\I iterace:}
  94 $\alpha^* = \varepsilon \alt \alpha \alt \alpha\alpha \alt \alpha\alpha\alpha \alt \ldots$
  95 \endlist
  96 \>Operace sjednocení a zøetìzení jsou asociativní, tak¾e je obvykle nebudeme
  97 závorkovat; operace sjednocení má ve~výrazech ni¾¹í prioritu ne¾ zøetìzení.
  98
  99 Pro ka¾dou dvojici vrcholù $i$,~$j$ nyní budeme hledat výraz $R_{ij}$ popisující
 100 v¹echny sledy z~$i$ do~$j$. Podobnì jako u~Floydova-Warshallova algoritmu zavedeme
 101 $R^k_{ij}$ coby výraz popisující sledy z~$i$ do~$j$ pøes 1 a¾~$k$ a nahlédneme,
 102 ¾e platí:
 103 $$\eqalign{
 104 R^0_{ij} &= \hbox{mno¾ina v¹ech hran z~$i$ do~$j$}, \cr
 105 R^n_{ij} &= \hbox{hledané $R_{ij}$}, \cr
 106 R^k_{ij} &= R^{k-1}_{ij} \alt R^{k-1}_{ik}(R^{k-1}_{kk})^*R^{k-1}_{kj}. \cr
 107 }$$
 108 První dvì rovnosti opìt dostaneme pøímo z~definice (mno¾inu v¹ech hran zapí¹eme
 109 buï jako prázdnou nebo ji vytvoøíme sjednocováním z~jednoprvkových mno¾in). Tøetí
 110 rovnost vychází z~toho, ¾e ka¾dý sled z~$i$ do~$j$ buï neobsahuje~$k$, nebo ho
 111 mù¾eme rozdìlit na~èásti mezi jednotlivými náv¹tìvami vrcholu~$k$.
 112
 113 Algoritmus tedy bude postupnì budovat matice $R^0, R^1, \ldots, R^n$ podle tìchto
 114 pravidel. Provedeme pøi tom $\Theta(n^3)$ operací, ov¹em s~výrazy, jejich¾ délka
 115 mù¾e být a¾ øádovì~$4^n$. Radìji ne¾ jako øetìzce je budeme ukládat v~podobì
 116 acyklických orientovaných grafù: vrcholy budou operace, hrany je budou pøipojovat
 117 k~operandùm.
 118
 119 K~pøímému pou¾ití se takový exponenciálnì dlouhý výraz hodí málokdy, ale mù¾e
 120 nám pomoci odpovídat na rùzné otázky týkající se sledù s~danými koncovými vrcholy.
 121 Máme-li nìjakou funkci~$f$ pøiøazující hodnoty mno¾inám sledù kódovaným sledovými
 122 výrazy, staèí umìt vyhodnotit:
 123 \itemize\ibull
 124 \:výsledek pro triviální výrazy $f(\emptyset)$, $f(\varepsilon)$ a $f(e)$ pro hranu~$e$,
 125 \:hodnoty $f(\alpha\alt\beta)$, $f(\alpha\beta)$ a $f(\alpha^*)$, známe-li ji¾ $f(\alpha)$ a $f(\beta)$.
 126 \endlist
 127 \>Pro výpoèet v¹ech $f(R_{ij})$ nám pak staèí $\Theta(n^3)$ vyhodnocení funkce~$f$.
 128
 129 \s{Pøíklady:}
 130
 131 \>{\I Nejkrat¹í sled:}
 132 $$\eqalign{
 133 f(\emptyset)&=+\infty \cr
 134 f(\varepsilon)&=0 \cr
 135 f(e)&=\ell(e) \hbox{\quad (délka hrany)} \cr
 136 f(\alpha\alt\beta) &= \min(f(\alpha),f(\beta)) \cr
 137 f(\alpha\beta) &= f(\alpha) + f(\beta) \cr
 138 f(\alpha^*) &= \cases{0 & \hbox{pro $f(\alpha)\ge 0$} \cr -\infty & \hbox{pro $f(\alpha)<0$} \cr} \cr
 139 }$$
 140 (Pokud pøedpokládáme, ¾e v~grafu nejsou záporné cykly, je $f(\alpha^*)$ v¾dy nulové
 141 a dostaneme pøesnì Floydùv-Warshallùv algoritmus.)
 142
 143 \>{\I Nej¹ir¹í cesta} (hranám jsou pøiøazeny ¹íøky, ¹íøka cesty je minimum z~¹íøek hran):
 144 $$\eqalign{
 145 f(\emptyset)&=0 \cr
 146 f(\varepsilon)&=\infty \cr
 147 f(e)&=w(e) \hbox{\quad (¹íøka hrany)} \cr
 148 f(\alpha\alt\beta) &= \max(f(\alpha),f(\beta)) \cr
 149 f(\alpha\beta) &= \min(f(\alpha),f(\beta)) \cr
 150 f(\alpha^*) &= \infty \cr
 151 }$$
 152
 153 \>{\I Pøevod koneèného automatu na regulární výraz:} Vrcholy multigrafu budou odpovídat
 154 stavùm automatu, hrany mo¾ným pøechodùm mezi stavy. Ka¾dou hranu ohodnotíme symbolem
 155 abecedy, po jeho¾ pøeètení automat pøechod provede. Funkce~$f$ pak pøiøadí $uv$-výrazu~$\psi$
 156 regulární výraz popisující mno¾inu v¹ech øetìzcù, po jejich¾ pøeètení automat pøejde
 157 ze~stavu~$u$ do stavu~$v$ po pøechodech z~mno¾iny $S(\psi)$. Vyhodnocování funkce~$f$
 158 odpovídá pøímoèarým operacím s~øetìzci.
 159
 160 \h{Násobení matic}
 161
 162 Øe¹íme-li grafové problémy pomocí matic, nabízí se pou¾ít známé subkubické algoritmy
 163 pro lineárnì algebraické úlohy. Ty jsou obvykle zalo¾eny na efektivním násobení
 164 matic -- dvì matice $n\times n$ mù¾eme vynásobit v~èase $\O(n^2.808)$ Strassenovým
 165 algoritmem~\cite{strassen:matmult}, pøípadnì asymptoticky nejrychlej¹ím známým algoritmem od Coppersmithe
 166 a Winograda~\cite{coppersmith:matmult} v~èase $\O(n^{2.376})$. Slavná hypotéza øíká,
 167 ¾e pro ka¾dé $\omega>2$ existuje algoritmus násobící matice se slo¾itostí $\O(n^\omega)$
 168 (blí¾e o~tomto fascinujícím tématu viz \cite{szegedy:matmult}). Oznaème tedy~$\omega$
 169 nejni¾¹í exponent, kterého jsme schopni dosáhnout.
 170
 171 Co se stane, kdy¾ mocníme matici sousednosti~$A$ grafu? V~matici $A^k$ se na pozici
 172 $i,j$ nachází poèet sledù délky~$k$, které vedou z~vrcholu~$i$ do vrcholu~$j$.
 173 (Snadný dùkaz indukcí vynecháváme.) Pro libovolné $k\ge n-1$ jsou tedy v~$(A+E)^k$
 174 (kde $E$ znaèí jednotkovou matici; doplnili jsme tedy do grafu smyèky) nenuly
 175 pøesnì tam, kde z~$i$ do~$j$ vede cesta.
 176
 177 To nám dává jednoduchý algoritmus pro výpoèet matice dosa¾itelnosti~$R$ ($R_{ij}$
 178 je 1 nebo~0 podle toho, zda z~$i$ do~$j$ vede cesta). Do~matice~$A$ doplníme
 179 na diagonálu jednièky a poté ji $\lceil \log_2 n\rceil$-krát umocníme na~druhou.
 180 Abychom se vyhnuli velkým èíslùm, nahradíme po ka¾dém umocnìní nenuly jednièkami.
 181 Celkem tedy provedeme $\O(\log n)$ násobení matic obsahující polynomiálnì velká
 182 èísla, co¾ trvá $\O(n^\omega\log n)$.
 183
 184 Na~tento postup se mù¾eme dívat i~obecnìji:
 185
 186 \s{Definice:} {\I $(\oplus,\otimes)$-souèin} matic~$A,B \in X^{n\times n}$
 187 kde $\oplus$ a~$\otimes$ jsou dvì asociativní binární operace na~mno¾inì~$X$,
 188 je matice~$C$ taková, ¾e
 189 $$
 190 C_{ij} = \bigoplus_{k=1}^n A_{ik}\otimes B_{kj}.
 191 $$
 192 Klasické násobení matic je tedy $(+,\cdot)$-souèin.
 193
 194 Uva¾ujme nyní podobnì jako v~pøedchozí sekci nìjakou funkci~$f$, která pøiøazuje
 195 mno¾inám sledù nìjaké hodnoty. Nech» $\oplus$ a $\otimes$ jsou operace,
 196 pro nì¾ platí $f(\alpha\alt\beta) = f(\alpha) \oplus f(\beta)$
 197 a $f(\alpha\beta) = f(\alpha) \otimes f(\beta)$.
 198
 199 Mìjme nyní pro ka¾dé $i,j$ nìjakou mno¾inu $\alpha_{ij}$ sledù z~$i$ do~$j$
 200 a matici~$A$ takovou, ¾e $A_{ij} = f(\alpha_{ij})$. Podobnì mìjme mno¾iny $\beta_{ij}$
 201 a pøíslu¹nou matici~$B$. Potom $(\oplus,\otimes)$-souèin matic $A$ a~$B$ je nìjaká
 202 matice~$C$, pro ní¾ platí:
 203 $$
 204 C_{ij} = f(\alpha_{i1}\beta_{1j} \alt \alpha_{i2}\beta_{2j} \alt \ldots \alt \alpha_{in}\beta_{nj}).
 205 $$
 206 Jinými slovy, matice~$C$ popisuje ohodnocení v¹ech sledù, které vznikly spojením
 207 sledu z~$\alpha$ se sledem z~$\beta$.
 208
 209 Pokud tedy zaèneme maticí popisující sledy délky 0 nebo~1 (to je obdoba matice sousednosti),
 210 staèí $\O(\log n)$ $(\oplus,\otimes)$-souèinù k~tomu, abychom znali ohodnocení v¹ech
 211 sledù délky právì~$k$ pro nìjaké $k\ge n$.
 212
 213 S~$(\lor,\land)$-souèiny a maticí sousednosti získáme algoritmus pro výpoèet dosa¾itelnosti
 214 (ka¾dý souèin pøitom mù¾eme provést jako násobení matic následované pøepsáním nenul na
 215 jednièky).
 216
 217 Podobnì mù¾eme poèítat i matici vzdáleností: zaèneme s~maticí délek hran doplnìnou o~nuly na~diagonále
 218 a pou¾ijeme $(\min,+)$-souèiny. Tyto souèiny ale bohu¾el neumíme pøevést na klasické násobení matic.
 219 Pøesto je známo nìkolik algoritmù efektivnìj¹ích ne¾ $\Theta(n^3)$, by» pouze o~málo:
 220 napøíklad Zwickùv \cite{zwick:apsp} v~èase $\O(n^3\sqrt{\log\log n}/\log n)$
 221 (zalo¾ený na dekompozici a pøedpoèítání malých blokù) nebo Chanùv \cite{chan:apsp} v~$\O(n^3/\log n)$
 222 (pou¾ívající geometrické techniky). Abychom porazili Floydùv-Warshallùv algoritmus,
 223 potøebovali bychom ov¹em vìt¹í ne¾ logaritmické zrychlení, proto¾e souèinù potøebujeme
 224 vypoèítat logaritmicky mnoho.
 225
 226 Dodejme je¹tì, ¾e pro grafy ohodnocené malými celými èísly je mo¾né vyu¾ít
 227 celou øadu dal¹ích trikù. Zájemce o~tento druh algoritmù odkazujeme na Zwickùv
 228 èlánek~\cite{zwick:apspint}.
 229
 230 %% FIXME: Indexovat matice mno¾inami, ne èísly
 231
 232 \h{Seidelùv algoritmus}
 233
 234 \h{Rozdìl a panuj}
 235
 236 \references
 237 \bye