\def\ppsp{1-1}
\def\sssp{1-$n$}
\def\apsp{$n$-$n$}
+\def\astar{A\kern-0.15em *}
Problém hledání nejkrat¹í cesty v~(obvykle ohodnoceném orientovaném) grafu
provází teorii grafových algoritmù od~samých poèátkù. Základní algoritmy
pro hledání cest jsou nedílnou souèástí základních kursù programování
a algoritmù, my se budeme vìnovat zejména rùzným jejich vylep¹ením.
-Mìjme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena
-{\I délkou} $\ell(e)$, co¾ je nìjaké reálné èíslo. Pro libovolnou
-posloupnost hran~$P$ (speciálnì tedy pro sled nebo cestu) definujeme
-její délku $\ell(P)$ jako souèet délek v¹ech hran posloupnosti.
-Za {\I vzdálenost} $d(u,v)$ dvou vrcholù prohlásíme nejmen¹í mo¾nou
-délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho,
+Uva¾ujme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena
+{\I délkou} $\ell(e)\in{\bb R}$. Mno¾inì hran (tøeba sledu nebo cestì)
+pak pøiøadíme délku rovnou souètu délek jednotlivých hran.
+
+Pro vrcholy $u,v$ definujeme jejich {\I vzdálenost} $d(u,v)$ jako nejmen¹í
+mo¾nou délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho,
minimum v¾dy existuje). Pokud z~$u$ do~$v$ ¾ádná cesta nevede, polo¾íme
$d(u,v) := \infty$.
-Obvykle se studují následující tøi varianty problému:
+Obvykle se studují následující tøi problémy:
\itemize\ibull
\:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkrat¹í
- ze~v¹ech cest z~daného vrcholu~$u$ do~daného vrcholu~$v$.
+ cestu z~daného vrcholu~$u$ do~daného vrcholu~$v$. (Pokud je nejkrat¹ích cest
+ více, tak libovolnou z~nich.)
\:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
nalézt nejkrat¹í cesty do~v¹ech ostatních vrcholù.
\:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkrat¹í cesty
Pøekvapivì, tak obecnì, jak jsme si uvedené problémy definovali, je neumíme
øe¹it v~polynomiálním èase: pro grafy, které mohou obsahovat hrany záporných
délek bez jakýchkoliv omezení, je toti¾ hledání nejkrat¹í cesty NP-tì¾ké
-(lze na~nìj snadno pøevést existence hamiltonovské cesty). V¹echny známé
+(lze na~nìj snadno pøevést existenci hamiltonovské cesty). V¹echny známé
polynomiální algoritmy toti¾ místo nejkrat¹í cesty hledají nejkrat¹í sled
--- nekontrolují toti¾ nijak, zda cesta neprojde jedním vrcholem vícekrát.
+-- nijak nekontrolují, zda cesta neprojde jedním vrcholem vícekrát.
Na¹tìstí pro nás je to v~grafech bez cyklù záporné délky toté¾: pokud se
v~nalezeném sledu vyskytne cyklus, mù¾eme jej \uv{vystøihnout} a tím získat
-sled, který není del¹í, a~který má ménì hran. Ka¾dý nejkrat¹í sled tedy
+sled, který není del¹í a~který má ménì hran. Ka¾dý nejkrat¹í sled tak
mù¾eme upravit na~stejnì dlouhou cestu.
V~grafech bez záporných cyklù je tedy jedno, zda hledáme sled nebo cestu;
naopak vyskytne-li se záporný cyklus dosa¾itelný z~poèáteèního vrcholu,
Navíc se nám bude hodit, ¾e ka¾dý prefix nejkrat¹í cesty je opìt nejkrat¹í
cesta. Jinými slovy pokud nìkterá z~nejkrat¹ích cest z~$u$ do~$v$ vede
pøes nìjaký vrchol~$w$, pak její èást z~$u$ do~$w$ je jednou z~nejkrat¹ích
-cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í
-cestu.)
+cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í.)
-Díky této vlastnosti mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom
-nejkrat¹ích cest}~${\cal T}(u)$. To je strom definovaný na~vrcholech zadaného
-grafu~$G$, zakoøenìný v~$u$ a orientovaný smìrem od~koøene, takový, ¾e pro ka¾dý
-vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou z~nejkrat¹ích
-cest z~$u$ do~$v$ v~grafy~$G$.
+Díky této {\I prefixové vlastnosti} mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom
+nejkrat¹ích cest}~${\cal T}(u)$. To je nìjaký podgraf grafu~$G$, který má tvar
+stromu zakoøenìného v~$u$ a orientovaného smìrem od~koøene, a~platí pro nìj, ¾e
+pro ka¾dý vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou
+z~nejkrat¹ích cest z~$u$ do~$v$ v~pùvodním grafu.
\s{Pozorování:} Strom nejkrat¹ích cest v¾dy existuje.
Nech» $u=v_1,\ldots,v_n$ jsou v¹echny vrcholy grafu~$G$. Indukcí budeme
dokazovat, ¾e pro ka¾dé~$i$ existuje strom~${\cal T}_i$, v~nìm¾ se nacházejí nejkrat¹í
cesty z~vrcholu~$u$ do vrcholù $v_1,\ldots,v_i$. Pro $i=1$ staèí uvá¾it
-strom obsahující pouze vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
+strom obsahující jediný vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkrat¹í cestu z~$u$ do~$v_i$
a oznaèíme~$z$ poslední vrchol na~této cestì, který se je¹tì vyskytuje v~${\cal T}_{i-1}$.
Úsek nejkrat¹í cesty od~$z$ do~$v_i$ pak pøidáme do~${\cal T}_{i-1}$
sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota men¹í ne¾~$h(w)$,
tak jí $h(w)$ pøepí¹eme.
-Relaxace tedy zachovává to, ¾e ohodnocení odpovídá délkám nìjakých sledù,
-a~souèasnì toto ohodnocení mù¾e zlep¹ovat. Budeme se tedy sna¾it nìjaké
-poèáteèní ohodnocení (nabízí se $h(u)=0$, $h(v)=\infty$ pro $v\ne u$)
-postupnými relaxacemi pøetvoøit na~ohodnocení vzdálenostmi.
-
Abychom zabránili opakovaným relaxacím tého¾ vrcholu, které nic nezmìní,
budeme rozli¹ovat tøi stavy vrcholù: {\I nevidìn} (je¹tì jsme ho nenav¹tívili),
{\I otevøen} (zmìnilo se ohodnocení, èasem chceme relaxovat) a {\I uzavøen}
\::$v\leftarrow\hbox{libovolný otevøený vrchol}$.
\::$\<stav>(v)\leftarrow\<uzavøen>$.
\::Relaxujeme~$v$:
-\:::Pro v¹echny hrany $(v,w)$ opakujeme:
+\:::Pro v¹echny hrany $vw$ opakujeme:
\::::Je-li $h(w) < h(v) + \ell(v,w)$:
\:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
\:::::$\<stav>(w)\leftarrow\<otevøen>$.
\endalgo
Podobnì jako u~minimálních koster, i zde se jedná o~meta-algoritmus, proto¾e
-v~kroku~4 nespecifikuje, podle jakého pravidla se vrchol~$v$ vybírá. Pøesto
+v~kroku~4 nespecifikuje, který z~otevøených vrcholù vybírá. Pøesto
ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu
výbìru nezávisejí.
\s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak:
\numlist\nparen
-\:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu -- doká¾eme indukcí podle poètu krokù algoritmu.
-\:$h(v)$ dokonce odpovídá délce nìjaké cesty -- staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus.
-\:Algoritmus se v¾dy zastaví -- cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro
- ka¾dý~$v$, je koneènì mnoho.
-\:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$ --
- implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol,
- který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran.
+\:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu.
+\:$h(v)$ dokonce odpovídá délce nìjaké cesty.
+\:Algoritmus se v¾dy zastaví.
+\:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$.
\:Po zastavení mají koneèné~$h(v)$ právì v¹echny uzavøené vrcholy.
-\:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$ -- kdyby to nebyla pravda,
+\:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$.
+\endlist
+
+\proof
+
+\numlist\nparen
+\:Doká¾eme indukcí podle poètu krokù algoritmu.
+\:Staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus.
+\:Cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro ka¾dý~$v$, je koneènì mnoho.
+\:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol,
+ který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran.
+\:$h(v)$ nastavujeme na~koneènou hodnotu právì v~okam¾icích, kdy se vrchol stává otevøeným.
+ Ka¾dý otevøený vrchol je èasem uzavøen.
+\:Kdyby tomu tak nebylo,
vyberme si ze~\uv{¹patných} vrcholù~$v$ takový, pro nìj¾ obsahuje nejkrat¹í cesta z~$u$ do~$v$
nejmen¹í mo¾ný poèet hran. Vrchol~$v$ je zajisté rùzný od~$u$, tak¾e má na~této cestì nìjakého
pøedchùdce~$w$. Pøitom~$w$ u¾ musí být ohodnocen správnì a relaxace, která mu toto ohodnocení
nastavila, ho musela prohlásit za~otevøený. Jen¾e ka¾dý otevøený vrchol je pozdìji uzavøen,
tak¾e~$w$ poté musel být je¹tì alespoò jednou relaxován, co¾ muselo sní¾it~$h(v)$ na správnou
vzdálenost.
+\qeditem
\endlist
-\>Meta-algoritmus tedy pro libovolnou implementaci kroku~4 spoèítá správné vzdálenosti.
-\qed
+\>Dokázali jsme tedy, ¾e meta-algoritmus pro libovolnou implementaci kroku~4
+spoèítá správné vzdálenosti.
+
+\medskip
\s{Cvièení:}
\itemize\ibull
\:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9
- pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$u$. Doka¾te, ¾e pøedchùdci
+ pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$v$. Doka¾te, ¾e pøedchùdci
dosa¾itelných vrcholù budou tvoøit strom a ¾e tento strom bude stromem
nejkrat¹ích cest z~vrcholu~$u$.
\:Doka¾te, ¾e pro graf, v~nìm¾ je alespoò jeden záporný cyklus dosa¾itelný
\h{Bellmanùv-Fordùv-Mooreùv algoritmus}
-Bellman, Ford a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM),
+Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM),
který lze v~øeèi na¹eho meta-algoritmu formulovat takto: Otevøené vrcholy
udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané
-zaøazujeme na~konec. Co toto pravidlo zpùsobí?
+zaøazujeme na~konec). Co toto pravidlo zpùsobí?
\s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$.
tedy nejvý¹e~$n$.
Relaxace ka¾dého vrcholu pøitom trvá lineárnì se stupnìm vrcholu, tak¾e celá
-fáze probìhne v~èase $\O(m)$.
+fáze probìhne v~èase $\O(m)$. V¹echny fáze pak v~$\O(nm)$.
\qed
\s{Cvièení:}
\h{Dijkstrùv algoritmus}
Pokud jsou v¹echny délky hran nezáporné, mù¾eme pou¾ít efektivnìj¹í pravidlo
-pro výbìr vrcholu navr¾ené Dijkstrou. To øíká, ¾e v¾dy relaxujeme ten z~otevøených
+pro výbìr vrcholu navr¾ené Dijkstrou \cite{dijkstra:mstandpath}. To øíká, ¾e v¾dy relaxujeme ten z~otevøených
vrcholù, jeho¾ ohodnocení je nejmen¹í.
\s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající
\h{Algoritmy pro problém typu \ppsp}
Zamìøme se nyní na~pøípad, kdy chceme hledat nejkrat¹í cesty mezi zadanou dvojicí
-vrcholù $u$,~$v$. Obvykle se to øe¹í pomocí algoritmu typu \sssp{} (SSSP) a v~obecném
+vrcholù $s$,~$t$. Obvykle se to øe¹í pomocí algoritmu typu \sssp{} (SSSP) a v~obecném
pøípadì ani není lep¹í øe¹ení známo. Existuje ov¹em velké mno¾ství heuristik, kterými
-lze ve~vìt¹inì aplikací hledání cest zrychlit. Nìkteré z~nich si pøedvedeme a omezíme
-se pøitom na pøípady s~nezápornými délkami.
+lze ve~vìt¹inì aplikací hledání cest zrychlit. Nìkteré z~nich si pøedvedeme na
+pøíkladu Dijkstrova algoritmu.
+
+Dijkstrùv algoritmus ve~své klasické podobì vùbec nic neví o~cílovém vrcholu
+a prohledá celý graf. První úprava, která se nabízí, je vyu¾ít toho, ¾e
+od~okam¾iku uzavøení kteréhokoliv vrcholu se ji¾ jeho ohodnocení nezmìní.
+Pokud tedy uzavøeme cílový vrchol, mù¾eme se zastavit.
+
+Jakou èást grafu prohledáváme teï? V~metrice dané vzdálenostmi v~grafu je to nejmen¹í
+koule se støedem ve~vrcholu~$u$, která obsahuje nejkrat¹í cestu (dobøe se to
+pøedstavuje na~hledání v~silnièní síti na~rovinné mapì).
+
+Také mù¾eme spustit prohledávání z~obou koncù zároveò, tedy zkombinovat hledání
+od~$s$ v~pùvodním grafu s~hledáním od~$t$ v~grafu s~obrácenou orientací hran.
+Oba postupy mù¾eme libovolnì støídat, zastavíme se v~okam¾iku, kdy jsme jeden
+vrchol uzavøeli v~obou smìrech. Pozor ov¹em na to, ¾e souèet obou ohodnocení
+tohoto vrcholu nemusí být roven vzdálenosti $v$ od~$u$ (zkuste vymyslet protipøíklad).
+Nejkrat¹í cesta je¹tì mù¾e vypadat tak, ¾e pøechází po nìjaké hranì mezi vrcholem
+uzavøeným v~jednom smìru a vrcholem uzavøeným ve~smìru druhém (ponechme bez dùkazu).
+Staèí tedy bìhem procházení hran otestovat, zda je koncový vrchol uzavøený v~opaèném
+smìru prohledávání, a~pokud ano, zapoèítat cestu do~prùbì¾ného minima.
+
+Obousmìrný Dijkstrùv algoritmus projde sjednocení nìjaké koule okolo~$s$ s~nìjakou
+koulí okolo~$t$, které obsahuje nejkrat¹í cestu. Prùmìry koulí pøitom závisí na tom,
+jak budeme bìhem výpoètu støídat oba smìry prohledávání. V~nejhor¹ím pøípadì samozøejmì
+mù¾eme prohledat a¾ celý graf.
+
+\h{Algoritmus \astar}
+
+V~umìlé inteligenci se èasto pro hledání nejkrat¹í cesty v~rozsáhlých grafech
+(obvykle stavových prostorech nìjaké úlohy) pou¾ívá algoritmus nazývaný~\astar.
+Jedná se o~modifikaci Dijkstrova algoritmu, která vyu¾ívá heuristickou funkci
+pro dolní odhad vzdálenosti do~cíle; oznaème si ji $\psi(v)$. V~ka¾dém kroku pak uzavíra
+vrchol~$v$ s~nejmen¹ím mo¾ným souètem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.
+
+Intuice za tímto algoritmem je jasná: pokud víme, ¾e nìjaký vrchol je blízko
+od~poèátaèního vrcholu~$s$, ale bude z~nìj urèitì daleko do cíle~$t$, zatím ho
+odlo¾íme a budeme zkoumat nadìjnìj¹í varianty.
+
+Heuristika se pøitom volí podle konkrétního problému -- napø. hledáme-li cestu
+v~mapì, mù¾eme pou¾ít vzdálenost do~cíle vzdu¹nou èarou.
+
+Je u~tohoto algoritmu zaruèeno, ¾e v¾dy najde nejkrat¹í cestu? Na to nám dá odpovìï
+teorie potenciálù.
+
+\s{Vìta:} Bìh algoritmu \astar{} odpovídá prùbìhu Dijkstrova algoritmu
+na~grafu redukovaném potenciálem daným heuristickou funkcí~$-\psi$. Pøesnìji,
+pokud oznaèíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
+v~synchronnì bì¾ícím Dijkstrovi, bude v¾dy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
+
+\proof
+Indukcí podle doby bìhu obou algoritmù. Na poèátku je $h^*(s)$ i $h(s)$ nulové
+a v¹echna ostatní $h^*$ a~$h$ jsou nekoneèná, tak¾e tvrzení platí. V~ka¾dém dal¹ím
+kroku \astar{} vybere vrchol~$v$ s~nejmen¹ím $h^*(v) + \psi(v)$, co¾ je tentý¾ vrchol,
+který vybere Dijkstra ($\psi(s)$ je stále stejné).
+
+Uva¾ujme, co se stane bìhem relaxace hrany $vw$: Dijkstra se pokusí sní¾it ohodnocení $h(w)$
+o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. Uká¾eme,
+¾e \astar{} udìlá toté¾:
+$$\eqalign{
+\delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
+&= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
+&= h^*(w) - h^*(v) - \ell(v,w).
+}$$
+Oba algoritmy tedy a¾ na~posunutí dané potenciálem poèítají toté¾.
+\qed
+
+\s{Dùsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ pøípustný.
+
+Napøíklad pro rovinnou mapu to heuristika daná euklidovskou vzdáleností, tedy $\psi(v) := \varrho(v,t)$, splòuje:
+Pøípustnost po¾aduje pro ka¾dou hranu $uv$ nerovnost
+$\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
+tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
+Jeliko¾ $\ell(u,v) \ge \varrho(u,v)$,
+staèí dokázat, ¾e $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
+co¾ je ov¹em trojúhelníková nerovnost pro metriku~$\varrho$.
\references
\bye
projects / ga.git / blobdiff