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