5-cesty/5-cesty.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{5}{Nejkrat¹í cesty}{}
   4
   5 Na~této pøedná¹ce budeme studovat problém hledání nejkrat¹ích cest
   6 v~orientovaných grafech ohodnocených reálnými èísly.
   7
   8 \s{Situace:} Máme orientovaný graf~$G$ a funkci $\ell : E(G) \rightarrow {\bb R}$
   9 pøiøazující hranám jejich ohodnocení (délky). Pro vrcholy $u,v\in V(G)$ budeme
  10 chtít spoèítat jejich vzdálenost $d(u,v)$, co¾ bude délka nejkrat¹í cesty z~$u$
  11 do~$v$ nebo $\infty$, pokud ¾ádná cesta neexistuje.
  12
  13 Chceme, aby se vzdálenosti chovaly \uv{rozumnì}, tedy co nejvíce jako metrika. Orientovanost
  14 grafù nám kazí symetriènost -- nemusí nutnì platit $d(x, y)=d(y, x)$. Budeme aspoò chtít,
  15 aby platily následující vlastnosti:
  16
  17 \itemize\ibull
  18 \:$d(u, u) = 0$,
  19 \:$d(u, v) \leq d(u, w) + d(w, v)$ (trojúhelníková nerovnost).
  20 \endlist
  21
  22 To nemusí obecnì platit (kazí nám to záporné cykly), proto budeme studovat
  23 pouze grafy, v~nich¾ záporné cykly neexistují. Pak u¾ budou obì vlastnosti
  24 splnìny, jak plyne napøíklad z~následujícího lemmatu:
  25
  26 \s{Lemma:}
  27 V~grafu bez záporných cyklù existuje ke~ka¾dému nejkrat¹ímu sledu z~$u$ do~$v$ stejnì dlouhá $uv$-cesta.
  28
  29 \proof Máme-li nejkrat¹í $uv$-sled, který není cestou, opakuje se v~nìm nìjaký vrchol
  30 $w \in V(G)$ tedy $uv$-sled je $(u\dots w \dots w \dots v)$. Délka cyklu $c=(w\dots
  31 w)$ je $\ell(c) \geq  0$ tedy platí $\ell(u\dots w\dots v) \leq \ell(\hbox{pùvodní
  32 sled})$. Tento postup mù¾eme opakovat a po koneèném poètu krokù dostaneme cestu. Z
  33 toho plyne trojúhelníková nerovnost. \qed
  34
  35 \s{Jednoduché pøípady}
  36
  37
  38 \itemize\ibull
  39 \:Pokud $\ell$ je konstantní funkce, pou¾ijeme BFS. Èasová slo¾itost bude $\Theta(m+n)$.
  40 \:Délky hran jsou malá pøirozená èísla -- $\ell(x, y) \in\{1, \dots, L\}$: Podrozdìlíme hrany
  41 a pou¾ijeme BFS. Èasová slo¾itost $\Theta(Lm+n)$.
  42 \:V DAG (orientovaném acyklickém grafu) najdeme nejkrat¹í cestu
  43 indukcí pøes topologické uspoøádání v èase $\Theta(m+n)$.
  44 \endlist
  45
  46 \s{Obecný algoritmus}
  47
  48 \s{Definice:} $D_k(v):=$ minimální délka ze v¹ech sledù z $v_0$ do $v$ o právì $k$ hranách.
  49 $D_0(v)=0$ pokud $v=v_0$, jinak $D_0(v)=\infty$.
  50
  51 $d(v_0, v)=\min D_k(v)$ kde $1 \leq k \leq n-1$.
  52
  53 Jak spoèítat $D_k$ kdy¾ u¾ známe $D_0\dots D_{k-1}$? Zøejmnì $$D_k=\min
  54 \{D_{k-1}(u)+\ell(u, v)\}$$ pro taková $u$ ¾e $(u, v)\in E(G)$. Z tohoto mù¾eme udìlat
  55 jednoduchý algoritmus: postupnì pro v¹echna $k=0\dots n-1$ zjistíme v¹echna $D_k(z)$
  56 pro v¹echny vrcholy $z\in V(G)$. Délka nejkrat¹í cesty z $v_0$ do $v$ je $\min D_k(v)$
  57 kde $1 \leq k \leq n-1$.
  58
  59 Naivní implementace pobì¾í $n^2(\sum_v {\rm deg}^+(v))+n$ (musíme pøièíst na
  60 konec $n$ za izolované vrcholy), upravíme $\sum_v {\rm deg}^+(v)=m$. Bohu¾el
  61 spotøebujeme $\Theta(n^2)$ pamìti.
  62
  63 Nevýhodou této implementace je pøistupování k hranám pozpátku. Pojïme zkusit nepatrnì
  64 odli¹ný pøístup.
  65
  66 \s{Bellmanùv-Fordùv algoritmus}
  67 \algo
  68 \:$D(*) \leftarrow \infty, D(v_0) \leftarrow 0$
  69 \:Pro $k=1, \dots, n-1$:
  70 \::Pro $\forall v\in V(G)$:
  71 \:::Pro $\forall w$ takové ¾e $(v, w)\in E(G)$:
  72 \::::$D(w)\leftarrow \min(D(w), D(v)+\ell(v, w))$
  73 \endalgo
  74
  75 Pokud by algoritmus i v $n$-tém kroku nìco zmìnil, graf obsahuje záporný cyklus.
  76
  77 \s{Vìta:} Bellmanùv -- Fordùv algoritmus najde v èase $\Theta(nm)$ vzdálenosti $d(v_0, v)$
  78 z $v_0$ do v¹ech $v\in V(G)$.
  79
  80 \proof
  81 Invarianty:
  82 \itemize\ibull
  83 \:Koneèné $D(v)$ v¾dy odpovídá délce nìjakého sledu z $v_0 \rightarrow v $.
  84 \endlist
  85
  86 Pro vrchol $v_0$ urèitì existuje sled nulové délky z $v_0$ do $v_0$.
  87
  88 Jak se z pùvodního nekoneèného $D(v)$ mohlo stát koneèné? Na¹li jsme takovou hranu,
  89 která vedla z vrcholu $w$ s koneèným $D(w)$ do vrcholu $v$. Tedy do $v$ existuje sled.
  90
  91 Pokud sní¾ím $D(v)$, znamená to, ¾e jsem do vrcholu $v$ na¹el krat¹í sled.
  92
  93 \itemize\ibull
  94 \:Na konci $k$-tého prùchodu vnìj¹ím cyklem platí $D(w)\leq \min$ délka sledu z $v_0$
  95 do $v$ o nejvý¹e $k$ hranách. Z èeho¾ plyne ¾e na konci je $D(w)\leq d(v_0, v)$.
  96 \endlist
  97
  98 Nech» nejkrat¹í sled $v_0\rightarrow w$ o nejvý¹e $k$ hranách konèí hranou $(v, w)$.
  99 Zastavme algoritmus v okam¾iku, kdy v $k$-tém prùchodu zpracovává hranu $(v, w)$ tehdy
 100 $D(w)\leq D(v)+\ell(v, w)$ a $D(v)$ je dle indukèního pøedpokladu men¹í nebo rovno
 101 minimální délce sledu z $v_0$ do $v$ o nejvý¹e $k$ hránách.
 102 \qed
 103
 104 V Bellman -- Fordovì algoritmu jsme v podstatì zlep¹ovali odhady na nejkrat¹í cestu.
 105 Pojïme vymyslet algoritmus zalo¾ený na podobné my¹lence.
 106
 107 \s{\uv{Prùzkumnický algoritmus}} Pro ka¾dý vrchol budeme udr¾ovat jeho ohodnocení
 108 (doèasnou vzdálenost) $D(v)$ a stav vrcholu $S(v)$. Stav mù¾e být buï $N$ nevidìn --
 109 vrchol jsme je¹tì nepotkali, $O$ otevøen -- od posledního prozkoumání se $D(v)$
 110 zmìnilo nebo $Z$ zavøen -- není potøeba zkoumat znovu, nic by se nezmìnilo. Abychom
 111 mohli nejkrat¹í cestu na konci bìhu také zrekonstruovat, budeme si je¹tì udr¾ovat $P(v)$
 112 pøedchùdce vrcholu $v$.
 113
 114 \algo
 115 \:$D(*)\leftarrow \infty, D(v_0)=0, S(*)\leftarrow N, S(v_0)\leftarrow O,
 116 P(*)\leftarrow ?$
 117 \:Dokud $\exists u$: $S(u)=O$ opakuj:
 118 \::$S(u)\leftarrow Z$
 119 \::Pro $\forall v: (u, v)\in E(G)$:
 120 \:::Je-li $D(u)+\ell(u, v)<D(v)$
 121 \::::$D(v)\leftarrow D(u)+\ell(u, v)$
 122 \::::$S(v)\leftarrow O$
 123 \endalgo
 124
 125 \s{Invariant:} $D(v)$ neroste a odpovídá délce nìjakého sledu z $v_0$ do $v$.
 126
 127 $D(v)$ volíme jako minimum z $D(v)$ a $D(u)+\ell(u, v)$, proto nikdy nemù¾e vzrùst.
 128
 129 Dùkaz toho, ¾e $D(v)$ odpovídá délce nìjakého sledu z $v_0$ do $v$ je stejný jako u
 130 Bellman -- Fordova algoritmu.
 131
 132 \s{Lemma:} Algoritmus se zastaví pøi jakémkoliv poøadí zavíraných vrcholù. Èas pøi
 133 nevhodném zavírání mù¾e být a¾ exponenciální.
 134
 135 \>Toto lemma bude zanecháno bez dùkazu, nebo» ho nebudeme potøebovat pro dùkaz
 136 správnosti algoritmù, které od \uv{prùzkumnického algoritmu} odvodíme.
 137
 138 \s{Lemma:} Pokud se algoritmus zastaví, pak dosa¾itelné vrcholy jsou zavøené a
 139 kdykoliv $S(v)=Z$, platí $D(v)=d(v_0, v)$.
 140
 141 \proof Nech» cesta z $v_0$ do $v$ je co do poètu hran nejmen¹í protipøíklad, pak musí
 142 existovat vrchol $u$, pro který neplatí $S(u)=Z$. Co¾ je spor, proto¾e takový vrchol
 143 musel ná¹ algoritmus projít.
 144
 145 Vezmìme minimání protipøíklad co do poètu hran. Nech» $v$ je nejbli¾¹í vrchol od $u$
 146 takový, ¾e $D(v)\neq d(v_0, v)$, tudí¾ musí být vìt¹í, ne¾ by mìl být, proto¾e
 147 odpovídá délce nìjakého sledu. Oznaème $u$ pøedchùdce vrcholu $v$ na nejkrat¹í cestì.
 148 Víme, ¾e $D(u)$ je správnì. Algoritmus zkoumal $u$ nastavil finální $D(u)$, tedy
 149 pøitom zpracoval hranu $(u, v)$ a $D(v)\leq D(u)+\ell(u, v)$, co¾ je opravdová
 150 vzdálenost. Dostali jsme spor s tím, ¾e $D(x)$ neroste. \qed
 151
 152 \bye