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 $l : 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 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)$. Délka cyklu  $\ell(c) \geq  0 \Rightarrow \ell(u\dots v\dots w) \leq \ell(\hbox{pùvodní
  31 sled})$. Tento postup mù¾eme opakovat a po koneèném poètu krokù dostaneme cestu, tedy
  32 platí trojúhelníková nerovnost. \qed
  33
  34 \s{Jednoduché pøípady}
  35
  36
  37 \itemize\ibull
  38 \:Pokud $l$ je konstantní funkce, pou¾ijeme BFS. Èasová slo¾itost bude $\Theta(m+n)$.
  39 \:Délky hran jsou malá pøirozená èísla $\ell(x, y) \in\{1, \dots, L\}$ podrozdìlíme hrany
  40 a pou¾ijeme BFS. Èasová slo¾itost $\Theta(Lm+n)$.
  41 \:DAG (orientovaný acyklický graf) indukcí pøes topologické uspoøádání v èase
  42 $\Theta(m+n)$.
  43 \endlist
  44
  45 \s{Definice:} $D_k(v):=$ minimální délka ze v¹ech sledù z $v_0$ do $v$ o právì $k$ hranách.
  46 $D_0(v)=0$ pokud $v=v_0$, jinak $D_0(v)=\infty$.
  47 $d(v_0, v)=\min D_k(v)$ kde $1 \leq k  \leq n-1$.
  48
  49 Kdy¾ známe $D_0 \dots D_{k-1}$ spoèteme $D_k=\min D_{k-1}(u)+\ell(u, v)$ pro taková $u$
  50 ¾e $(u, v)\in E(G)$.
  51
  52 Naivní implementace pobì¾í $n(\sum_v {\rm deg}^+(v))+n$ (musíme pøièíst na
  53 konec $n$ za izolované vrcholy), upravíme $\sum_v {\rm deg}^+(v)=m$. Bohu¾el
  54 spotøebujeme $\Theta(n^2)$ pamìti.
  55
  56 Nevýhodou této implementace je pøistupování k hranám pozpátku.
  57
  58 \s{Bellmanùv-Fordùv algoritmus}
  59 \algo
  60 \:$D(*) \leftarrow \infty, D(s) \leftarrow 0$
  61 \:Pro $k=1, \dots, n-1$:
  62 \::$D_k(*) \leftarrow \infty$
  63 \::Pro $\forall v\in V(G)$:
  64 \:::Pro $\forall w (v, w)\in E(G)$:
  65 \::::$D(w)\leftarrow \min(D(w), D_{k-1}(v)+\ell(v, w))$
  66 \endalgo
  67
  68 Pokud by i v $n$-tém kroku nìco vykonal, graf obsahuje záporný cyklus.
  69
  70 \s{Vìta:} Bellmanùv--Fordùv algoritmus najde v èase $\Theta(nm)$ vzdálenosti $d(v_0, v)$
  71 pro $\forall v\in V(G)$.
  72
  73 \proof
  74 Invarianty:
  75 \itemize\ibull
  76 \:Koneèné $D(v)$ v¾dy odpovídá délce nìjakého sledu z $v_0 \rightarrow w$
  77 \:Na konci $k$-tého prùchodu vnìj¹m cyklem platí $D(w)\leq \min$ délka sledu z $v_0
  78 \rightarrow v$ o ménì ne¾ $k$ hranách z toho plyne ¾e na konci $D(w)\leq d(v_0, v)$
  79
  80 Nech» nejkrat¹í sled $v_0\rightarrow w$ o ménì ne¾ $k$ hranách konèí hranou $(v, w)$,
  81 zastavme algoritmus v okam¾iku kdy v $k$-tém prùchodu zpravovává hranu $(v, w)$ tehdy
  82 $D(w)\leq D(v)+\ell(v, w)$ a $D(v)$ je dle indukèního pøedpokladu men¹í nebo rovný
  83 minimální délce sledu $v_0\rightarrow v$ o $\leq k$ hránách.
  84 \endlist
  85 \qed
  86
  87 \s{\uv{Prùzkumnický algoritmus}}
  88 Stav: $D(v)$ je délka zatím nejkrat¹í nalezené cesty do vrcholu $v$, $S(v)$ stav
  89 vrcholu ($N$ nevidìn -- vrchol jsme je¹tì nepotkali, $O$ otevøen -- od posledního prozkoumání
  90 se $D(v)$ zmìnilo, $Z$ zavøen -- není potøeba zkoumat znovu, nic by se nezmìnilo). $P(v)$ je
  91 pøedchùdce $v$.
  92
  93 \algo
  94 \:$D(*)\leftarrow \infty, D(v_0)=0, S(*)\leftarrow N, S(v_0)\leftarrow O,
  95 P(*)\leftarrow ?$
  96 \:Dokud $\exists u$: $S(u)=O$ opakuj:
  97 \::$S(u)\leftarrow Z$
  98 \::Pro $\forall v: (u, v)\in E(G)$:
  99 \:::Je-li $D(u)+\ell(u, v)<D(v)$
 100 \::::$D(v)\leftarrow D(u)+\ell(u, v)$
 101 \::::$S(v)\leftarrow O$
 102 \endalgo
 103
 104 \s{Invariant} $D(v)$ neroste a odpovídá délce nìjakého sledu z $v_0$ do $v$.
 105
 106 \s{Lemma} Algoritmus se zastaví pøi jakémkoliv poøadí zavíraných vrcholù. Èas pøi
 107 nevhodném zavírání mù¾e být a¾ exponenciální.
 108
 109 \>Toto lemma bude zanecháno bez dùkazu.
 110
 111 \s{Lemma} Pokud se zastaví, pak dosa¾itelné vrcholy jsou zavøené a $S(v)=Z$ pak platí
 112 $D(v)=d(v_0, v)$.
 113
 114 \proof
 115 Nech» cesta z $v_0$ do $v$ je nejmen¹í protipøíklad, pak musí existovat vrchol $u$,
 116 pro který neplatí $S(u)=Z$. Co¾ je spor, proto¾e takový vrchol musel ná¹ algoritmus
 117 projít.
 118
 119 Vezmìme minimání protipøíklad co do poètu hran. Nech» $v$ je nejbli¾¹í vrchol takový
 120 ¾e $D(v)\neq d(v_0, v)$, tudí¾ musí být vìt¹í (odpovídá délce nìjakého sledu). $u:=$
 121 pøedchùdce $v$ na nejkrat¹í cestì tedy $D(u)$ je správnì. Algoritmus zkoumal u na
 122 nastavil finální $D(u)$, tedy zpracoval hranu $(u, v)$ a $D(v)\leq D(u)+\ell(u, v)$, co¾
 123 je opravdová vzdálenost. Dostali jsme spor s tím, ¾e $D(x)$ neroste.
 124 \qed
 125
 126 \bye