3 \prednaska{13}{Nejkratší cesty}{}
8 \def\astar{A\kern-0.15em *}
10 Problém hledání nejkratší cesty v~(obvykle ohodnoceném orientovaném) grafu
11 provází teorii grafových algoritmů od~samých počátků. Základní algoritmy
12 pro hledání cest jsou nedílnou součástí základních kursů programování
13 a algoritmů, my se budeme věnovat zejména různým jejich vylepšením.
15 Uvažujme tedy nějaký orientovaný graf, jehož každá hrana~$e$ je opatřena
16 {\I délkou} $\ell(e)\in{\bb R}$. Množině hran (třeba sledu nebo cestě)
17 pak přiřadíme délku rovnou součtu délek jednotlivých hran.
19 Pro vrcholy $u,v$ definujeme jejich {\I vzdálenost} $d(u,v)$ jako nejmenší
20 možnou délku cesty z~$u$ do~$v$ (jelikož cest je v~grafu konečně mnoho,
21 minimum vždy existuje). Pokud z~$u$ do~$v$ žádná cesta nevede, položíme
24 Obvykle se studují následující tři problémy:
27 \:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkratší
28 cestu z~daného vrcholu~$u$ do~daného vrcholu~$v$. (Pokud je nejkratších cest
29 více, tak libovolnou z~nich.)
30 \:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
31 nalézt nejkratší cesty do~všech ostatních vrcholů.
32 \:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkratší cesty
33 mezi všemi dvojicemi vrcholů.
36 Překvapivě, tak obecně, jak jsme si uvedené problémy definovali, je neumíme
37 řešit v~polynomiálním čase: pro grafy, které mohou obsahovat hrany záporných
38 délek bez jakýchkoliv omezení, je totiž hledání nejkratší cesty NP-těžké
39 (lze na~něj snadno převést existenci hamiltonovské cesty). Všechny známé
40 polynomiální algoritmy totiž místo nejkratší cesty hledají nejkratší sled
41 -- nijak nekontrolují, zda cesta neprojde jedním vrcholem vícekrát.
43 Naštěstí pro nás je to v~grafech bez cyklů záporné délky totéž: pokud se
44 v~nalezeném sledu vyskytne cyklus, můžeme jej \uv{vystřihnout} a tím získat
45 sled, který není delší a~který má méně hran. Každý nejkratší sled tak
46 můžeme upravit na~stejně dlouhou cestu.
47 V~grafech bez záporných cyklů je tedy jedno, zda hledáme sled nebo cestu;
48 naopak vyskytne-li se záporný cyklus dosažitelný z~počátečního vrcholu,
49 nejkratší sled ani neexistuje.
51 Navíc se nám bude hodit, že každý prefix nejkratší cesty je opět nejkratší
52 cesta. Jinými slovy pokud některá z~nejkratších cest z~$u$ do~$v$ vede
53 přes nějaký vrchol~$w$, pak její část z~$u$ do~$w$ je jednou z~nejkratších
54 cest z~$u$ do~$w$. (V~opačném případě bychom mohli úsek $u\ldots w$ vyměnit za~kratší.)
56 Díky této {\I prefixové vlastnosti} můžeme pro každý vrchol~$u$ sestrojit jeho {\I strom
57 nejkratších cest}~${\cal T}(u)$. To je nějaký podgraf grafu~$G$, který má tvar
58 stromu zakořeněného v~$u$ a orientovaného směrem od~kořene, a~platí pro něj, že
59 pro každý vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou
60 z~nejkratších cest z~$u$ do~$v$ v~původním grafu.
62 \s{Pozorování:} Strom nejkratších cest vždy existuje.
65 Nechť $u=v_1,\ldots,v_n$ jsou všechny vrcholy grafu~$G$. Indukcí budeme
66 dokazovat, že pro každé~$i$ existuje strom~${\cal T}_i$, v~němž se nacházejí nejkratší
67 cesty z~vrcholu~$u$ do vrcholů $v_1,\ldots,v_i$. Pro $i=1$ stačí uvážit
68 strom obsahující jediný vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
69 strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkratší cestu z~$u$ do~$v_i$
70 a označíme~$z$ poslední vrchol na~této cestě, který se ještě vyskytuje v~${\cal T}_{i-1}$.
71 Úsek nejkratší cesty od~$z$ do~$v_i$ pak přidáme do~${\cal T}_{i-1}$
72 a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
76 Zbývá se dohodnout, v~jakém tvaru mají naše algoritmy vydávat výsledek.
77 U~problémů typu \ppsp{} je nejjednodušší vypsat celou cestu, u~\sssp{} můžeme jako výstup
78 vydat strom nejkratších cest z~daného počátku (všimněte si, že stačí
79 uvést předchůdce každého vrcholu), u~\apsp{} vydáme strom nejkratších cest
80 pro každý ze~zdrojových vrcholů.
82 Často se ovšem ukáže, že podstatná část problému se skrývá v~samotném
83 výpočtu vzdáleností a sestrojení předchůdců je triviálním rozšířením algoritmu.
84 Budeme tedy obvykle jen počítat vzdálenosti a samotnou rekonstrukci cest
85 ponecháme čtenáři jako snadné cvičení.
87 \h{Relaxační algoritmus}
89 Začněme problémem \sssp{} a označme~$u$ výchozí vrchol. Většina známých
90 algoritmů funguje tak, že pro každý vrchol~$v$ udržují ohodnocení $h(v)$,
91 které v~každém okamžiku odpovídá délce nějakého sledu z~$u$ do~$v$. Postupně
92 toto ohodnocení upravují, až se z~něj stane vzdálenost $d(u,v)$ a algoritmus
95 Vhodnou operací pro vylepšování ohodnocení je takzvaná {\I relaxace.}
96 Vybereme si nějaký vrchol~$v$ a pro všechny jeho sousedy~$w$ spočítáme
97 $h(v) + \ell(v,w)$, tedy délku sledu, který vznikne rozšířením aktuálního
98 sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota menší než~$h(w)$,
99 tak jí $h(w)$ přepíšeme.
101 Abychom zabránili opakovaným relaxacím téhož vrcholu, které nic nezmění,
102 budeme rozlišovat tři stavy vrcholů: {\I neviděn} (ještě jsme ho nenavštívili),
103 {\I otevřen} (změnilo se ohodnocení, časem chceme relaxovat) a {\I uzavřen}
104 (už jsme relaxovali a není potřeba znovu).
106 Náš algoritmus bude fungovat následovně:
109 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
110 \:$\<stav>(*)\leftarrow\<neviděn>$, $\<stav>(u)\leftarrow\<otevřen>$.
111 \:Dokud existují otevřené vrcholy, opakujeme:
112 \::$v\leftarrow\hbox{libovolný otevřený vrchol}$.
113 \::$\<stav>(v)\leftarrow\<uzavřen>$.
115 \:::Pro všechny hrany $vw$ opakujeme:
116 \::::Je-li $h(w) > h(v) + \ell(v,w)$:
117 \:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
118 \:::::$\<stav>(w)\leftarrow\<otevřen>$.
119 \:Vrátíme výsledek $d(u,v)=h(v)$ pro všechna~$v$.
122 Podobně jako u~minimálních koster, i zde se jedná o~meta-algoritmus, protože
123 v~kroku~4 nespecifikuje, který z~otevřených vrcholů vybírá. Přesto
124 ale můžeme dokázat několik zajímavých tvrzení, která na~konkrétním způsobu
127 \s{Věta:} Spustíme-li meta-algoritmus na graf bez záporných cyklů, pak:
130 \:Ohodnocení $h(v)$ vždy odpovídá délce nějakého sledu z~$u$ do~$v$.
131 \:$h(v)$ dokonce odpovídá délce nějaké cesty z~$u$ do~$v$.
132 \:Algoritmus se vždy zastaví.
133 \:Po zastavení jsou označeny jako uzavřené právě ty vrcholy, které jsou dosažitelné z~$u$.
134 \:Po zastavení mají konečné~$h(v)$ právě všechny uzavřené vrcholy.
135 \:Pro každý dosažitelný vrchol je na~konci $h(v)$ rovno $d(u,v)$.
141 \:Dokážeme indukcí podle počtu kroků algoritmu.
142 \:Stačí rozmyslet, v~jaké situaci by vytvořený sled mohl obsahovat cyklus.
143 \:Cest, a~tím pádem i možných hodnot~$h(v)$ pro každý~$v$, je konečně mnoho.
144 \:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ stačí uvážit neuzavřený vrchol,
145 který je dosažitelný z~$u$ cestou o~co nejmenším počtu hran.
146 \:$h(v)$ nastavujeme na~konečnou hodnotu právě v~okamžicích, kdy se vrchol stává otevřeným.
147 Každý otevřený vrchol je časem uzavřen.
148 \:Kdyby tomu tak nebylo,
149 vyberme si ze~\uv{špatných} vrcholů~$v$ takový, pro nějž obsahuje nejkratší cesta z~$u$ do~$v$
150 nejmenší možný počet hran. Vrchol~$v$ je zajisté různý od~$u$, takže má na~této cestě nějakého
151 předchůdce~$w$. Přitom~$w$ už musí být ohodnocen správně a relaxace, která mu toto ohodnocení
152 nastavila, ho musela prohlásit za~otevřený. Jenže každý otevřený vrchol je později uzavřen,
153 takže~$w$ poté musel být ještě alespoň jednou relaxován, což muselo snížit~$h(v)$ na správnou
158 \>Dokázali jsme tedy, že meta-algoritmus pro libovolnou implementaci kroku~4
159 spočítá správné vzdálenosti.
165 \:Nechť do algoritmu doplníme udržování předchůdců tak, že v~kroku~9
166 přenastavíme předchůdce vrcholu~$w$ na vrchol~$v$. Dokažte, že předchůdci
167 dosažitelných vrcholů budou tvořit strom a že tento strom bude stromem
168 nejkratších cest z~vrcholu~$u$.
169 \:Dokažte, že pro graf, v~němž je alespoň jeden záporný cyklus dosažitelný
170 z~počátečního vrcholu, se algoritmus nezastaví a ohodnocení všech vrcholů
171 na cyklu postupně klesnou libovolně hluboko. Nedosažitelné záporné cykly
172 chod algoritmu samozřejmě nijak neovlivní.
175 \h{Bellmanův-Fordův-Mooreův algoritmus}
177 Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobě algoritmus (říkejme mu BFM),
178 který lze v~řeči našeho meta-algoritmu formulovat takto: Otevřené vrcholy
179 udržujeme ve~frontě (vždy relaxujeme vrchol na počátku fronty, nově otevírané
180 zařazujeme na~konec). Co toto pravidlo způsobí?
182 \s{Věta:} Časová složitost algoritmu~BFM činí $\O(nm)$.
185 Běh algoritmu rozdělíme na~fáze. Nultá fáze sestává z~vložení vrcholu~$u$
186 do~fronty. V~$(i+1)$-ní fázi relaxujeme ty vrcholy, které byly do~fronty
187 uloženy během $i$-té fáze.
189 Jelikož relaxace vrcholu trvá lineárně se stupněm vrcholu a každý vrchol
190 se dané fáze účastní nejvýše jednou, trvá jedna fáze $\O(m)$. Zbývá ukázat,
191 že fází provedeme nejvýše~$n$.
193 Indukcí dokážeme, že na konci $i$-té fáze je každé ohodnocení $h(v)$ shora omezeno
194 délkou nejkratšího z~$uv$-sledů o~nejvýše~$i$ hranách. Pro $i=0$ to triviálně
195 platí. Uvažujme nyní vrchol~$v$ na konci $(i+1)$-ní fáze a nějaký nejkratší $uv$-sled~$P$
196 o~$i+1$ hranách. Označme $wv$ poslední hranu tohoto sledu a $P'$ sled bez této hrany,
197 který tedy má délku~$i$. Podle indukčního předpokladu je na konci $i$-té fáze
198 $h(w)\le \ell(P')$. Tuto hodnotu získalo $h(w)$ nejpozději v~$i$-té fázi, při tom jsme
199 vrchol~$w$ otevřeli, takže jsme ho nejpozději v~$(i+1)$-ní fázi zavřeli a relaxovali.
200 Po této relaxaci je ovšem $h(v)\le h(w)+\ell(w,v)\le \ell(P') + \ell(w,v) = \ell(P)$.
205 \:Ukažte, že asymptoticky stejné časové složitosti by dosáhl algoritmus,
206 který by vrcholy očísloval $v_1,\ldots,v_n$ a opakovaně by je v~tomto
207 pořadí relaxoval tak dlouho, dokud by se ohodnocení měnila.
208 \:Jak algoritmus upravit, aby v~$i$-té fázi spočítal minimální délky sledů
210 \:Jak lze algoritmus BFM využít k~nalezení záporného cyklu?
213 \h{Dijkstrův algoritmus}
215 Pokud jsou všechny délky hran nezáporné, můžeme použít efektivnější pravidlo
216 pro výběr vrcholu navržené Dijkstrou \cite{dijkstra:mstandpath}. To říká, že vždy relaxujeme ten z~otevřených
217 vrcholů, jehož ohodnocení je nejmenší.
219 \s{Věta:} Dijkstrův algoritmus uzavírá vrcholy v~pořadí podle neklesající
220 vzdálenosti od~$u$ a každý dosažitelný vrchol uzavře právě jednou.
223 Indukcí dokážeme, že v~každém okamžiku mají všechny uzavřené vrcholy ohodnocení
224 menší nebo rovné ohodnocením všech otevřených vrcholů. Na~počátku to jistě platí.
225 Nechť nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevřenými. Během jeho
226 relaxace nemůžeme žádnou hodnotu snížit pod~$h(v)$, jelikož v~grafu s~nezápornými
227 hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevřených vrcholů
228 tedy neklesne pod hodnotu tohoto nově uzavřeného. Hodnoty dříve uzavřených vrcholů
229 se nemohou nijak změnit.
232 Přímočará implementace Dijkstrova algoritmu by tedy pokaždé v~čase $\O(n)$
233 vybrala otevřený vrchol s~nejmenším ohodnocením, v~čase $\O(n)$ ho relaxovala
234 a toto by se opakovalo nejvýše $n$-krát. Algoritmus by tudíž doběhl v~čase $\O(n^2)$,
235 což je pro husté grafy zajisté optimální. Zkusíme nyní zrychlit výpočet
238 Všechny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, takže úzkým hrdlem je
239 vybírání minima. Použijeme pro něj vhodnou datovou strukturu, v~níž budeme udržovat
240 množinu všech otevřených vrcholů spolu s~jejich ohodnoceními. Od~datové struktury
241 potřebujeme, aby uměla operace \<Insert> (vložení vrcholu), \<ExtractMin> (nalezení
242 a smazání minima) a \<Decrease> (snížení hodnoty vrcholu). První dvě operace přitom
243 voláme nejvýše $n$-krát a operaci \<Decrease> nejvýše $m$-krát. Celý algoritmus
245 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
246 kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou časové složitosti jednotlivých operací
247 na~struktuře o~nejvýše~$n$ prvcích (stačí amortizovaně).
249 \>Jaké možnosti máme pro volbu struktury?
252 \:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
253 celkem tedy $\O(n^2)$.
254 \:{\I (binární) halda} -- všechny tři operace umíme provést v~čase $\O(\log n)$, takže celkem
255 $\O(m\log n)$. To je pro husté grafy horší, pro řídké lepší.
256 \:{\I $k$-regulární halda} -- pokud haldu upravíme tak, že každý prvek bude mít až $k$ synů,
257 hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky směrem nahoru,
258 což je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ovšem \<ExtractMin> potřebuje
259 zkoumat všechny syny každého navštíveného prvku, takže se zpomalí na $\O(k\log_k n)$.
261 Celková složitost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba členy se vyrovnají
262 pro $k=m/n$, čímž získáme $\O(m\log_{m/n} n)$. Člen $\log_{m/n} n$ je přitom $\O(1)$,
263 kdykoliv je $m\ge n^{1+\varepsilon}$ pro nějaké~$\varepsilon>0$, takže pro dostatečně
264 husté grafy jsme získali lineární algoritmus.
266 (Všimněte si, že pro $m\approx n^2$ algoritmus zvolí $k\approx n$, takže halda degeneruje
267 na jediné patro, tedy na pole, které se opravdu ukázalo být optimální volbou pro husté grafy.)
268 \:{\I Fibonacciho halda} \cite{ft:fibonacci} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má složitost
269 $\O(\log n)$ [vše amortizovaně]. Dijkstrův algoritmus proto doběhne v~čase $\O(m + n\log n)$.
270 To je lineární pro grafy s~hustotou $\Omega(\log n)$. Téže složitosti operací dosahují
271 i jiné, méně známé haldy \cite{haeupler:rankph,elmasry:violheap}, které mohou být v~praxi
273 \:{\I Monotónní haldy} -- můžeme použít nějakou jinou haldu, která využívá toho,
274 že posloupnost odebíraných prvků je neklesající. Pro celá čísla na~\hbox{RAMu} to může
275 být například Thorupova halda \cite{thorup:queue} se složitostí $\O(\log\log n)$ u~operace \<ExtractMin>
276 a $\O(1)$ u~ostatních operací. Dijkstra tedy běží v~$\O(m + n\log\log n)$.
277 \:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápětí.
283 \:Najděte příklad grafu se zápornými hranami (ale bez záporných cyklů),
284 na~kterém Dijkstrův algoritmus selže.
285 \:Rozmyslete si, že pokud nevyužijeme nějaké speciální vlastnosti čísel (celočíselnost,
286 omezený rozsah), je mez $\O(m+n\log n)$ nejlepší možná, protože Dijkstrovým algoritmem
287 můžeme třídit $n$-tici čísel. Thorup dokonce dokázal \cite{thorup:equiv}, že z~každého třídícího algoritmu
288 se složitostí $\O(nT(n))$ můžeme odvodit haldu se složitostí mazání $\O(T(n))$.
289 \:Jsou-li délky hran celočíselné, můžeme se na Dijkstrův algoritmus dívat i takto:
290 Představme si, že každou hranu nahradíme cestou tvořenou příslušným počtem hran jednotkové délky
291 a na vzniklý neohodnocený graf spustíme prohledávání do~šířky. To samozřejmě vydá
292 správný výsledek, ale poměrně pomalu, protože bude většinu času trávit posouváním
293 vlny \uv{uvnitř} původních hran. Můžeme si tedy pro každou původní hranu nařídit
294 \uv{budík}, který nám řekne, za~kolik posunutí vlny dospějeme na~její konec.
295 Dokažte, že tento algoritmus je ekvivalentní s~Dijkstrovým.
298 \h{Celočíselné délky}
300 Uvažujme nyní grafy, v~nichž jsou všechny délky hran nezáporná celá čísla omezená
301 nějakou konstantou~$L$. Všechny vzdálenosti jsou tedy omezeny číslem~$nL$, takže
302 nám stačí datová struktura schopná uchovávat takto omezená celá čísla.
304 Použijeme jednoduchou přihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
305 jeho $i$-tý prvek bude obsahovat seznam vrcholů, jejichž ohodnocení je rovno~$i$.
306 Operace \<Insert> a \<Decrease> zvládneme v~konstantním čase, budeme-li si u~každého
307 prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potřebuje najít první
308 neprázdnou přihrádku, ale jelikož víme, že posloupnost odebíraných minim je monotónní,
309 stačí hledat od místa, kde se hledání zastavilo minule. Všechna hledání přihrádek
310 tedy zaberou dohromady $\O(nL)$ a celý Dijkstrův algoritmus bude trvat $\O(nL + m)$.
312 Prostorová složitost $\O(nL+m)$ je nevalná, ale můžeme ji jednoduchým trikem
313 snížit: Všimneme si, že všechna konečná ohodnocení vrcholů nemohou být větší
314 než aktuální minimum zvětšené o~$L$. Jinými slovy všechny neprázdné přihrádky
315 se nacházejí v~úseku pole dlouhém~$L+1$, takže stačí indexovat modulo~$L+1$.
316 Pouze si musíme dávat pozor, abychom správně poznali, kdy se struktura
317 vyprázdnila, což zjistíme například pomocí počítadla otevřených vrcholů. Čas si
318 asymptoticky nezhoršíme, prostor klesne na~$\O(L+m)$.
320 Podobný trik můžeme použít i pro libovolnou jinou datovou strukturu: rozsah čísel
321 rozdělíme na~\uv{okna} velikosti~$L$ (v~$i$-tém okně jsou čísla $iL,iL+1,\ldots,(i+1)L-1$).
322 V~libovolné chvíli mohou tedy být neprázdná nejvýše dvě okna. Stačí nám proto
323 pořídit si dvě struktury pro ukládání čísel v~rozsahu $0,\ldots,L-1$ -- jedna
324 z~nich bude reprezentovat aktuální okno (to, v~němž leželo minulé minimum),
325 druhá okno bezprostředně následující. Minimum mažeme z~první struktury; pokud
326 už je prázdná, obě struktury prohodíme. Operace \<Insert> podle hodnoty určí,
327 do~které struktury se má vkládat. S~operací \<Decrease> je to složitější --
328 hodnota z~vyšší struktury může přeskočit do té nižší, ale v~takovém případě
329 ji ve~vyšší struktuře vymažeme (to je \<Decrease> na $-\infty$ následovaný
330 \<ExtractMin>em) a do~té nižší vložíme. To se každému prvku může přihodit nejvýše
331 jednou, takže stále platí, že se každý prvek účastní $\O(1)$ vložení a $\O(1)$
334 Ukázali jsme tedy, že pro naše potřeby postačuje struktura schopná uchovávání
335 čísel menších nebo rovných~$L$.
337 Nabízí se použít van Emde-Boasův strom z~kapitoly o~výpočetních modelech.
338 Ten dosahuje složitosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
339 operaci \<Decrease> musíme překládat na \<Delete> a \<Insert>. Celková
340 složitost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, přičemž čas~$L$
341 spotřebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
342 viz zmíněná kapitola).
344 Vraťme se ale ještě k~využití přihrádek\dots
346 \h{Víceúrovňové přihrádky}
348 Podobně jako u~třídění čísel, i~zde se vyplácí stavět přihrádkové struktury
349 víceúrovňově (původně popsáno Goldbergem a Silversteinem \cite{goldberg:mlb}).
350 Jednotlivé hodnoty budeme zapisovat v~soustavě o~základu~$B$,
351 který zvolíme jako nějakou mocninu dvojky, abychom mohli s~číslicemi tohoto
352 zápisu snadno zacházet pomocí bitových operací. Každé číslo tedy zabere nejvýše
353 $d=1+\lfloor\log_B L\rfloor$ číslic; pokud bude kratší, doplníme ho zleva nulami.
355 Nejvyšší patro struktury bude tvořeno polem $B$~přihrádek, v~$i$-té z~nich
356 budou uložena ta čísla, jejichž číslice nejvyššího řádu je rovna~$i$. Za~{\I aktivní}
357 prohlásíme tu přihrádku, která obsahuje aktuální minimum. Přihrádky s~menšími
358 indexy jsou prázdné a zůstanou takové až do~konce výpočtu, protože halda
359 je monotónní. Pokud v~přihrádce obsahující minimum bude více prvků, budeme
360 ji rozkládat podle druhého nejvyššího řádu na dalších~$B$ přihrádek atd.
361 Celkem tak vznikne až~$d$ úrovní.
363 \>Struktura bude obsahovat následující data:
366 \:Parametry $L$, $B$ a~$d$.
367 \:Pole úrovní (nejvyšší má číslo~$d-1$, nejnižší~0), každá úroveň je buďto prázdná
368 (a pak jsou prázdné i~všechny nižší), nebo obsahuje pole~$U_i$ o~$B$ přihrádkách
369 a v~každé z~nich seznam prvků. Pole úrovní používáme jako zásobník, udržujeme
370 si číslo nejnižší neprázdné úrovně.
371 \:Hodnotu~$\mu$ předchozího odebraného minima.
374 Operace \<Insert> vloží hodnotu do~nejhlubší možné přihrádky. Podívá se tedy
375 na~nejvyšší úroveň: pokud hodnota patří do přihrádky, která není aktivní, vloží
376 ji přímo. Jinak přejde o~úroveň níže a zopakuje stejný postup. To vše lze provést
377 v~konstantním čase: stačí se podívat, jaký je nejvyšší jedničkový bit ve~{\sc xor}u
378 nové hodnoty s~číslem~$\mu$ (opět viz kapitola o~výpočetních modelech), a tím zjistit
379 číslo úrovně, kam hodnota patří.
381 Pokud chceme provést \<Decrease>, odstraníme hodnotu z~přihrádky, ve~které se
382 právě nachází (polohu si můžeme u~každé hodnoty pamatovat zvlášť), a znovu ji
385 Většinu práce samozřejmě přenecháme funkci \<ExtractMin>. Ta začne prohledávat
386 nejnižší obsazenou úroveň od~aktivní přihrádky dál (to, která přihrádka je na
387 které úrovni aktivní, poznáme z~číslic hodnoty~$\mu$). Pokud přihrádky na~této
388 úrovni dojdou, prázdnou úroveň zrušíme a pokračujeme o~patro výše.
390 Jakmile najdeme neprázdnou přihrádku, nalezneme v~ní minimum a to se stane novým~$\mu$.
391 Pokud v~přihrádce nebyly žádné další prvky, skončíme. V~opačném případě zbývající
392 prvky rozprostřeme do~přihrádek na~bezprostředně nižší úrovni, kterou tím založíme.
394 Čas strávený hledáním minima můžeme rozdělit na~několik částí:
397 \:$\O(B)$ na inicializaci nové úrovně -- to naúčtujeme prvku, který jsme
399 \:hledání neprázdných přihrádek -- prozkoumání každé prázdné přihrádky
400 naúčtujeme jejímu vytvoření, což se rozpustí v~$\O(B)$ na inicializaci
402 \:zrušení úrovně -- opět naúčtujeme jejímu vzniku;
403 \:rozhazování prvků do přihrádek -- jelikož prvky v~hierarchii přihrádek
404 putují během operací pouze doleva a dolů (jejich hodnoty se nikdy nezvětšují),
405 klesne každý prvek nejvýše~$d$-krát, takže stačí, když na všechna rozhazování
406 přispěje časem $\O(d)$;
407 \:hledání minima -- minimum naúčtujeme smazanému prvku, ostatní prvky,
408 které jsme museli projít, naúčtujeme jejich rozhazování.
411 \>Stačí tedy, aby každý prvek při \<Insert>u zaplatil čas $\O(B+d)$ a jak \<Decrease>,
412 tak \<ExtractMin> budou mít konstantní amortizovanou složitost. Dijkstrův
413 algoritmus pak poběží v~$\O(m + n(B+d))$.
415 Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
416 Vhodná volba je $B=\log L/\log\log L$. Při ní platí
418 {\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
419 = {\log L\over \log\log L - \log\log\log L} = \Theta(B).
421 Tehdy Dijkstra vydá výsledek v~čase $\O(m + n\cdot{\log L\over\log\log L})$.
423 \h{HOT Queue -- kombinace přihrádek s~haldou}
425 Cherkassky, Goldberg a Silverstein \cite{cherkassky:hotq} si všimli, že ve~víceúrovňových přihrádkových strukturách
426 platíme příliš mnoho za~úrovně, ve~kterých se za~dobu jejich existence objeví jen malé
427 množství prvků. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~společné haldy.
428 Výsledné struktuře se říká HOT (Heap-on-Top) Queue. My si předvedeme její upravenou
429 variantu (v~té původní se skrývá několik chyb).
431 Pořídíme si haldu, řekněme Fibonacciho, a~navíc ke~každé úrovni počítadlo udávající,
432 kolik prvků z~této úrovně jsme uložili do~haldy. Dokud toto počítadlo nepřeroste nějaký
433 parametr~$H$, přihrádky nebudeme zakládat a prvky poputují do~haldy. Čas $\O(B)$ na
434 založení úrovně a její procházení proto můžeme rozpočítat mezi~$H$ prvků, které se musely
435 na~dané úrovni objevit, než byla rozpřihrádkována. (Povšimněte si, že počítadlo nikdy
436 nesnižujeme, pouze ho vynulujeme, když je úroveň zrušena. Proto vůbec nemusí odpovídat
437 skutečnému počtu prvků z~příslušné úrovně, které jsou právě uloženy v~haldě. To ovšem
438 vůbec nevadí -- počítadlo pouze hlídá, aby se úroveň nevytvořila příliš brzy, tedy abychom
439 měli dost prvků k~rozúčtování času.)
441 Proměnnou~$\mu$ necháme ukazovat na~místo, kde jsme se při hledání minima v~přihrádkách
442 zastavili. Současné globální minimum struktury může být nižší, nachází-li se minimum
443 zrovna v~haldě. Stále je však zaručeno, že před~$\mu$ se nenachází žádná
446 Operace budou fungovat takto:
450 \:Spočítáme, do~které úrovně~$i$ má prvek padnout (bitovými operacemi).
451 \:Pokud je počítadlo této úrovně menší než~$H$, zvýšíme ho, vložíme prvek do~haldy a skočíme.
452 \:Nebyly-li ještě pro tuto úroveň založeny přihrádky, vyrobíme prázdné.
453 \:Vložíme prvek do~příslušné přihrádky.
458 \:Pokud se prvek nachází v~haldě (to si u~každého prvku pamatujeme), provedeme
459 \<Decrease> v~haldě a skončíme.
460 \:Smažeme prvek z~jeho přihrádky a provedeme \<Insert> s~novou hodnotou.
465 \:Dokud je~$\mu$ menší než aktuální minimum haldy, opakujeme:
466 \::Najdeme přihrádku odpovídající hodnotě~$\mu$.
467 \::Je-li tato přihrádka prázdná, přejdeme na~další (upravíme~$\mu$). Jsme-li na konci úrovně,
468 zrušíme ji, vynulujeme její počítadlo a pokračujeme o~úroveň výš.
469 \::Není-li prázdná, rozprostřeme ji o~úroveň níž (stejným způsobem jako při \<Insert>u,
470 takže prvních~$H$ prvků vložíme do~haldy).
471 \:Smažeme minimum z~haldy a vrátíme ho jako výsledek.
474 \>Pustíme se do~analýzy složitosti. Jako parametry si zvolíme počet hladin~$d$ (takže
475 počet přihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
477 Nejprve si všimneme, že než počítadlo nějaké úrovně vynulujeme, jsou bezpečně
478 z~haldy pryč všechny prvky patřící do~této úrovně. Celkem se tedy v~haldě
479 vyskytuje nejvýše $\O(dH)$ prvků. \<ExtractMin> v~haldě proto trvá $\O(\log(dH))$,
480 ostatní haldové operace $\O(1)$.
482 Nyní rozúčtujeme čas operací mezi jednotlivé prvky (opět si vše předplatíme
483 v~\<Insert>u a ostatní operace poběží v~amortizovaně konstantním čase):
486 \:Každý prvek může být nejvýše jednou za~dobu svého života vložen do~haldy
487 a nejvýše jednou z~ní vyjmut. Na~obojí dohromady přispěje $\O(\log dH)$.
488 \:Prvek se účastní nejvýše~$d$ přehození do~nižší úrovně. Pokud byl přihozen
489 do~haldy, už tam setrvá, jinak pokaždé zaplatí $\O(1)$ za~zařazení do~přihrádky,
490 celkem tedy $\O(d)$ na prvek.
491 \:Vytvoření, projití a smazání přihrádek na~jedné úrovni nastane až tehdy, co bylo
492 $H$~prvků patřících do~této úrovně vloženo do~haldy. Stačí tedy, aby každý
493 prvek přispěl časem $\O(B/H) = \O(L^{1/d}/H)$.
496 \>Každý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
497 Pojďme najít nastavení parametrů, které tento výraz minimalizuje.
498 Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
499 Celý výraz tím zjednodušíme na $\O(d + \log\,(L^{1/d}/d))$ =
500 $\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Oba sčítance volbou
501 $d=\sqrt{\log L}$ vyrovnáme.
503 HOT Queue tedy zvládne \<Insert> s~amortizovanou časovou složitostí $\O(\sqrt{\log L})$
504 a ostatní operace v~čase amortizovaně konstantním. Použijeme-li tuto strukturu
505 v~Dijkstrově algoritmu, spočte vzdálenosti v~čase $\O(m + n\sqrt{\log L})$.
507 \h{Dinicův algoritmus}
509 Zajímavé vylepšení Dijkstrova algoritmu navrhl Dinic. Všiml si, že pokud
510 je každá hrana dlouhá alespoň~$\delta$, můžeme uzavírat nejen
511 vrchol s~minimálním ohodnocením~$\mu$, ale i všechny s~ohodnocením
512 menším než $\mu+\delta$.
514 Pro takto upravený Dijkstrův algoritmus bude stále platit, že při uzavírání
515 vrcholu odpovídá ohodnocení skutečné vzdálenosti, takže uzavřené vrcholy již
516 nejsou znovu otevírány.
518 O~monotonii vzdáleností jsme sice přišli, ale v~přihrádkové struktuře nebo
519 haldě můžeme klíče nahradit hodnotami $h'(v) := \lfloor h(v)/\delta \rfloor$.
520 Tyto hodnoty se totiž chovají monotónně a vrcholy se stejným $h'(v)$ můžeme
523 Kteroukoli z~popsaných přihrádkových struktur můžeme tedy použít, pouze
524 v~rozboru časové složitosti nahradíme~$L$ výrazem $L/\delta$. Tento přístup
525 přitom funguje i pro neceločíselné délky hran, pouze potřebujeme mít předem
526 k~dispozici netriviální dolní odhad na~všechny délky.
530 Viděli jsme, že v~grafech s~nezápornými délkami hran se nejkratší cesty
531 hledají snáze. Nabízí se nalézt nějakou transformaci, která by
532 dovedla délky hran upravit tak, aby byly nejkratší cesty zachovány (samozřejmě
533 ne jejich délky, ale alespoň to, které cesty jsou nejkratší). Nabízí se
534 následující fyzikální inspirace:
536 \s{Definice:} {\I Potenciál} budeme říkat libovolné funkci $\psi: V\rightarrow {\bb R}$.
537 Pro každý potenciál zavedeme {\I redukované délky hran} $\ell_\psi(u,v) := \ell(u,v) + \psi(u) - \psi(v)$.
538 Potenciál nazveme {\I přípustný,} pokud žádná hrana nemá zápornou redukovanou délku.
540 \s{Pozorování:} Pro redukovanou délku libovolné cesty~$P$ z~$u$ do~$v$ platí: $\ell_\psi(P) = \ell(P) + \psi(u) - \psi(v)$.
543 Nechť cesta~$P$ prochází přes vrcholy $u=w_1,\ldots,w_k=v$. Potom:
545 \ell_\psi(P) = \sum_i \ell_\psi(w_i,w_{i+1}) = \sum_i \left( \ell(w_i,w_{i+1}) + \psi(w_i) - \psi(w_{i+1}) \right).
547 Tato suma je ovšem teleskopická, takže z~ní zbude
549 \sum_i\ell(w_i,w_{i+1}) + \psi(w_1) - \psi(w_k) = \ell(P) + \psi(u) - \psi(v).
554 \s{Důsledek:} Potenciálovou redukcí se délky všech cest mezi~$u$ a~$v$
555 změní o~tutéž konstantu, takže struktura nejkratších cest zůstane nezměněna.
557 Zbývá přijít na~to, kde si obstarat nějaký přípustný potenciál. Přidejme do~grafu
558 nový vrchol~$z$, přiveďme z~něj hrany nulové délky do~všech ostatních vrcholů
559 a~označme~$\psi(v)$ vzdálenost ze~$z$ do~$v$ v~tomto grafu. Aby byl tento potenciál
560 přípustný, musí pro každou hranu $uv$ platit $\ell_\psi(u,v) = \ell(u,v) + \psi(u) - \psi(v) \ge 0$.
561 Tuto nerovnost můžeme upravit na $\ell(u,v) + d(z,u) - d(z,v) \ge 0$, čili
562 $d(z,u) + \ell(u,v) \ge d(z,v)$, což je ale obyčejná trojúhelníková nerovnost
563 pro vzdálenost v~grafu, která jistě platí.
565 Jedním výpočtem nejkratších cest v~grafu se zápornými hranami (třeba algoritmem BFM)
566 tedy dokážeme spočítat potenciál, který nám poslouží k~redukci všech hran na~nezáporné
567 délky. To nám samozřejmě nepomůže, chceme-li jednorázově hledat nejkratší cestu,
568 ale může nám to výrazně zjednodušit další, složitější práci s~grafem. Jak uvidíme
569 v~příští kapitole, můžeme tak například nalézt vzdálenosti mezi všemi dvojicemi
570 vrcholů v~čase $\O(nm + n^2\log n)$.
572 Na~závěr tohoto oddílu dokážeme jedno pomocné tvrzení o~potenciálech, které
573 nám pomůže v~konstrukci algoritmů typu \ppsp:
575 \s{Lemma:} Pokud $f$ a~$g$ jsou přípustné potenciály, pak jsou jimi i:
577 \:konvexní kombinace $f$ a~$g$, tedy $\alpha f + \beta g$ pro libovolné $\alpha,\beta\ge 0, \alpha+\beta=1$;
582 \proof Buď $uv$ hrana. Potom z~definice přípustnosti platí $\ell(u,v) \ge f(v) - f(u)$ a $\ell(u,v) \ge g(v) - g(u)$.
583 Jednotlivé části tvrzení dokážeme takto:
585 \:Pokud obě strany nerovnosti pro~$f$ vynásobíme konstantou~$\alpha$, u~nerovnosti pro~$g$
586 konstantou~$\beta$ a obě nerovnosti sečteme, dostaneme:
588 (\alpha+\beta) \cdot \ell(u,v) \ge (\alpha f(v) + \beta g(v)) - (\alpha f(u) + \beta g(u)),
590 což je přesně požadovaná nerovnost pro přípustnost funkce $\alpha f+\beta g$.
591 \:Označme $h := \min(f,g)$. Nechť bez újmy na obecnosti $f(u)\le g(u)$. Pokud také platí $f(v)\le g(v)$,
592 shoduje se minimum s~funkcí~$f$ a není co dokazovat. V~opačném případě je $h(u) = f(u)$, $h(v) = g(v)$.
593 Tehdy si stačí všimnout, že $h(v) - h(u) = g(v) - f(u) < f(v) - f(u) \le \ell(u,v)$, takže
594 potenciál~$h$ je přípustný.
595 \:Dokážeme analogicky.
599 \h{Algoritmy pro problém typu \ppsp}
601 Zaměřme se nyní na~případ, kdy chceme hledat nejkratší cesty mezi zadanou dvojicí
602 vrcholů $s$,~$t$. Obvykle se i v~této situaci používají algoritmy \sssp{} (SSSP) a v~obecném
603 případě ani není efektivnější řešení známo. Existuje ovšem velké množství heuristik, kterými
604 lze obvykle výpočet zrychlit. Některé z~nich si předvedeme na Dijkstrově algoritmu.
606 Dijkstrův algoritmus ve~své klasické podobě neví vůbec nic o~cílovém vrcholu a
607 prohledá celý graf. Hned se nabízí využít toho, že od~okamžiku uzavření
608 kteréhokoliv vrcholu se již jeho ohodnocení nezmění. Pokud tedy uzavřeme cílový
609 vrchol, můžeme se zastavit.
611 Jakou část grafu prohledáváme teď? V~metrice dané vzdálenostmi v~grafu je to nejmenší
612 koule se středem ve~vrcholu~$u$, která obsahuje nejkratší cestu (dobře se to
613 představuje na~hledání v~silniční síti na~rovinné mapě).
615 Také můžeme spustit prohledávání z~obou konců zároveň, tedy zkombinovat hledání
616 od~$s$ v~původním grafu s~hledáním od~$t$ v~grafu s~obrácenou orientací hran.
617 Oba postupy můžeme libovolně střídat a zastavíme se v~okamžiku, kdy jsme jeden
618 vrchol uzavřeli v~obou směrech. Pozor ovšem na to, že součet obou ohodnocení
619 tohoto vrcholu nemusí být roven $d(v,u)$ -- zkuste vymyslet protipříklad.
620 Nejkratší cesta ještě může vypadat tak, že přechází po nějaké hraně mezi vrcholem
621 uzavřeným v~jednom směru a vrcholem uzavřeným ve~směru druhém (ponechme bez důkazu).
622 Stačí tedy během relaxace zjistit, zda je konec hrany uzavřený v~opačném
623 směru prohledávání, a~pokud ano, započítat cestu do~průběžného minima.
625 Obousměrný Dijkstrův algoritmus projde sjednocení nějaké koule okolo~$s$ s~nějakou
626 koulí okolo~$t$, které obsahuje nejkratší cestu. Průměry koulí přitom závisí na tom,
627 jak budeme během výpočtu střídat oba směry prohledávání. V~nejhorším případě samozřejmě
628 můžeme prohledat celý graf.
630 \h{Algoritmus \astar}
632 V~umělé inteligenci se často pro hledání nejkratší cesty v~rozsáhlých grafech
633 (obvykle stavových prostorech úloh) používá algoritmus nazývaný~\astar{} \cite{hart:astar}.
634 Jedná se o~modifikaci Dijkstrova algoritmu, která využívá heuristickou funkci
635 pro dolní odhad vzdálenosti do~cíle; označme si ji $\psi(v)$. V~každém kroku pak uzavíra
636 vrchol~$v$ s~nejmenším možným součtem $h(v)+\psi(v)$ aktuálního ohodnocení s~heuristikou.
638 Intuice za tímto algoritmem je jasná: pokud víme, že nějaký vrchol je blízko
639 od~počátačního vrcholu~$s$, ale bude z~něj určitě daleko do cíle~$t$, zatím ho
640 odložíme a budeme zkoumat nadějnější varianty.
642 Heuristika se přitom volí podle konkrétního problému -- např. hledáme-li cestu
643 v~mapě, můžeme použít vzdálenost do~cíle vzdušnou čarou.
645 Je u~tohoto algoritmu zaručeno, že vždy najde nejkratší cestu? Na to nám dá odpověď
648 \s{Věta:} Běh algoritmu \astar{} odpovídá průběhu Dijkstrova algoritmu
649 na~grafu redukovaném potenciálem~$-\psi$. Přesněji,
650 pokud označíme $h^*$ aktuální ohodnocení v~\astar{} a $h$ aktuální ohodnocení
651 v~synchronně běžícím Dijkstrovi, bude vždy platit $h(v) = h^*(v) - \psi(s) + \psi(v)$.
654 Indukcí podle doby běhu obou algoritmů. Na počátku je $h^*(s)$ i $h(s)$ nulové
655 a všechna ostatní $h^*$ a~$h$ jsou nekonečná, takže tvrzení platí. V~každém dalším
656 kroku \astar{} vybere vrchol~$v$ s~nejmenším $h^*(v) + \psi(v)$, což je tentýž vrchol,
657 který vybere Dijkstra ($\psi(s)$ je stále stejné).
659 Uvažujme, co se stane během relaxace hrany $vw$: Dijkstra se pokusí snížit ohodnocení $h(w)$
660 o~$\delta = h(w) - h(v) - \ell_{-\psi}(v,w)$ a provede to, pokud $\delta>0$. Ukážeme,
661 že \astar{} udělá totéž:
663 \delta &= (h^*(w) - \psi(s) + \psi(w)) - (h^*(v) - \psi(s) + \psi(v)) - (\ell(v,w) - \psi(v) + \psi(w)) \cr
664 &= h^*(w) - \psi(s) + \psi(w) - h^*(v) + \psi(s) - \psi(v) - \ell(v,w) + \psi(v) - \psi(w) \cr
665 &= h^*(w) - h^*(v) - \ell(v,w).
667 Oba algoritmy tedy až na~posunutí dané potenciálem počítají totéž.
670 \s{Důsledek:} Algoritmus \astar{} funguje jen tehdy, je-li potenciál $-\psi$ přípustný.
672 Například pro rovinnou mapu to heuristika daná euklidovskou vzdáleností~$\varrho$, tedy $\psi(v) := \varrho(v,t)$, splňuje:
673 Přípustnost požaduje pro každou hranu $uv$ nerovnost
674 $\ell(u,v) - \psi(v) + \psi(u) \ge 0$,
675 tedy $\ell(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$.
676 Jelikož $\ell(u,v) \ge \varrho(u,v)$,
677 stačí dokázat, že $\varrho(u,v) - \varrho(v,t) + \varrho(u,t) \ge 0$,
678 což je ovšem trojúhelníková nerovnost pro metriku~$\varrho$.
projects / ga.git / blob