3 \prednaska{13}{Nejkrat¹í cesty: relaxaèní metody}{}
9 Problém hledání nejkrat¹í cesty v~(obvykle ohodnoceném orientovaném) grafu
10 provází teorii grafových algoritmù od~samých poèátkù. Základní algoritmy
11 pro hledání cest jsou nedílnou souèástí základních kursù programování
12 a algoritmù, my se budeme vìnovat zejména rùzným jejich vylep¹ením.
14 Mìjme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena
15 {\I délkou} $\ell(e)$, co¾ je nìjaké reálné èíslo. Pro libovolnou
16 posloupnost hran~$P$ (speciálnì tedy pro sled nebo cestu) definujeme
17 její délku $\ell(P)$ jako souèet délek v¹ech hran posloupnosti.
18 Za {\I vzdálenost} $d(u,v)$ dvou vrcholù prohlásíme nejmen¹í mo¾nou
19 délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho,
20 minimum v¾dy existuje). Pokud z~$u$ do~$v$ ¾ádná cesta nevede, polo¾íme
23 Obvykle se studují následující tøi varianty problému:
26 \:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkrat¹í
27 ze~v¹ech cest z~daného vrcholu~$u$ do~daného vrcholu~$v$.
28 \:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme
29 nalézt nejkrat¹í cesty do~v¹ech ostatních vrcholù.
30 \:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkrat¹í cesty
31 mezi v¹emi dvojicemi vrcholù.
34 Pøekvapivì, tak obecnì, jak jsme si uvedené problémy definovali, je neumíme
35 øe¹it v~polynomiálním èase: pro grafy, které mohou obsahovat hrany záporných
36 délek bez jakýchkoliv omezení, je toti¾ hledání nejkrat¹í cesty NP-tì¾ké
37 (lze na~nìj snadno pøevést existence hamiltonovské cesty). V¹echny známé
38 polynomiální algoritmy toti¾ místo nejkrat¹í cesty hledají nejkrat¹í sled
39 -- nekontrolují toti¾ nijak, zda cesta neprojde jedním vrcholem vícekrát.
41 Na¹tìstí pro nás je to v~grafech bez cyklù záporné délky toté¾: pokud se
42 v~nalezeném sledu vyskytne cyklus, mù¾eme jej \uv{vystøihnout} a tím získat
43 sled, který není del¹í, a~který má ménì hran. Ka¾dý nejkrat¹í sled tedy
44 mù¾eme upravit na~stejnì dlouhou cestu.
45 V~grafech bez záporných cyklù je tedy jedno, zda hledáme sled nebo cestu;
46 naopak vyskytne-li se záporný cyklus dosa¾itelný z~poèáteèního vrcholu,
47 nejkrat¹í sled ani neexistuje.
49 Navíc se nám bude hodit, ¾e ka¾dý prefix nejkrat¹í cesty je opìt nejkrat¹í
50 cesta. Jinými slovy pokud nìkterá z~nejkrat¹ích cest z~$u$ do~$v$ vede
51 pøes nìjaký vrchol~$w$, pak její èást z~$u$ do~$w$ je jednou z~nejkrat¹ích
52 cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í
55 Díky této vlastnosti mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom
56 nejkrat¹ích cest}~${\cal T}(u)$. To je strom definovaný na~vrcholech zadaného
57 grafu~$G$, zakoøenìný v~$u$ a orientovaný smìrem od~koøene, takový, ¾e pro ka¾dý
58 vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou z~nejkrat¹ích
59 cest z~$u$ do~$v$ v~grafy~$G$.
61 \>{\bo Pozorování:} Strom nejkrat¹ích cest v¾dy existuje.
64 Nech» $u=v_1,\ldots,v_n$ jsou v¹echny vrcholy grafu~$G$. Indukcí budeme
65 dokazovat, ¾e pro ka¾dé~$i$ existuje strom~${\cal T}_i$, v~nìm¾ se nacházejí nejkrat¹í
66 cesty z~vrcholu~$u$ do vrcholù $v_1,\ldots,v_i$. Pro $i=1$ staèí uvá¾it
67 strom obsahující pouze vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme
68 strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkrat¹í cestu z~$u$ do~$v_i$
69 a oznaèíme~$z$ poslední vrchol na~této cestì, který se je¹tì vyskytuje v~${\cal T}_{i-1}$.
70 Úsek nejkrat¹í cesty od~$z$ do~$v_i$ pak pøidáme do~${\cal T}_{i-1}$
71 a díky prefixové vlastnosti bude i cesta z~$u$ do~$v_i$ v~novém stromu
75 Zbývá se dohodnout, v~jakém tvaru mají na¹e algoritmy vydávat výsledek.
76 U~problémù typu \ppsp{} je nejjednodu¹¹í vypsat celou cestu, u~\sssp{} mù¾eme jako výstup
77 vydat strom nejkrat¹ích cest z~daného poèátku (v¹imnìte si, ¾e staèí
78 uvést pøedchùdce ka¾dého vrcholu), u~\apsp{} vydáme strom nejkrat¹ích cest
79 pro ka¾dý ze~zdrojových vrcholù.
81 Èasto se ov¹em uká¾e, ¾e podstatná èást problému se skrývá v~samotném
82 výpoètu vzdáleností a sestrojení pøedchùdcù je triviálním roz¹íøením algoritmu.
83 Budeme tedy obvykle jen poèítat vzdálenosti a samotnou rekonstrukci cest
84 ponecháme ètenáøi jako snadné cvièení.
86 \h{Relaxaèní algoritmus}
88 Zaènìme problémem \sssp{} a oznaème~$u$ výchozí vrchol. Vìt¹ina známých
89 algoritmù funguje tak, ¾e pro ka¾dý vrchol~$v$ udr¾ují ohodnocení $h(v)$,
90 které v~ka¾dém okam¾iku odpovídá délce nìjakého sledu z~$u$ do~$v$. Postupnì
91 toto ohodnocení upravují, a¾ se z~nìj stane vzdálenost $d(u,v)$ a algoritmus
94 Vhodnou operací pro vylep¹ování ohodnocení je takzvaná {\I relaxace.}
95 Vybereme si nìjaký vrchol~$v$ a pro v¹echny jeho sousedy~$w$ spoèítáme
96 $h(v) + \ell(v,w)$, tedy délku sledu, který vznikne roz¹íøením aktuálního
97 sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota men¹í ne¾~$h(w)$,
98 tak jí $h(w)$ pøepí¹eme.
100 Relaxace tedy zachovává to, ¾e ohodnocení odpovídá délkám nìjakých sledù,
101 a~souèasnì toto ohodnocení mù¾e zlep¹ovat. Budeme se tedy sna¾it nìjaké
102 poèáteèní ohodnocení (nabízí se $h(u)=0$, $h(v)=\infty$ pro $v\ne u$)
103 postupnými relaxacemi pøetvoøit na~ohodnocení vzdálenostmi.
105 Abychom zabránili opakovaným relaxacím tého¾ vrcholu, které nic nezmìní,
106 budeme rozli¹ovat tøi stavy vrcholù: {\I nevidìn} (je¹tì jsme ho nenav¹tívili),
107 {\I otevøen} (zmìnilo se ohodnocení, èasem chceme relaxovat) a {\I uzavøen}
108 (u¾ jsme relaxovali a není potøeba znovu).
110 Ná¹ algoritmus bude fungovat následovnì:
113 \:$h(*)\leftarrow \infty$, $h(u)\leftarrow 0$.
114 \:$\<stav>(*)\leftarrow\<nevidìn>$, $\<stav>(u)\leftarrow\<otevøen>$.
115 \:Dokud existují otevøené vrcholy, opakujeme:
116 \::$v\leftarrow\hbox{libovolný otevøený vrchol}$.
117 \::$\<stav>(v)\leftarrow\<uzavøen>$.
119 \:::Pro v¹echny hrany $(v,w)$ opakujeme:
120 \::::Je-li $h(w) < h(v) + \ell(v,w)$:
121 \:::::$h(w)\leftarrow h(v) + \ell(v,w)$.
122 \:::::$\<stav>(w)\leftarrow\<otevøen>$.
123 \:Vrátíme výsledek $d(u,v)=h(v)$ pro v¹echna~$v$.
126 Podobnì jako u~minimálních koster, i zde se jedná o~meta-algoritmus, proto¾e
127 v~kroku~4 nespecifikuje, podle jakého pravidla se vrchol~$v$ vybírá. Pøesto
128 ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu
131 \>\s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak:
134 \:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu -- doká¾eme indukcí podle poètu krokù algoritmu.
135 \:$h(v)$ dokonce odpovídá délce nìjaké cesty -- staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus.
136 \:Algoritmus se v¾dy zastaví -- cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro
137 ka¾dý~$v$, je koneènì mnoho.
138 \:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$ --
139 implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol,
140 který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran.
141 \:Po zastavení mají koneèné~$h(v)$ právì v¹echny uzavøené vrcholy.
142 \:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$ -- kdyby to nebyla pravda,
143 vyberme si ze~\uv{¹patných} vrcholù~$v$ takový, pro nìj¾ obsahuje nejkrat¹í cesta z~$u$ do~$v$
144 nejmen¹í mo¾ný poèet hran. Vrchol~$v$ je zajisté rùzný od~$u$, tak¾e má na~této cestì nìjakého
145 pøedchùdce~$w$. Pøitom~$w$ u¾ musí být ohodnocen správnì a relaxace, která mu toto ohodnocení
146 nastavila, ho musela prohlásit za~otevøený. Jen¾e ka¾dý otevøený vrchol je pozdìji uzavøen,
147 tak¾e~$w$ poté musel být je¹tì alespoò jednou relaxován, co¾ muselo sní¾it~$h(v)$ na správnou
151 \>Meta-algoritmus tedy pro libovolnou implementaci kroku~4 spoèítá správné vzdálenosti.
156 \:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9
157 pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$u$. Doka¾te, ¾e pøedchùdci
158 dosa¾itelných vrcholù budou tvoøit strom a ¾e tento strom bude stromem
159 nejkrat¹ích cest z~vrcholu~$u$.
160 \:Doka¾te, ¾e pro graf, v~nìm¾ je alespoò jeden záporný cyklus dosa¾itelný
161 z~poèáteèního vrcholu, se algoritmus nezastaví a ohodnocení v¹ech vrcholù
162 na cyklu postupnì klesnou libovolnì hluboko. Nedosa¾itelné záporné cykly
163 chod algoritmu samozøejmì nijak neovlivní.
166 \h{Bellmanùv-Fordùv-Mooreùv algoritmus}
168 Bellman, Ford a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM),
169 který lze v~øeèi na¹eho meta-algoritmu formulovat takto: Otevøené vrcholy
170 udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané
171 zaøazujeme na~konec. Co toto pravidlo zpùsobí?
173 \>\s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$.
176 Bìh algoritmu rozdìlíme na~fáze. Nultá fáze sestává z~vlo¾ení vrcholu~$u$
177 do~fronty. V~$(i+1)$-ní fázi relaxujeme ty vrcholy, které byly do~fronty
178 ulo¾eny bìhem $i$-té fáze.
180 V¹imneme si, ¾e na~konci $i$-té fáze je ka¾dé ohodnocení $h(v)$ shora omezeno
181 délkou nejkrat¹ího ze~sledù z~$u$ do~$v$, které mají nejvý¹e~$i$ hran. Fází je
184 Relaxace ka¾dého vrcholu pøitom trvá lineárnì se stupnìm vrcholu, tak¾e celá
185 fáze probìhne v~èase $\O(m)$.
190 \:Uka¾te, ¾e asymptoticky stejné èasové slo¾itosti by dosáhl algoritmus,
191 který by vrcholy oèísloval $v_1,\ldots,v_n$ a opakovanì by je v~tomto
192 poøadí relaxoval tak dlouho, dokud by se ohodnocení mìnila.
193 \:Jak algoritmus upravit, aby v~$i$-té fázi spoèítal minimální délky sledù
195 \:Jak lze algoritmus BFM vyu¾ít k~nalezení záporného cyklu?
198 \h{Dijkstrùv algoritmus}
200 Pokud jsou v¹echny délky hran nezáporné, mù¾eme pou¾ít efektivnìj¹í pravidlo
201 pro výbìr vrcholu navr¾ené Dijkstrou. To øíká, ¾e v¾dy relaxujeme ten z~otevøených
202 vrcholù, jeho¾ ohodnocení je nejmen¹í.
204 \>\s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající
205 vzdálenosti od~$u$ a ka¾dý dosa¾itelný vrchol uzavøe právì jednou.
208 Indukcí doká¾eme, ¾e v~ka¾dém okam¾iku mají v¹echny uzavøené vrcholy ohodnocení
209 men¹í nebo rovné ohodnocením v¹ech otevøených vrcholù. Na~poèátku to jistì platí.
210 Nech» nyní uzavíráme vrchol~$v$ s~minimálním $h(v)$ mezi otevøenými. Bìhem jeho
211 relaxace nemù¾eme ¾ádnou hodnotu sní¾it pod~$h(v)$, jeliko¾ v~grafu s~nezápornými
212 hranami je $h(v) + \ell(v,w) \ge h(v)$. Hodnota zbývajících otevøených vrcholù
213 tedy neklesne pod hodnotu tohoto novì uzavøeného. Hodnoty døíve uzavøených vrcholù
214 se nemohou nijak zmìnit.
217 Pøímoèará implementace Dijkstrova algoritmu by tedy poka¾dé v~èase $\O(n)$
218 vybrala otevøený vrchol s~nejmen¹ím ohodnocením, v~èase $\O(n)$ ho relaxovala
219 a toto by se opakovalo nejvý¹e $n$-krát. Algoritmus by tedy dobìhl v~èase $\O(n^2)$,
220 co¾ je pro husté grafy zajisté optimální. Zkusíme tedy algoritmus zrychlit
223 V¹echny relaxace trvají dohromady $\O(\sum_v \deg(v)) = \O(m)$, tak¾e úzkým hrdlem je
224 vybírání minima. Pou¾ijeme tedy vhodnou datovou strukturu, v~ní¾ budeme udr¾ovat
225 mno¾inu v¹ech otevøených vrcholù spolu s~jejich ohodnoceními. Od~datové struktury
226 potøebujeme, aby umìla operace \<Insert> (vlo¾ení vrcholu), \<ExtractMin> (nalezení
227 a smazání minima) a \<Decrease> (sní¾ení hodnoty vrcholu). První dvì operace pøitom
228 voláme nejvý¹e $n$-krát a operaci \<Decrease> nejvý¹e $m$-krát. Celý algoritmus
230 $$\O(nT_I(n) + nT_E(n) + mT_D(n)),$$
231 kde $T_I(n)$, $T_E(n)$ a $T_D(n)$ jsou èasové slo¾itosti jednotlivých operací
232 na~struktuøe o~nejvý¹e~$n$ prvcích (staèí amortizovanì).
234 \>Jaké mo¾nosti máme pro volbu struktury?
237 \:{\I pole} -- \<Insert> a \<Decrease> stojí konstantu, \<ExtractMin> trvá $\O(n)$,
238 celkem tedy $\O(n^2)$.
239 \:{\I (binární) halda} -- v¹echny tøi operace umíme provést v~èase $\O(\log n)$, tak¾e celkem
240 $\O(m\log n)$. To je pro husté grafy hor¹í, pro øídké lep¹í.
241 \:{\I $k$-regulární halda} -- pokud haldu upravíme tak, ¾e ka¾dý vrchol bude mít a¾ $k$ synù,
242 hloubka haldy klesne na~$\O(\log_k n)$. Operace \uv{vybublávající} prvky smìrem nahoru,
243 co¾ je \<Insert> a \<Decrease>, se zrychlí na~$\O(\log_k n)$. Ov¹em \<ExtractMin> potøebuje
244 zkoumat v¹echny syny ka¾dého nav¹tíveného prvku, tak¾e se zpomalí na $\O(k\log_k n)$.
246 Celková slo¾itost tedy vyjde $\O(nk\log_k n + m\log_k n)$. Oba èleny se vyrovnají
247 pro $k=m/n$, èím¾ získáme $\O(m\log_{m/n} n)$. Tento logaritmus je pøitom $\O(1)$,
248 kdykoliv je $m\ge n^{1+\varepsilon}$ pro nìjaké~$\varepsilon>0$, tak¾e pro dostateènì
249 husté grafy je algoritmus lineární.
251 (V¹imnìte si, ¾e pro $m\approx n^2$ algoritmus zvolí $k\approx n$, tak¾e halda degeneruje
252 na jediné patro, tedy na pole, které se opravdu ukázalo jako optimální volba pro husté grafy.)
253 \:{\I Fibonacciho halda} -- \<Insert> a \<Decrease> stojí $\O(1)$, \<ExtractMin> má slo¾itost
254 $\O(\log n)$ [v¹e amortizovanì]. Dijkstrùv algoritmus tedy dobìhne v~èase $\O(m + n\log n)$.
255 To je lineární pro grafy s~hustotou $\Omega(\log n)$.
256 \:{\I Monotónní haldy} -- mù¾eme pou¾ít nìjakou jinou haldu, která vyu¾ívá toho,
257 ¾e posloupnost odebíraných prvkù neklesající. Pro celá èísla na~RAMu to mù¾e
258 být napøíklad Thorupova halda (REF) se slo¾itostí $\O(\log\log n)$ na~\<ExtractMin>
259 a $\O(1)$ u~ostatních operací. Dijkstra tedy bì¾í v~$\O(m + n\log\log n)$.
260 \:{\I Datové struktury pro omezené universum} -- prozkoumáme vzápìtí.
266 \:Najdìte pøíklad nìjakého grafu se zápornými hranami (ale bez záporných cyklù),
267 na~kterém Dijkstrùv algoritmus sel¾e.
268 \:Rozmyslete si, ¾e pokud nevyu¾ijeme nìjaké speciální vlastnosti èísel (celoèíselnost,
269 omezený rozsah), je mez $\O(m+n\log n)$ nejlep¹í mo¾ná, proto¾e Dijkstrovým algoritmem
270 mù¾eme tøídit $n$-tici èísel. Thorup dokonce dokázal (REF), ¾e z~ka¾dého tøídícího algoritmu
271 se slo¾itostí $nT(n)$ mù¾eme odvodit monotónní haldu se slo¾itostí mazání $\O(T(n))$.
272 \:Jsou-li délky hran celoèíselné, mù¾eme se na Dijkstrùv algoritmus dívat i takto:
273 Pøedstavme si, ¾e ka¾dou hranu nahradíme cestou tvoøenou hranami jednotkové délky
274 a na vzniklý neohodnocený graf spustíme prohledávání do~¹íøky. To samozøejmì vydá
275 správný výsledek, ale pomìrnì pomalu, proto¾e bude vìt¹inu èasu trávit posouváním
276 vlny \uv{uvnitø} pùvodních hran. Mù¾eme si tedy pro ka¾dou pùvodní hranu naøídit
277 \uv{budík}, který nám øekne, za~kolik posunutí vlny dospìjeme na~její konec.
278 Doka¾te, ¾e tento algoritmus je ekvivalentní s~Dijkstrovým.
281 \h{Celoèíselné délky}
283 Uva¾ujme nyní grafy, v~nich¾ jsou v¹echny délky hran nezáporná celá èísla omezená
284 nìjakou konstantou~$L$. V¹echny vzdálenosti jsou tedy omezeny èíslem~$nL$, tak¾e
285 nám staèí datová struktura schopná uchovávat takto omezená celá èísla.
287 Pou¾ijeme jednoduchou pøihrádkovou strukturu: pole indexované hodnotami od~0 do~$nL$,
288 jeho $i$-tý prvek bude obsahovat seznam vrcholù, jejich¾ ohodnocení je rovno~$i$.
289 Operace \<Insert> a \<Decrease> zvládneme v~konstantním èase, budeme-li si u~ka¾dého
290 prvku pamatovat jeho polohu v~seznamu. Operace \<ExtractMin> potøebuje najít první
291 neprázdnou pøihrádku, ale jeliko¾ víme, ¾e posloupnost odebíraných minim je monotónní,
292 staèí hledat od místa, kde se hledání zastavilo minule. V¹echna hledání pøihrádek
293 tedy zaberou dohromady $\O(nL)$ a celý Dijkstrùv algoritmus bude trvat $\O(nL + m)$.
295 Prostorová slo¾itost $\O(nL+m)$ je nevalná, ale mù¾eme ji jednoduchým trikem
296 sní¾it: V¹imneme si, ¾e v¹echna koneèná ohodnocení vrcholù nemohou být vìt¹í
297 ne¾ aktuální minimum zvìt¹ené o~$L$. Jinými slovy v¹echny neprázdné pøihrádky
298 se nacházejí v~úseku pole dlouhém~$L+1$, tak¾e staèí indexovat modulo~$L+1$.
299 Pouze si musíme dávat pozor, abychom správnì poznali, kdy se struktura
300 vyprázdnila, co¾ zjistíme napøíklad pomocí poèítadla otevøených vrcholù. Èas si
301 asymptoticky nezhor¹íme, prostor klesne na~$\O(L+m)$.
303 Podobný trik mù¾eme pou¾ít i pro libovolnou jinou datovou strukturu: rozsah èísel
304 rozdìlíme na~\uv{okna} velikosti~$L$ (v~$i$-tém oknì jsou èísla $Li,\ldots,L(i+1)-1$).
305 V~libovolné chvíli mohou tedy být neprázdná nejvý¹e dvì okna. Staèí nám proto
306 poøídit si dvì struktury pro ukládání èísel v~rozsahu $0,\ldots,L-1$ -- jedna
307 z~nich bude reprezentovat aktuální okno (to, v~nìm¾ le¾elo minulé minimum),
308 druhá okno bezprostøednì následující. Minimum ma¾eme z~první struktury; pokud
309 u¾ je prázdná, obì struktury prohodíme. Operace \<Insert> podle hodnoty urèí,
310 do~které struktury se má vkládat. S~operací \<Decrease> je to slo¾itìj¹í --
311 hodnota z~vy¹¹í struktury mù¾e pøeskoèit do té ni¾¹í, ale v~takovém pøípadì
312 ji ve~vy¹¹í struktuøe vyma¾eme (to je \<Decrease> na $-\infty$ následovaný
313 \<ExtractMin>em) a do~ni¾¹í vlo¾íme. To se ka¾dému prvku mù¾e pøihodit nejvý¹e
314 jednou, tak¾e stále platí, ¾e se ka¾dý prvek úèastní $\O(1)$ vlo¾ení a $\O(1)$
317 Ukázali jsme tedy, ¾e pro na¹e potøeby postaèuje struktura schopná uchovávání
318 èísel men¹ích nebo rovných~$L$.
320 Nabízí se pou¾ít van Emde-Boasùv strom z~kapitoly o~výpoèetních modelech.
321 Ten dosahuje slo¾itosti $\O(\log\log L)$ pro operace \<Insert> a \<ExtractMin>,
322 operaci \<Decrease> musíme pøekládat na \<Delete> a \<Insert>. Celková
323 slo¾itost Dijkstrova algoritmu vyjde $\O(L+m\log\log L)$, pøièem¾ èas~$L$
324 spotøebujeme na inicializaci struktury (té se lze za jistých podmínek vyhnout,
325 viz zmínìná kapitola).
327 Vra»me se ale je¹tì k~vyu¾ití pøihrádek\dots
329 \h{Víceúrovòové pøihrádky}
331 Podobnì jako u~tøídìní èísel, i~zde se vyplácí stavìt pøihrádkové struktury
332 víceúrovòovì. Jednotlivé hodnoty budeme zapisovat v~soustavì o~základu~$B$,
333 který zvolíme jako nìjakou mocnina dvojky, abychom mohli s~èíslicemi tohoto
334 zápisu snadno zacházet pomocí bitových operací. Ka¾dé èíslo tedy zabere nejvý¹e
335 $d=1+\lfloor\log_B L\rfloor$ èíslic; pokud bude krat¹í, doplníme ho zleva nulami.
337 Nejvy¹¹í patro struktury bude tvoøeno polem $B$~pøihrádek, v~$i$-té z~nich
338 budou ulo¾ena ta èísla, jejich¾ nejvy¹¹í øád je roven~$i$. Za~{\I aktivní}
339 prohlásíme tu pøihrádku, která obsahuje aktuální minimum. Pøihrádky s~men¹ími
340 indexy jsou prázdné a zùstanou takové a¾ do~konce výpoètu, proto¾e halda
341 je monotónní. Pokud v~pøihrádce obsahující minimum bude více prvkù, budeme
342 ji rozkládat podle druhého nejvy¹¹ího øádu na dal¹ích~$B$ pøihrádek atd.
343 Celkem tak vznikne a¾~$d$ úrovní.
345 \>Struktura bude obsahovat následující data:
348 \:Parametry $L$, $B$ a~$d$.
349 \:Pole úrovní (nejvy¹¹í má èíslo~$d-1$, nejni¾¹í~0), ka¾dá úroveò je buïto prázdná
350 (a pak jsou prázdné i~v¹echny ni¾¹í), nebo obsahuje pole~$U_i$ o~$B$ pøihrádkách,
351 z~nich¾ ka¾dá obsahuje seznam prvkù. Toto pole pou¾íváme jako zásobník, udr¾ujeme
352 si èíslo nejni¾¹í neprázdné úrovnì.
353 \:Hodnotu~$\mu$ pøedchozího odebraného minima.
356 Operace \<Insert> vlo¾í hodnotu do~nejhlub¹í mo¾né pøihrádky. Podívá se tedy
357 na~nejvy¹¹í úroveò: pokud hodnota patøí do pøihrádky, která není aktivní, vlo¾í
358 ji pøímo. Jinak pøejde o~úroveò ní¾e a zopakuje stejný postup. To v¹e lze provést
359 v~konstantním èase: staèí se podívat, jaký je nejvy¹¹í jednièkový bit ve~{\sc xor}u
360 nové hodnoty s~èíslem~$\mu$ (opìt viz kapitola o~výpoèetních modelech).
362 Pokud chceme provést \<Decrease>, odstraníme hodnotu z~pøihrádky, ve~které se
363 právì nachází (polohu si mù¾eme u~ka¾dé hodnoty pamatovat zvlá¹»), a znovu ji
366 Vìt¹inu práce samozøejmì pøenecháme funkci \<ExtractMin>. Ta zaène prohledávat
367 nejni¾¹í obsazenou úroveò od~aktivní pøihrádky dál (to, která pøihrádka je na
368 které úrovni aktivní, poznáme z~èíslic hodnoty~$\mu$). Pokud pøihrádky na~této
369 úrovni dojdou, prázdnou úroveò zru¹í a pokraèuje o~patro vý¹e.
371 Jakmile najde neprázdnou pøihrádku, nalezne v~ní minimum a to se stane novým~$\mu$.
372 Pokud v~pøihrádce nebyly ¾ádné dal¹í prvky, skonèí. Jinak zbývající prvky
373 rozprostøe do~pøihrádek na~bezprostøednì ni¾¹í úrovni, kterou tím zalo¾í.
375 Èas strávený hledáním minima mù¾eme rozdìlit na~nìkolik èástí:
378 \:$\O(B)$ na inicializaci nové úrovnì -- to naúètujeme prvku, který jsme
380 \:hledání neprázdných pøihrádek -- prozkoumání ka¾dé prázdné pøihrádky
381 naúètujeme jejímu vytvoøení, co¾ se rozpustí v~$\O(B)$ na inicializaci
383 \:zru¹ení úrovnì -- opìt naúètujeme jejímu vzniku;
384 \:rozhazování prvkù do pøihrádek -- jeliko¾ prvky v~hierarchii pøihrádek
385 putují bìhem operací pouze doleva a dolù (jejich hodnoty se nikdy nezvìt¹ují),
386 klesne ka¾dý prvek nejvý¹e~$d$-krát, tak¾e staèí, kdy¾ na v¹echna rozhazování
387 pøispìje èasem $\O(d)$.
390 \>Staèí tedy, aby ka¾dý prvek pøi \<Insert>u zaplatil èas $\O(B+d)$ a jak \<Decrease>,
391 tak \<ExtractMin> pak budou mít konstantní amortizovanou slo¾itost. Dijkstrùv
392 algoritmus pak pobì¾í v~$\O(m + n(B+d))$.
394 Zbývá nastavit parametry tak, abychom minimalizovali výraz $B+d = B + \log L/\log B$.
395 Vhodná volba je $B=\log L/\log\log L$. Pøi ní platí
397 {\log L\over\log B} = {\log L \over \log\left(\log L/\log\log L\right) }
398 = {\log L\over \log\log L - \log\log\log L} = \Theta(B).
400 Tehdy Dijkstra vydá výsledek v~èase $\O(m + n\cdot{\log L\over\log\log L})$.
402 \h{HOT Queue -- kombinace pøihrádek s~haldou}
404 Goldberg a Cherkassky (REF) si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách
405 platíme pøíli¹ mnoho za~úrovnì, ve~kterých se za~dobu jejich existence objeví jen malé
406 mno¾ství prvkù. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~spoleèné haldy.
407 Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. My si pøedvedeme její upravenou
408 variantu (v~té pùvodní se skrývá nìkolik chyb).
410 Poøídíme si haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající,
411 kolik prvkù z~této úrovnì jsme ulo¾ili do~haldy. Dokud toto poèítadlo nepøeroste nìjaký
412 parametr~$H$, pøihrádky nebudeme zakládat a prvky poputují do~haldy. Èas $\O(B)$ na
413 zalo¾ení úrovnì a její procházení tedy mù¾eme rozpoèítat mezi~$H$ prvkù, které se musely
414 na~dané úrovni objevit, ne¾ byla rozpøihrádkována. (Pov¹imnìte si, ¾e poèítadlo nikdy
415 nesni¾ujeme, pouze ho vynulujeme, kdy¾ je úroveò zru¹ena, tak¾e vùbec nemusí odpovídat
416 skuteènému poètu prvkù z~pøíslu¹né úrovnì, které jsou právì ulo¾eny v~haldì. To ov¹em
417 vùbec nevadí -- poèítadlo pouze hlídá, aby se úroveò nevytvoøila pøíli¹ brzy a abychom
418 mìli dost prvkù k~rozúètování èasu.)
420 Promìnnou~$\mu$ necháme ukazovat na~místo, kde jsme se pøi hledání minima v~pøihrádkách
421 zastavili. Souèasné globální minimum struktury tedy mù¾e být ni¾¹í, kdy¾ se minimum
422 zrovna nachází v~haldì, ale stále je zaruèeno, ¾e pøed~$\mu$ se ji¾ nenachází ¾ádná
425 Operace budou fungovat takto:
429 \:Spoèítáme, do~které úrovnì~$i$ ma prvek padnout.
430 \:Pokud je poèítadlo této úrovnì men¹í ne¾~$K$, zvý¹íme ho, vlo¾íme prvek do~haldy a skoèíme.
431 \:Nebyly-li je¹tì pro tuto úroveò zalo¾eny pøihrádky, vyrobíme je (prázdné).
432 \:Vlo¾íme prvek do~pøíslu¹né pøihrádky.
437 \:Pokud se prvek nachází v~haldì (to si u~ka¾dého prvku pamatujeme), provedeme
438 \<Decrease> v~haldì a skonèíme.
439 \:Sma¾eme prvek z~jeho pøihrádky a provedeme \<Insert> s~novou hodnotou.
444 \:Dokud je~$\mu$ men¹í ne¾ aktuální minimum haldy, opakujeme:
445 \::Najdeme pøihrádku odpovídající hodnotì~$\mu$.
446 \::Je-li tato pøihrádka prázdná, pøejdeme na~dal¹í (upravíme~$\mu$). Jsme-li na konci úrovnì, pak o~úroveò vý¹.
447 \::Rozprostøeme tuto pøihrádku o~úroveò ní¾ (stejným zpùsobem, jako pøi \<Insert>u,
448 tak¾e prvních~$H$ prvkù vlo¾íme do~haldy).
449 \:Sma¾eme minimum z~haldy a vrátíme ho jako výsledek.
452 \>Pustíme se do~analýzy slo¾itosti. Jako parametry si zvolíme poèet hladin~$d$ (tak¾e
453 poèet pøihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
455 Nejprve si v¹imneme, ¾e ne¾ poèítadlo nìjaké úrovnì vynulujeme, jsou bezpeènì
456 z~haldy pryè v¹echny prvky patøící do~této úrovnì. Celkem se tedy v~haldì
457 vyskytuje nejvý¹e $\O(dH)$ prvkù. \<ExtractMin> v~haldì tedy trvá $\O(\log(dH))$,
458 ostatní haldové operace $\O(1)$.
460 Nyní rozúètujeme èas operací mezi jednotlivé prvky (opìt si v¹e pøedplatíme
461 v~\<Insert>u a ostatní operace pobì¾í v~amortizovanì konstantním èase):
464 \:Ka¾dý prvek mù¾e být nejvý¹e jednou za~dobu svého ¾ivota vlo¾en do~haldy
465 a nejvý¹e jednou z~ní vyjmut. Na~obojí dohromady pøispìje $\O(\log dH)$.
466 \:Prvek se úèastní nejvý¹e~$d$ pøehození do~ni¾¹í úrovnì. Pokud byl pøihozen
467 do~haldy, u¾ tam setrvá, jinak poka¾dé zaplatí $\O(1)$ za~zaøazení do~pøihrádky,
468 celkem tedy $\O(d)$ na prvek.
469 \:Vytvoøení, projití a smazání pøihrádek na~jedné úrovni nastane a¾ tehdy, co bylo
470 $H$~prvkù patøících do~této úrovnì vlo¾eno do~haldy. Staèí tedy, aby ka¾dý
471 prvek pøispìl èasem $\O(B/H) = \O(L^{1/d}/H)$.
474 \>Ka¾dý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
475 Pojïme najít nastavení parametrù, abychom tento výraz minimalizovali.
476 Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
477 Celý výraz tím zjednodu¹íme na $\O(d + \log\,(L^{1/d}/d))$ =
478 $\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Dále zvolíme~$d$
479 tak, aby se oba výrazy vyrovnaly, èili $d=\sqrt{\log L}$.
481 HOT Queue tedy zvládne \<Insert> amortizovanou èasovou slo¾itostí $\O(\sqrt{\log L})$
482 a ostatní operace v~èase amortizovanì konstantním. Pou¾ijeme-li tuto strukturu
483 v~Dijkstrovì algoritmu, spoète vzdálenosti v~èase $\O(m + n\sqrt{\log L})$.