10-cesty/10-cesty.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{10}{Nejkrat¹í cesty}{(zapsali L. Banáková, O. Hoferek, J. Bøeèka)}
   4
   5 \s{Definice:} {\I Vzdálenost vrcholù} $d(u,v)$ je délka nejkrat¹í cesty $(u,v)$,
   6 pokud existuje, nebo $+\infty$, pokud taková cesta neexistuje.
   7
   8 \s{Problém:} Je dán graf G a funkce $l: E(G) \rightarrow {\bb R}$ pøiøazující
   9 hranám jejich délky. Dále je dán startovací a cílový vrchol
  10 $s,c~\in~V(G)$. Chceme najít cestu $s=v_1, v_2, \dots, v_k=c$ takovou, aby délka cesty
  11 $$l(v_1, v_2) + l(v_2, v_3) + \dots + l(v_{k-1}, v_k)$$
  12 byla minimální. Takovéto cestì budeme øíkat {\I nejkrat¹í cesta} z~$s$~do~$c$.
  13
  14 \noindent
  15 Bez újmy na obecnosti budeme pøedpokládat, ¾e graf $G$ je orientovaný, bez smyèek a
  16 násobných hran.
  17
  18 \noindent
  19 Nejprve uvá¾íme pøípady, kdy jsou v¹echny hrany stejnì dlouhé. Tehdy mù¾eme pou¾ít
  20 algoritmus prohledávání do ¹íøky (BFS). K jeho implementaci je zapotøebí fronta $Q$ s
  21 metodami $Put(Q, v)$ (pøidání prvku $v$ na konec fronty) a $Get(Q)$ (odebrání
  22 prvku ze zaèátku fronty). Algoritmus vrátí pole \uv{znaèek} $z$: $z(v) = 1$ právì tehdy
  23 pokus je vrchol $v$ dostupný ze startovacího vrcholu $s$, jinak $z(v) = 0$.
  24
  25 \s{Algoritmus:} (Prohledávání do ¹íøky (BFS))
  26
  27 \algo
  28 \:$z(*) \leftarrow 0, z(s) \leftarrow 1$
  29 \:$Q \leftarrow \{s\}$
  30 \:while $Q \not= \emptyset :$
  31 \::$v \leftarrow Get(Q)$
  32 \::for $\forall w: (v,w)\in E$
  33 \:::if $z(w) = 0$ then
  34 \::::$z(w) \leftarrow 1$
  35 \::::$Put(Q, w)$
  36 \endalgo
  37
  38 \s{Lemma È (èasové):} BFS dobìhne v~èase $\O(m+n)$.
  39
  40 \proof
  41 Ka¾dý vrchol se do fronty dostane maximálnì jednou a ka¾dou hranu zpracujeme
  42 maximálnì jednou.
  43 \qed
  44
  45 \s{Lemma D (dosa¾itelnost):} BFS oznaèí právì vrcholy dostupné ze $s$.
  46
  47 \proof
  48
  49 \noindent
  50 \uv{$\Rightarrow$}: Indukcí podle bìhu algoritmu.
  51
  52 \noindent
  53 \uv{$\Leftarrow$}: Doká¾eme sporem. Uva¾me, ¾e existuje vrchol dostupný, ale algoritmem
  54 neoznaèený. Vezmìme takovýto \uv{¹patný} vrchol $v$, který je $s$ nejblí¾e. Uva¾me
  55 nejkrat¹í cestu $(s,v)$: $s,\dots,u,v$. Pøedchozí vrchol na této cestì $u$
  56 musí být \uv{dobrý}. Vrchol $u$ se dostane do fronty, pak je z~ní vybrán a tím
  57 se zpracuje i vrchol $v$ $\Rightarrow$ spor.
  58
  59 Pøedchozím algoritmem jsme pouze zjistili, které vrcholy jsou z~$s$ dosa¾itelné.
  60 Nyní si tento algoritmus modifikujeme tak, abychom na¹li $d(s,v)$ pro v¹echna
  61 $v~\in~V(G)$.
  62
  63 \s{Roz¹íøený algoritmus:} (Prohledávání do ¹íøky (BFS))
  64
  65 \algo
  66 \:$z(*) \leftarrow 0, z(s) \leftarrow 1$
  67 \:$D(*) \leftarrow +\infty, D(s) \leftarrow 0$
  68 \:$Q \leftarrow \{s\}$
  69 \:while $Q \not= \emptyset :$
  70 \::$v \leftarrow Get(Q)$
  71 \::for $\forall w: (v,w)\in E$
  72 \:::if $z(w) = 0$ then
  73 \::::$z(w) \leftarrow 1$
  74 \::::$D(w) \leftarrow D(v) + 1$
  75 \::::$Put(Q, w)$
  76 \endalgo
  77
  78 \noindent
  79 Prùbìh tohoto algoritmu si mù¾eme ukázat na následujícím obrázku (\uv{praseèí graf}):
  80
  81 \figure{praseci-graf.eps}{Praseèí graf}{75mm}
  82
  83 \s{Definice:} {\I Vrstva} $ L_i\subseteq V $ : $ L_0 = \{s\} $ , $ L_{i+1} = $
  84 $ \{ w$ : $ w $  oznaèen pøi procházení vrcholu $ v \in L_i $$ \} $
  85
  86 \s{Lemma V (vzdálenosti):} Na konci BFS je $\forall v: D(v) = d(s,v)$.
  87
  88 \proof
  89
  90 \noindent
  91 a) pro nedosa¾itelné vrcholy: OK (algoritmus je neoznaèí $\Rightarrow D(v) = \infty$)
  92
  93 \noindent
  94 b) pro dosa¾itelné vrcholy: Víme, ¾e pro vrchol $v \in L_i$ platí $D(v)=i$,
  95 staèí tedy zjistit, zda $\forall i: \forall v \in L_i$ je $d(s,v)=i$. To ovìøíme matematickou indukcí
  96 podle~$i$:
  97
  98 pro $i=0$: evidentní,
  99
 100 pro $i>0$: Pøi procházení vrstvy $L_{i-1}$ musí být vrchol $v$ takový, ¾e $d(s,v)=i$, oznaèen
 101 a zároveò nemohl být oznaèen døíve a tudí¾ patøí do $L_i$.
 102 \qed
 103
 104 \noindent
 105 V¹imnìme si, ¾e v~grafu existují pouze tøi typy hran vzhledem k na¹emu algoritmu:
 106 \itemize\ibull
 107 \:dopøedu o jednu vrstvu
 108 \:dozadu o jednu nebo víc vrstev
 109 \:ve vrstvì
 110 \endlist
 111
 112 Abychom na¹li i samotné cesty, nejen jejich délky, modifikujeme svùj algoritmus tak,
 113 ¾e si pro ka¾dý vrchol $v$, který oznaèíme, budeme pamatovat jeho pøedchùdce $p(v)$:
 114
 115 \algo
 116 \:$z(*) \leftarrow 0, z(s) \leftarrow 1$
 117 \:$D(*) \leftarrow +\infty, D(s) \leftarrow 0$
 118 \:$p(*) \leftarrow$ ?
 119 \:$Q \leftarrow \{s\}$
 120 \:while $Q \not=  \emptyset :$
 121 \::$v \leftarrow Get(Q)$
 122 \::for $\forall w: (v,w)\in E$
 123 \:::if $z(w) = 0$ then
 124 \::::$z(w) \leftarrow 1$
 125 \::::$D(w) \leftarrow D(v) + 1$
 126 \::::$p(w) \leftarrow v$
 127 \::::$Put(Q, w)$
 128 \endalgo
 129
 130 \s{Pozorování:} Pokud $p(v) \not=$ ? $\Rightarrow D(v) = D(p(v)) + 1$.
 131
 132 \s{Lemma S (stromové):} Graf $(W,F)$, kde $W$ = dosa¾itelná èást $V$, $F = \{(v,p(v))\}$
 133 je strom orientovaný do~koøene $s$. Navíc ukazuje nejkrat¹í cestu pro ka¾dý dosa¾itelný
 134 vrchol (pro ka¾dý vrchol v tomto grafu, existuje jediná orientovaná cesta do koøene
 135 $s$, která je zároveò nejkrat¹í cesta z $s$ do tohoto vrcholu).
 136
 137 \noindent
 138 Nyní uva¾me, ¾e délky hran $l$ nejsou v¹echny stejnì dlouhé:
 139
 140 Uká¾eme si trik pro ohodnocené hrany: hranu délky $l$
 141 podrozdìlíme na $l$ hran délky 1 a pak spustíme BFS. Algoritmus pobì¾í s èasovou
 142 slo¾itostí $O((m+n)l_{max})$. To není zrovna moc výhodné, a proto si uká¾eme tzv. {\I Budíkovou taktiku}:
 143
 144 Místo toho, abychom ka¾dou hranu podrozdìlovali, si budeme pro ka¾dý vrchol pamatovat \uv{èas budíku} $b$.
 145 Èasem $b(v)$ budíku vrcholu~$v$ rozumíme èas, kdy se do tohoto vrcholu vlna dostane, kdy¾ se bude ¹íøit po
 146 dosud známých hranách. Na zaèátku nastavíme $\forall v \in V: b(v) = l(s,v)$ a pokud pøi bìhu
 147 algoritmu objevíme hranu, která nám umo¾ní dostat se do $v$ rychleji, tak hodnotu $b(v)$ zmìníme.
 148 Algoritmus pak bude pracovat tak, ¾e bude spát, dokud nezazvoní nìjaký budík (co¾ znamená, ¾e
 149 jsme dorazili do nìjakého vrcholu).
 150
 151 Tato taktika nás pøivede k Dijkstrovu algoritmu, kde se ze dvoustavového $z(v)$ stane tøístavové
 152 $z(v)) \in \{{\bf{N}}, {\bf{V}}, {\bf{H}}\}$, kde {\bf{N}} znamená nevidìn, {\bf{V}} vidìn a {\bf{H}} hotov. Podle hodnoty $z(v)$ se
 153 pak $D(v)$ rovná $+\infty$ pro $z(v) = {\bf{N}}$, èasu budíku pro $z(v) = {\bf{V}}$ nebo vzdálenosti $d(s,v)$ pro $z(v) = {\bf{H}}$.
 154
 155 \s{Algoritmus:} (Dijkstrùv algoritmus)
 156
 157 \algo
 158 \:$z(*) \leftarrow {\bf{N}}, z(s) \leftarrow {\bf{V}}$
 159 \:$D(*) \leftarrow +\infty , D(s) \leftarrow 0$
 160 \:$p(*) \leftarrow $?
 161 \:while $\exists v : z(v) = {\bf{V}} :$
 162 \::$v \leftarrow $ vrchol, pro nìj¾ $z(v)={\bf{V}}$ a zároveò $D(v)$ je minimální
 163 \::$z(v) \leftarrow {\bf{H}}$
 164 \::for $\forall w : (v,w) \in E$:
 165 \:::if $D(w)>D(v) + l(v,w)$ then
 166 \::::$D(w) \leftarrow D(v) + l(v,w)$
 167 \::::$z(w) \leftarrow {\bf{V}}$
 168 \::::$p(w) \leftarrow v$
 169 \endalgo
 170
 171 \s{Vìta:} Pokud $\forall v,w: l(v,w) \in \bb{Z}^+ \cup \{\infty\}$, pak Dijkstrùv algoritmus
 172 najde nejkrat¹í cesty v èase $\O(n^2)$.
 173
 174 \proof
 175 V prùbìhu algoritmu se maximálnì $n$-krát hledá vrchol $v$ s minimálním $D(v)$,
 176 maximálnì $m$-krát se pøenastavuje $D(v)$. Pokud bude struktura $D$ ulo¾ena jako
 177 pole (hledání minima v $\O(n)$, zmìna hodnoty $\O(1)$), bude celková
 178 èasová slo¾itost Dijkstrova algoritmu $\O(n^2 + m) = \O(n^2)$. Fakt, ¾e se algoritmus
 179 zastaví je evidentní, proto¾e se stav ¾ádného vrcholu nevrací z {\bf{H}} do {\bf{V}}.
 180
 181 Úplný dùkaz správnosti a èasové slo¾itosti i pro hrany ohodnocené reálnými èísly
 182 bude na pøí¹tí pøedná¹ce.
 183 \qed
 184
 185 Nahlédnìme nyní, zda by vedlo k~vylep¹ení èasové slo¾itosti, kdybychom pøi~implementaci
 186 Dijkstrova algoritmu pou¾ili jako datovou strukturu pro ukládání vidìných vrcholù rùzné typy hald.
 187 Provádìli bychom s~nimi operace \<DeleteMin> (maximálnì $n$-krát) a \<Decrease> (maximálnì $m$-krát). Zmínìné
 188 operace mají pro rùzné typy hald následující èasové slo¾itosti:
 189 $$\vbox{\halign{\strut # \quad & # \quad & # \quad & #\cr
 190 & \it binární halda & \it $k$-regulární halda & \it Fibonacciho halda\cr
 191 \noalign{\smallskip}
 192 \<DeleteMin> & $\O(\log{n})$ & $\O(k\log_k{n})$ & $\O(\log{n})$ \cr
 193 \<Decrease> & $\O(\log{n})$ & $\O(\log_k{n})$ & $\O(1)$ \cr
 194 {\I celková slo¾itost} & $\O((m+n)\log{n})$ & $\O(m\log_{m/n}{n})$ & $\O(n\log{n}+m)$ \cr
 195 }}$$
 196
 197 Pou¾ijeme-li klasickou haldu, dostaneme celkovou èasovou slo¾itost $\O((m+n)\log{n})$, co¾ znamená,
 198 ¾e jsme si pomohli v pøípadech, kdy je graf \uv{øídký}. U $k$-regulární haldy se celková èasová slo¾itost
 199 rovná $\O(nk\log_k{n}+m\log_k{n})$, ideálnì pro $k=m/n$: $\O(m\log_{m/n}{n})$. Prozkoumejme,
 200 jak se nám v tomto pøípadì bude mìnit èasová slo¾itost pro rùznì \uv{husté} grafy:
 201 \itemize\ibull
 202 \:$m \approx n \rightarrow \O((m+n)\log{n})$
 203 \:$m \approx n^2 \rightarrow \O(m)$
 204 \:$m \approx n^{1+\epsilon} \rightarrow \O(m) \dots (k=m/n= n^\epsilon)$
 205 \endlist
 206 \noindent
 207 Pøi pou¾ití Fibonacciho haldy je pak celková èasová slo¾itost rovna $\O(n\log{n}+m)$.
 208
 209 \medskip
 210
 211 Nyní si pøedvedeme trochu jiný algoritmus na prohledávání grafu. Mìjme matici sousednosti $A$
 212 ke grafu $G = (V, E)$: $ A_{ij} = 1 \Leftrightarrow (v_i, v_j) \in E $, jinak $A_{ij} = 0$. Potom
 213 $A^2_{ij} = \sum_{k=1}^n A_{ik}A_{kj} $. Tento souèet je nenulový právì tehdy, kdy¾
 214 vrcholy $i$,$k$,$j$ tvoøí sled délky 2. Jinými slovy $A^2_{ij}$ se rovná poètu sledù
 215 délky 2 v $G$ z $i$ do $j$. Obdobnì $A^k_{ij}$ = poèet sledù délky $k$. Pokud
 216 k matici $A$ pøièteme jednotkovou matici ${\bb E}_n$ (èím¾ si pøimyslíme smyèky),
 217 dostaneme po umocnìní:
 218
 219 $ (A+{\bb E}_n)^k_{ij} \neq 0 \Leftrightarrow \exists$ $i,j$-sled délky maximálnì $k$.
 220
 221 Výstupem algoritmu tedy bude matice $(A + {\bb E}_n)^n$. Mù¾eme si také v¹imnout, ¾e
 222 pokud matici $A + {\bb E}_n$ umocníme na èíslo vìt¹í ne¾ $n$, tak výsledek bude poøád
 223 správný, jen bude výpoèet trvat déle. Tak¾e algoritmus mù¾e pracovat
 224 v iteracích umocòováním matice na druhou: $M_0 = A + {\bb E}_n$, $M_1 = M^2_0$, $M_{i+1} = M^2_i$.
 225 Výstupní matice bude tudí¾:
 226
 227 $ M_{\lceil \log{n} \rceil (ij)} \neq 0 \Leftrightarrow \exists$ cesta z $i$ do $j$
 228
 229 Na výpoèet dosa¾itelnosti vrcholù v grafu tedy staèí $\O(\log{n})$ násobení matic,
 230 a pokud na toto pou¾ijeme Strassenùv algoritmus, dostaneme
 231 ve výsledku algoritmus se slo¾itostí $\O(n^{\log_2{7}}\log{n})$.
 232
 233 \bye