From f179dc323f105d194bb820c22a544c857f11009d Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 17 Oct 2010 13:31:46 +0200
Subject: [PATCH] Cesty: Algoritmy pro PPSP (obousmerny Dijkstra, A*)

---
 13-dijkstra/13-dijkstra.tex | 81 +++++++++++++++++++++++++++++++++++--
 1 file changed, 78 insertions(+), 3 deletions(-)

diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex
index 3c1dfb8..9fc3dd4 100644
--- a/13-dijkstra/13-dijkstra.tex
+++ b/13-dijkstra/13-dijkstra.tex
@@ -5,6 +5,7 @@
 \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
@@ -579,10 +580,84 @@ Jednotliv
 \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
-- 
2.39.5