]> mj.ucw.cz Git - ga.git/blob - 9-decomp/9-decomp.tex
Dekompozice: Oprava preklepu v analyze Union-Findu
[ga.git] / 9-decomp / 9-decomp.tex
1 \input ../sgr.tex
2
3 \hyphenation{mikro-strom mikro-stro-mo-vé}
4
5 \prednaska{9}{Dekompozice stromù}{}
6
7 V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených
8 na~my¹lence dekompozice problému na~dostateènì malé podproblémy,
9 které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
10 èase.
11
12 \h{Union-Find Problem}
13
14 \s{Problém:} Udr¾ování tøíd ekvivalence: na~poèátku máme $N$ jednoprvkových ekvivalenèních
15 tøíd, provádíme operace \<Find> (zji¹tìní, zda dva prvky jsou ekvivalentní) a \<Union>
16 (slouèení dvou tøíd do~jedné). Také na~to lze pohlí¾et jako na~inkrementální udr¾ování
17 komponent souvislosti neorientovaného grafu: \<Union> je pøidání hrany, \<Find> test,
18 zda dva vrcholy le¾í v~té¾e komponentì. To se hodí v~mnoha algoritmech, kupøíkladu
19 v~Kruskalovì algoritmu pro hledání minimální kostry.
20
21 \s{Triviální øe¹ení:} Prvky ka¾dé tøídy obarvíme unikátní barvou (identifikátorem
22 tøídy). Operace \<Find> porovnává barvy, \<Union> prvky jedné ze~sjednocovaných
23 tøíd pøebarvuje.
24
25 Operace \<Find> tak pracuje v~konstantním èase, \<Union> mù¾e zabrat a¾ lineární èas. Mù¾eme si
26 pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme
27 si pro ka¾dou tøídu pamatovat seznam jejích prvkù a velikost). Tehdy mù¾e být ka¾dý
28 prvek pøebarven jen $\O(\log n)$-krát, jeliko¾ ka¾dým pøebarvením se alespoò zdvojnásobí
29 velikost tøídy, ve~které prvek le¾í. Posloupnost operací \<Union>, kterou vznikla tøída
30 velikosti~$k$, tak trvá $\O(k\log k)$, tak¾e mù¾eme bezpeènì prohlásit, ¾e amortizovaná
31 slo¾itost operace \<Union> je $\O(\log n)$.
32
33 \s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami
34 orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce
35 nebo ¾e je to koøen). \<Find> nalezne koøeny stromù a porovná je, \<Union> pøipojí koøen
36 jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì pravidla:
37
38 \itemize\ibull
39 \:{\I Union dle ranku:} ka¾dý koøen $v$ si bude pamatuje svùj rank $r(v)$, co¾ je nìjaké
40 pøirozené èíslo. Na~poèátku jsou v¹echny ranky nulové. Pokud spojujeme
41 dva stromy s~koøeny $v$, $w$ a $r(v)<r(w)$, pøipojíme $v$ pod~$w$ a rank zachováme.
42 Pokud $r(v)=r(w)$, pøipojíme libovolnì a nový koøen bude mít rank $r(v)+1$.%
43 \foot{Stejnì by fungovalo pravidlo {\I Union dle velikosti,} které pøipojuje men¹í
44 strom pod vìt¹í, ale ranky máme radìji, neb jsou skladnìj¹í a snáze se analyzují.}
45
46 \:{\I Komprese cest:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
47 bìhem operace \<Find>), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li,
48 rovnou pod koøen.
49 \endlist
50
51 Pro úèely analýzy struktury budeme uva¾ovat také ranky ostatních vrcholù -- ka¾dý vrchol
52 si ponese svùj rank z~doby, kdy byl naposledy koøenem. Struktura se ov¹em
53 podle rankù vnitøních vrcholù nijak neøídí a nemusí si je ani pamatovat.
54 Stromu s~koøenem ranku~$r$ budeme zkrácenì øíkat {\I strom ranku~$r$.}
55
56 \s{Invariant~C:} Na ka¾dé cestì z~vrcholu do~koøene pøíslu¹ného stromu ranky
57 ostøe rostou. Jinými slovy rank vrcholu, který není koøen, je men¹í, ne¾ je rank
58 jeho otce.
59
60 \proof
61 Na poèátku (pro jednovrcholové stromy) tvrzení jistì platí.
62 Nech» provedeme Union, který pøipojí vrchol~$v$ pod~$w$. Cesty do~koøene z~vrcholù,
63 které le¾ely pod~$w$, zùstanou zachovány, pouze se vrcholu~$w$ pøípadnì
64 zvý¹í rank. Cesty z~vrcholù pod~$v$ se roz¹íøí o~hranu~$vw$, na které rank
65 v~ka¾dém pøípadì roste.
66 Komprese cest nahrazuje otce vrcholu jeho vzdálenìj¹ím pøedkem, tak¾e se rank
67 otce mù¾e jedinì zvý¹it.
68 \qed
69
70 \s{Invariant~R:} Strom ranku~$r$ obsahuje alespoò $2^r$ vrcholù.
71
72 \proof
73 Indukcí podle èasu. Pro jednovrcholové stromy o~nulovém ranku tvrzení platí.
74 Nech» pøipojíme vrchol~$v$ pod vrchol~$w$. Je-li $r(v)<r(w)$, rank stromu
75 zùstane zachován a strom se je¹tì zvìt¹í. Je-li $r(v)=r(w)$, rank stromu
76 se zvìt¹í o~1, ale z~indukce víme, ¾e oba spojované stromy mìly alespoò
77 $2^{r(v)}$ vrcholù, tak¾e jejich spojením vznikne strom o~alespoò $2^{r(v)+1}$
78 vrcholech. Komprese cest zasahuje pouze do~vnitøní struktury stromu, ranky
79 ani velikosti stromù nemìní.
80 \qed
81
82 \s{Dùsledek:} Rank ka¾dého stromu je $\O(\log n)$, tak¾e rank ka¾dého vnitøního
83 vrcholu takté¾. Díky invariantu~C strávíme výstupem z~ka¾dého vrcholu do~koøene
84 také èas $\O(\log n)$, tak¾e logaritmická je i slo¾itost operací \<Union> a \<Find>.
85
86 K~tomu nám ov¹em staèilo samotné pravidlo Union podle ranku, o~kompresi cest
87 jsme zatím dokázali pouze to, ¾e slo¾itost v~nejhor¹ím pøípadì nezhor¹uje.%
88 \foot{Mimochodem, Komprese cest samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila \cite{tarjan84setunion}.}
89 Kombinace obou metod se ve~skuteènosti chová mnohem lépe:
90
91 \s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion})
92 Posloupnost $m$~operací \<Union> a \<Find> provedená na~prázdné struktuøe s~$n$ vrcholy
93 trvá $\O(n + m\alpha(m,n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
94 \foot{Je známo \cite{fredman:cellprobe}, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout,
95 a~to ani v~modelu silnìj¹ím ne¾ RAM. Námi uvádìný algoritmus si témìø vystaèí
96 s~Pointer Machine, jen porovnávání rankù z~tohoto modelu vyboèuje. Slo¾itost
97 operací v~nejhor¹ím pøípadì je obecnì hor¹í, je znám dolní odhad $\Omega(\log n/\log\log n)$;
98 více viz Alstrup \cite{alstrup:worstuf}.}
99
100 Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný. Místo toho podobnou
101 metodou uká¾eme trochu slab¹í výsledek s~iterovaným logaritmem:
102
103 \s{Vìta':} Ve~struktuøe s~$n$ prvky trvá provedení posloupnosti $m$~operací
104 \<Union> a \<Find> $\O((n+m)\cdot\log^* n)$.
105
106 \def\up{\mathop{\uparrow}}
107
108 \s{Definice:} {\I Vì¾ovou funkci} $2\up k$ definujeme následovnì: $2\up 0=1$,
109 $2\up (k+1)=2^{2\up k}$.
110
111 Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
112 k~této funkci inverzní.
113
114 Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù:
115 $k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
116 tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té
117 skupinì.
118
119 \s{Invariant~S:} V~$k$-té skupinì le¾í nejvý¹e $n/(2\up k)$ vrcholù.
120
121 \proof
122 Nejprve uká¾eme, ¾e vrcholù s~rankem~$r$ je nejvý¹e $n/2^r$. Kdybychom nekomprimovali
123 cesty, snadno to plyne z~invariantù~C a~R: ka¾dému vrcholu ranku~$r$ pøiøadíme v¹ech
124 jeho alespoò $2^r$ potomkù. Jeliko¾ ranky na cestách smìrem ke~koøeni rostou, ¾ádného
125 potomka jsme nemohli pøiøadit více vrcholùm. Komprese cest ov¹em nemù¾e invariant
126 poru¹it, proto¾e nemìní ranky ani rozhodnutí, jak probìhne který \<Union>.
127
128 Teï u¾ staèí odhad $n/2^r$ seèíst pøes v¹echny ranky ve~skupinì:
129 $$
130 {n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
131 {n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
132 {n \over 2^{2\up(k-1)}} \cdot 1 =
133 {n \over 2\up k}.
134 $$
135 \qed
136
137 \>{\sl Dùkaz vìty:}
138 Operace \<Union> a \<Find> potøebují nekonstantní èas pouze na~vystoupání
139 po~cestì ze~zadaného vrcholu~$v$ do~koøene stromu. Èas strávený na~této cestì
140 je pøímo úmìrný poètu hran cesty. Celá cesta je pøitom rozpojena a v¹echny
141 vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu.
142
143 Hrany cesty, které spojují vrcholy z~rùzných skupin (takových je $\O(\log^* n)$),
144 naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(m\log^*n)$.
145 Zbylé hrany budeme poèítat pøes celou dobu bìhu algoritmu a úètovat je vrcholùm.
146
147 Uva¾me vrchol~$v$ v~$k$-té skupinì, jeho¾ rodiè le¾í také v~$k$-té skupinì.
148 Jeliko¾ hrany na cestách do~koøene ostøe rostou, ka¾dým pøepojením vrcholu~$v$ rank jeho
149 rodièe vzroste. Proto po nejvý¹e $2\up k$ pøepojeních se bude rodiè vrcholu~$v$ nacházet
150 v~nìkteré z~vy¹¹ích skupin. Jeliko¾ rank vrcholu~$v$ se u¾ nikdy nezmìní, bude hrana z~$v$
151 do~jeho otce ji¾ nav¾dy hranou mezi skupinami. Ka¾dému vrcholu v~$k$-té skupinì tedy naúètujeme
152 nejvý¹e $2\up k$ pøepojení a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù,
153 naúètujeme celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$.
154 \qed
155
156 \h{Union-Find s~pøedem známými Uniony}
157
158 Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe
159 posloupnost Unionù, èili strom, který spojováním komponent vznikne.\foot{Kdy se to hodí?
160 Tøeba v~Thorupovì lineárním algoritmu \cite{thorup:usssp} na~nejkrat¹í cesty nebo
161 ve~Weiheho takté¾ lineárním algoritmu \cite{weihe:paths} na~hledání hranovì disjunktních
162 cest v~rovinných grafech.}
163 Jiná interpretace tého¾ (jen pozpátku) je dekrementální udr¾ování komponent
164 souvislosti lesa: na~poèátku je dán les, umíme smazat hranu a otestovat, zda jsou
165 dva vrcholy v~tém¾e stromu.
166
167 Popí¹eme algoritmus,
168 který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
169 konstantním èase. Tento algoritmus je kombinací dekompozic popsaných Alstrupem \cite{alstrup97optimal,alstrup98marked}.
170
171 \s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
172 definujeme:
173 \itemize\ibull
174 \:{\I Koøeny mikrostromù} budou nejvy¹¹í vrcholy v~$T$, pod~nimi¾ je nejvý¹e $\log n$ listù
175 a které nejsou koøenem celého~$T$.
176 \:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
177 \:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
178 \:{\I Makrostrom} je tvoøen zbývajícími vrcholy a hranami stromu~$T$.
179 \endlist
180
181 \s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
182 alespoò jeden mikrostrom (mù¾e jich být i více, viz dekompozice hvìzdy na~obrázku), tak¾e
183 listù makrostromu je nejvý¹e $n/\log n$.
184
185 Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
186 vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
187 ji nahradíme hranou, která bude vlo¾ena právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.
188
189 \s{Pøíklad:} Následující obrázek ukazuje dekompozici nìkolika stromù za~pøedpokladu,
190 ¾e $\log n=4$. Vrcholy mikrostromù jsou èerné, makrostromu bílé. Spojovací hrany kreslíme teèkovanì,
191 hrany komprimovaných cest tuènì.
192
193 \medskip
194 \fig{mima.eps}{\epsfxsize}
195
196 \s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si ulo¾íme
197 mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
198 odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
199 délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.
200
201 \>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):
202 \algo
203 \:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
204 \:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
205 \endalgo
206
207 \>$\<Find>(x,y):$
208 \algo
209 \:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
210   jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
211 \:Pokud jsou v~rùzných úsecích, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
212   na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
213 \endalgo
214
215 Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
216 amortizovanì, ale za~dobu ¾ivota struktury je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.
217
218 \s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím zpùsobem
219 pøevádìt na~operace s~jejich cestovì komprimovanými podobami a na~operace s~cestovými strukturami:
220
221 \>$\<Union>(x,y)$:
222 \algo
223 \:Pokud $e=xy$ le¾í uvnitø nìjaké cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
224   pøidávání jiné hrany, a~nebo u¾ jsme hotovi.
225 \:Provedeme \<Union> v~komprimovaném stromu.
226 \endalgo
227
228 \>$\<Find>(x,y)$:
229 \algo
230 \:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
231 \:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
232   ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
233   Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní;
234   pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
235   stromu spojeny hranou. Analogicky pro~$y$.
236 \:Zeptáme se struktury pro komprimovaný strom.
237 \endalgo
238
239 \s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
240 vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
241 mno¾inu hran pak mù¾eme reprezentovat $(2\log n)$-bitovým èíslem a mno¾inové operace
242 provádìt pomocí bitových v~konstantním èase.
243
244 Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
245 na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
246 pøítomných hran~$F$.
247
248 \>$\<Union>(x,y):$
249
250 \algo
251 \:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
252 \:$F \leftarrow F \cup \{i\}$.
253 \endalgo
254
255 \>$\<Find>(x,y):$
256
257 \algo
258 \:$P \leftarrow P_x \mathop{\Delta} P_y$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$).
259 \:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
260 \endalgo
261
262 \s{Algoritmus pro celý problém:} Strom rozlo¾íme na~mikrostromy, makrostrom a spojovací
263 hrany. V~mikrostromech i makrostromu zkomprimujeme cesty. Pro cesty a mikrostromy pou¾ijeme
264 vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
265 zda je pøítomna, a pro makrostrom pøebarvovací strukturu.
266
267 \>$\<Union>(x,y)$:
268
269 \algo
270 \:Pokud $e=xy$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
271 \:Nyní víme, ¾e $e$ le¾í uvnitø mikrostromu nebo makrostromu, a~tak provedeme \<Union>
272    na~pøíslu¹né struktuøe.
273 \endlist
274
275 \>$\<Find>(x,y)$:
276
277 \algo
278 \:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
279 \:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostruktury na~spojení s~koøenem mikrostromu.
280   Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
281   Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
282 \:Odpovíme podle struktury pro makrostrom.
283 \endalgo
284
285 \s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
286 v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
287 trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
288 hranami a cestami a $\O(n/\log n)$ operací s~makrostromem, které trvají $\O(\log n)$ amortizovanì
289 ka¾dá.%
290 \foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
291 struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
292 sluèování v~makrostromu.}
293
294 \s{Cvièení:} Zkuste pomocí dekompozice vyøe¹it následující problém: je dán strom,
295 jeho¾ ka¾dý vrchol mù¾e být oznaèený. Navrhnìte datovou strukturu, která bude umìt
296 v~èase $\O(\log\log n)$ oznaèit nebo odznaèit vrchol a v~èase $\O(\log n/\log\log n)$ najít
297 nejbli¾¹ího oznaèeného pøedchùdce.
298
299 \h{Fredericksonova clusterizace}
300
301 Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
302 se více hodí následující my¹lenka:
303
304 \s{Definice:} {\I (Fredericksonova clusterizace)} Nech» $k\ge 1$ je pøirozené èíslo
305 a $T$~strom s~maximálním stupnìm nejvý¹e~3. Pak $k$-clusterizací stromu~$T$
306 nazveme libovolný rozklad $V_1\cup\ldots\cup V_t$ mno¾iny~$V(T)$, pro který platí:
307 \itemize\ibull
308 \:Podgrafy stromu~$T$ indukované jednotlivými~$V_i$ jsou souvislé.
309 Tìmto podgrafùm budeme øíkat {\I clustery} a znaèit je~$C_i$.
310 \:Z~ka¾dého clusteru vedou nejvý¹e 3~hrany do sousedních clusterù.
311 Takovým hranám øíkáme {\I vnìj¹í,} jejich poèet je {\I vnìj¹í stupeò} clusteru $\<ed>(C_i)$.
312 Hrany uvnitø clusterù nazveme {\I vnitøní.}
313 \:Nech» $\vert C_i\vert$ znaèí poèet vrcholù clusteru~$C_i$.
314 Pak pro v¹echny clustery platí $\vert C_i\vert \le k$
315 a pro clustery vnìj¹ího stupnì~3 dokonce $\vert C_i\vert = 1$.
316 \:®ádné dva sousední clustery není mo¾né slouèit.
317 \endlist
318
319 \s{Úmluva:}
320 Clustery vnìj¹ího stupnì~0 se nazývají {\I izolované,}
321 stupnì~1 {\I listové,}
322 stupnì~2 {\I cestové} a
323 stupnì~3 {\I vìtvicí.}
324
325 \s{Pozorování:} Nech» $C$ a~$D$ jsou sousední clustery (bez újmy na obecnosti $\<ed>(C) \ge \<ed>(D)$).
326 Kdy je lze slouèit? Pøedev¹ím $\vert C\vert + \vert D\vert$ musí být nejvý¹e rovno~$k$. Pak mohou
327 nastat následující pøípady:
328 \itemize\ibull
329 \:Pokud~$C$ i~$D$ jsou listové, lze je slouèit do jednoho izolovaného clusteru.
330 \:Pokud~$C$ je cestový a $D$~listový, lze je slouèit do listového clusteru.
331 \:Pokud~$C$ i~$D$ jsou cestové, lze je slouèit do cestového clusteru.
332 \:Pokud~$C$ je vìtvicí a $D$~listový, lze je slouèit do cestového clusteru.
333 \:V~ostatních pøípadech sluèovat nelze, nebo» by vznikl cluster vnìj¹ího stupnì~4
334   nebo stupnì~3 s~více ne¾ jedním vrcholem.
335 \endlist
336
337 \s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Ka¾dá $k$-clusterizace stromu~$T$
338 na $n$~vrcholech obsahuje $\O(n/k)$ clusterù.
339
340 \proof
341 Pokud clusterizace obsahuje pouze izolované nebo listové clustery, pak je konstantnì
342 velká a tvrzení triviálnì platí.
343
344 Pokud navíc obsahuje cestové clustery, musí být clustery propojeny do jedné cesty,
345 která zaèíná a konèí listovými clustery a ostatní clustery jsou cestové. Cestové
346 clustery rozdìlíme na velké (alespoò $k/2$ vrcholù) a malé (ostatní). V¹imneme si,
347 ¾e malé spolu nemohou sousedit. Velkých je pøitom nejvý¹e $n/k$, tak¾e malých
348 nejvý¹e $n/k+1$.
349
350 Zbývá obecný pøípad, v~nìm¾ jsou i vìtvicí clustery. Uva¾me clusterizaèní strom~$S$:
351 jeho vrcholy odpovídají clusterùm, hrany externím hranám mezi nimi. Tento strom zakoøeòme
352 v~libovolném vìtvicím clusteru.
353
354 Pokud ve~stromu~$S$ nahradíme ka¾dou nevìtvící se cestu hranou, vznikne nìjaký
355 komprimovaný strom~$S'$. V~nìm u¾ jsou pouze listové clustery (coby listy) a
356 vìtvicí clustery (jako vnitøní vrcholy).
357
358 Nyní si v¹imneme, ¾e pro ka¾dý list~$\ell$ stromu~$S$ platí, ¾e tento cluster
359 spolu s~cestovými clustery nad ním (které se schovaly do hrany mezi~$\ell$ a jeho
360 otcem) musí mít velikost alespoò~$k$. V~opaèném pøípadì by toti¾ bylo mo¾né
361 tyto clustery spoleènì s~vìtvicím clusterem nad nimi slouèit do jediného clusteru,
362 co¾ by poru¹ilo poslední podmínku z~definice clusterizace.
363
364 Proto strom~$S'$ obsahuje nejvý¹e $n/k$ listù. A~jeliko¾ v¹echny jeho vnitøní
365 vrcholy mají alespoò~2 syny, musí být vnitøních vrcholù také nanejvý¹ $n/k$.
366
367 Zbývá zapoèítat cestové clustery. Uva¾me hranu~$e$ stromu~$S'$ a cestové clustery,
368 které se do ní zkomprimovaly. U¾ víme, ¾e je-li celková velikost tìchto clusterù~$r$,
369 mù¾e jich být nanejvý¹ $2r/k + 1$. A~jeliko¾ clustery jsou disjunktní, v~souètu
370 pøes v¹echny hrany~$e$ dostaneme $2n/k + \hbox{poèet hran stromu~$S'$} = \O(n/k)$.
371
372 Clusterù v¹ech typù je tedy dohromady $\O(n/k)$.
373 \qed
374
375 \s{Vìta:} (Frederickson \cite{frederickson91ambivalent}) Pro ka¾dé~$k$ lze $k$-clusterizaci
376 stromu o~$n$~vrcholech najít v~èase $\O(n)$.
377
378 \proof
379 Clusterizaci lze najít upraveným hledáním do hloubky, ale pøi tom je nutné øe¹it
380 mnoho rùzných pøípadù sluèování clusterù. Místo toho pou¾ijeme následující
381 hladový algoritmus.
382
383 Nejprve vytvoøíme z~ka¾dého vrcholu triviální cluster. Taková clusterizace
384 splòuje v¹echny podmínky kromì poslední. Budeme tedy clustery hladovì sluèovat.
385
386 Poøídíme si frontu clusterù, u~nich¾ jsme je¹tì nezkontrolovali sluèitelnost.
387 Na poèátku do ní umístíme v¹echny clustery. Pak v¾dy odebereme cluster, prozkoumáme
388 jeho sousedy a pokud mezi nimi je nìjaký, s~ním¾ lze sluèovat, tak to provedeme.
389 Nový cluster ulo¾íme do fronty, oba staré z~fronty odstraníme.
390
391 V¹imneme si, ¾e pøi ka¾dé kontrole poklesne velikost fronty o~1 -- buïto jsme
392 nesluèovali a zmizel pouze kontrolovaný cluster, anebo sluèovali, ale pak zmizely
393 dva clustery a pøibyl jeden. Jeliko¾ kontrolu i slouèení zvládneme v~konstantním
394 èase, celý algoritmus dobìhne v~èase $\O(n)$.
395 \qed
396
397 \s{Pou¾ití:} Pøedchozí variantu Union-Find problému bychom také mohli vyøe¹it nahrazením
398 vrcholù stupnì vìt¹ího ne¾~3 \uv{kruhovými objezdy bez jedné hrany},
399 nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
400 a pøebarvovací struktury na~hrany mezi clustery.
401
402 \h{Stromoví pøedchùdci}
403
404 \s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
405 tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
406 spoleèného pøedchùdce.
407
408 \s{Triviální øe¹ení LCA:}
409 \itemize\ibull
410 \:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
411   potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
412   pøedzpracování.
413 \:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
414   krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
415 \:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
416 \:\dots\ co dál?
417 \endlist
418
419 \>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.
420
421 \s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
422 $a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
423 \foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}
424
425 \s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
426 èasem na~pøevod dotazu.
427
428 \proof Strom projdeme do~hloubky a poka¾dé, kdy¾ vstoupíme do~vrcholu (a» ji¾ poprvé nebo se do~nìj vrátíme),
429 zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejvy¹¹í vrchol mezi libovolnou
430 náv¹tìvou~$x$ a libovolnou náv¹tìvou~$y$.
431 \qed
432
433 \s{Triviální øe¹ení RMQ:}
434 \itemize\ibull
435 \:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
436 \:Pro ka¾dé $i$ a $j\le \log n$ pøedpoèítáme $m_{ij} = \min\{ a_i, a_{i+1}, \ldots, a_{i+2^j-1} \}$,
437 èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
438 na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í~$k$ takové, ¾e $2^k < j-i$
439 a vrátíme:
440 $$\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} ).$$
441 Tak zvládneme dotazy v~èase $\O(1)$ po~pøedzpracování v~èase $\O(n\log n)$.
442 \endlist
443
444 My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
445 toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
446 øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.
447
448 \s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
449 ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásti blokù.
450
451 V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
452 a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
453 o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
454 blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
455 $\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.
456
457 Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
458 jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
459 týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
460 triviální struktury. To nás bude stát $\O(n/b\cdot\log (n/b))=\O(n/\log n\cdot\log n)=\O(n)$ na~pøedzpracování
461 a $\O(1)$ na~dotaz.
462
463 Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
464 pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
465 Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
466 i konstantní/lineární algoritmus pro obecné RMQ.
467
468 \s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
469 jeho¾ koøenem je minimum posloupnosti, tj. nìjaké $a_j=\min_i a_i$, jeho levý podstrom je
470 kartézský strom pro $a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.
471
472 \s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.
473
474 \proof Pou¾ijeme inkrementální algoritmus. V¾dy si budeme pamatovat
475 kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
476 prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
477 pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imnìme si, ¾e vzhledem
478 k~potenciálu rovnému hloubce oznaèeného prvku je èasová slo¾itost pøidání
479 prvku amortizovanì konstantní.
480 \qed
481
482 \s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
483 èasem na~pøevod dotazu.
484
485 \proof Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
486 \qed
487
488 Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:
489
490 \s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
491 po~pøedzpracování v~lineárním èase.
492
493 \s{Cvièení:} Vymyslete jednodu¹¹í strukturu pro RMQ, víte-li, ¾e v¹echny dotazy budou na~intervaly stejné délky.
494
495 \references
496 \bye