[ga.git] / 10-decomp / 10-decomp.tex

\input ../sgr.tex

\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}

V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených
na~my¹lence dekompozice problému na~dostateènì malé podproblémy,
které u¾ umíme (obvykle vhodným kódováním èísly) øe¹it v~konstantním
èase.

\h{Union-Find problem}

\s{Problém:} Udr¾ování tøíd ekvivalence: na~poèátku máme $N$ jednoprvkových ekvivalenèních
tøíd, provádíme operace \<Find> (zji¹tìní, zda dva prvky jsou ekvivalentní) a \<Union>
(slouèení dvou tøíd do~jedné). Také na~to lze pohlí¾et jako na~inkrementální udr¾ování
komponent souvislosti neorientovaného grafu: \<Union> je pøidání hrany, \<Find> test,
zda dva vrcholy le¾í v~té¾e komponentì. To se hodí v~mnoha algoritmech, kupøíkladu
v~Kruskalovì algoritmu pro hledání minimální kostry.

\s{Triviální øe¹ení:} Ka¾dé tøídì pøiøadíme unikátní barvu, kterou obarvíme prvky tøídy. Operace \<Find>
porovnává barvy, operace \<Union> prvky jedné tøídy pøebarvuje.

Operace \<Find> tak pracuje v~konstantním èase, \<Union> mù¾e zabrat a¾ lineární. Mù¾eme si
pomoci tím, ¾e v¾dy pøebarvíme {\I men¹í} ze~sluèovaných ekvivalenèních tøíd (budeme
si pro ka¾dou tøídu pamatovat seznam jejích prvkù a velikost). Tehdy mù¾e být ka¾dý
prvek pøebarven jen $\O(\log n)$-krát, jeliko¾ ka¾dým pøebarvením se alespoò zdvojnásobí
velikost tøídy, ve~které prvek le¾í. Posloupnost operací \<Union>, kterou vznikla tøída
velikosti~$k$, tak trvá $\O(k\log k)$, tak¾e mù¾eme bezpeènì prohlásit, ¾e amortizovaná
slo¾itost operace \<Union> je $\O(\log n)$.

\s{Chytøej¹í øe¹ení:} Ka¾dou tøídu budeme reprezentovat zakoøenìným stromem s~hranami
orientovanými smìrem ke~koøeni (jinými slovy pro ka¾dý prvek si pamatujeme jeho otce
nebo ¾e je to koøen). \<Find> nalezne koøeny stromù a porovná je, \<Union> pøipojí koøen
jedné tøídy pod koøen druhé. Aby stromy nedegenerovaly, pøidáme dvì podmínky:

\itemize\ibull
\:{\I Union by rank:} ka¾dý koøen $v$ si pamatuje svùj rank $r(v)$. Pokud spojujeme
dva stromy s~koøeny $v$, $w$ a $r(v)<r(w)$, pøipojíme $v$ pod~$w$ a rank zachováme.
Pokud $r(v)=r(w)$, pøipojíme libovolnì a nový koøen bude mít rank $r(v)+1$.%
\foot{Podobnì by fungovalo pravidlo {\I Union by size,} které pøipojuje men¹í
strom pod vìt¹í, ale ranky máme radìji, neb jsou skladnìj¹í a snáze se analyzují.}

\:{\I Path compression:} pokud z~vrcholu vystoupíme do~koøene (napøíklad
bìhem operace \<Find>), pøepojíme v¹echny vrcholy na~cestì, po~které jsme pro¹li,
rovnou pod koøen.
\endlist

\s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude
mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací
bude omezena $\O(\log n)$.%
\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}

\s{Vìta:} (Tarjan, van Leeuwen \cite{tarjan84setunion}) Kombinace Union by rank a Path compression vede k~amortizované
slo¾itosti obou operací $\O(\alpha(n))$, kde $\alpha$ je inverzní Ackermannova funkce.%
\foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím
pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.}

\h{Union-Find s~pøedem známými Uniony}

Dále nás bude zajímat speciální varianta Union-Find problemu, v~ní¾ dopøedu známe
posloupnost unionù, èili strom, který spojováním komponent vznikne. Popí¹eme algoritmus,
který po~poèáteèním pøedzpracování v~èase $\O(n)$ zvládne \<Union> i \<Find> v~amortizovanì
konstantním èase. Tento algoritmus je kombinací dekompozic popsaných v~\cite{alstrup97optimal}
a \cite{alstrup98marked}.

\s{Definice:} {\I (Microtree/Macrotree dekompozice)} Pro zakoøenìný strom $T$ o~$n$ vrcholech
definujeme:
\itemize\ibull
\:{\I Koøeny mikrostromù} $R$ budou nejvy¹¹í vrcholy, pod~nimi¾ je nejvý¹e $\log n$ listù.
\:{\I Mikrostromy} le¾í v~$T$ od~tìchto koøenù ní¾e.
\:{\I Spojovací hrany} vedou z~koøenù mikrostromù do~jejich otcù.
\:{\I Makrostrom} je tvoøen ostatními vrcholy a hranami stromu~$T$.
\endlist

\s{Pozorování:} Ka¾dý mikrostrom má nejvý¹e $\log n$ listù. Pod ka¾dým listem makrostromu le¾í
alespoò jeden mikrostrom\foot{Mù¾e jich být i více, pøedstavte si dekompozici hvìzdy.}, tak¾e
listù makrostromu je nejvý¹e $n/\log n$.

Vnitøních vrcholù makro- i mikrostromù ale mù¾e být ne¹ikovnì mnoho, proto¾e se ve~stromech mohou
vyskytovat dlouhé cesty. Pomù¾eme si snadno: ka¾dou cestu si budeme pamatovat zvlá¹» a ve~stromu
ji nahradíme hranou, která bude existovat právì tehdy, kdy¾ budou pøítomny v¹echny hrany cesty.

\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdìlíme na~úseky délky $\log n$, pro nì¾ si pamatujeme
mno¾iny ji¾ pøítomných hran (po~bitech jako èísla). Pak si je¹tì pamatujeme zkomprimovanou cestu (hrany
odpovídají úsekùm a jsou pøítomny právì tehdy, jsou-li pøítomny v¹echny hrany pøíslu¹ného úseku)
délky $l/\log n$ a pro ni \uv{pøebarvovací} strukturu pro Union-Find.

\>$\<Union>(x,y)$ (pøidání hrany $e=xy$ do~cesty):

\algo
\:Pøidáme $e$ do mno¾iny hran pøítomných v~pøíslu¹ném úseku.
\:Pokud se tím úsek naplnil, pøidáme odpovídající hranu do~zkomprimované cesty.
\endalgo

\>$\<Find>(x,y):$
\algo
\:Pokud $x$ a $y$ jsou v~tém¾e úseku, otestujeme bitovými operacemi, zda
  jsou v¹echny hrany mezi $x$ a $y$ pøítomny.
\:Pokud jsou v~rùzných, rozdìlíme cestu z~$x$ do~$y$ na~posloupnost celých úsekù,
  na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních èásteèných úsecích.
\endalgo

Operace uvnitø úsekù pracují v~èase $\O(1)$, operace na~zkomprimované cestì v~$\O(\log l)$
amortizovanì, ale je jich $\O(l/\log n)=\O(l/\log l)$, tak¾e celkovì zaberou lineární èas.

\s{Algoritmus pro mikrostromy:} Po~kompresi cest má ka¾dý mikrostrom nejvý¹e $2\log n$
vrcholù, èili také nejvý¹e tolik hran. Hrany si oèíslujeme pøirozenými èísly, ka¾dou
mno¾inu hran pak mù¾eme reprezentovat $2\log n$-bitovým èíslem a mno¾inové operace
provádìt pomocí bitových v~konstantním èase.

Pro ka¾dý mikrostrom si pøedpoèítáme pro v¹echny jeho vrcholy~$v$ mno¾iny~$P_v$ hran le¾ících
na~cestì z~koøene mikrostromu do~$v$. Navíc si budeme pro celý mikrostrom pamatovat mno¾inu
pøítomných hran~$F$.

\>$\<Union>(x,y):$

\algo
\:Najdeme poøadové èíslo $i$ hrany $xy$ (máme pøedpoèítané).
\:$F := F \cup \{i\}$.
\endalgo

\>$\<Find>(x,y):$

\algo
\:$P := P_x \mathop{\Delta} P_v$ (mno¾ina hran le¾ících na~cestì z~$x$ do~$y$)
\:Pokud $P\setminus F=\emptyset$, le¾í $x$ a $y$ ve~stejnì komponentì, jinak ne.
\endalgo

\s{Algoritmus pro celý problém:} Zkomprimujeme cesty a výsledný strom rozlo¾íme
na~mikrostromy, makrostromy a spojovací hrany. Pro cesty a mikrostromy pou¾ijeme
vý¹e popsané struktury, pro ka¾dou spojovací hranu si budeme pamatovat jen znaèku,
zda je pøítomna, a pro makrostrom pøebarvovací strukturu.

\>Operace $\<Union>(x,y)$:

\algo
\:Pokud $e=xy$ le¾í uvnitø cesty, pøidáme ji do~cesty, co¾ buïto zpùsobí
   pøidávání jiné hrany do~stromu, a~nebo u¾ jsme hotovi.
\:Pokud $e$ je spojovací, poznamenáme si, ¾e je pøítomna, a~konèíme.
\:Pokud $e$ le¾í uvnitø mikrostromu nebo makrostromu, provedeme \<Union>
   na~pøíslu¹né struktuøe.
\endlist

\>Operace $\<Find>(x,y)$:

\algo
\:Pokud $x$ a $y$ le¾í uvnitø jedné cesty, zeptáme se cestové struktury a konèíme.
\:Pokud $x$ le¾í uvnitø nìjaké cesty, zjistíme dotazem na~cestovou strukturu,
   ke~kterému krajnímu vrcholu cesty je pøipojen, a~$x$ nahradíme tímto vrcholem.
   Není-li pøipojen k~¾ádnému, je~evidentnì odpovìï na~celý \<Find> negativní,
   pokud k~obìma, vybereme si libovolný, proto¾e jsou stejnì v~cestovì komprimovaném
   stromu spojeny hranou. Analogicky pro~$y$.
\:[Nyní jsou $x$ a $y$ vrcholy cestovì zkomprimovaného stromu.]
\:Le¾í-li $x$ a $y$ v~jednom mikrostromu, zeptáme se struktury pro~mikrostrom.
\:Je-li $x$ uvnitø mikrostromu, zeptáme se mikrostromové struktury na~spojení s~koøenem mikrostromu.
  Není-li, odpovíme {\sc ne}, stejnì jako kdy¾ není pøítomna pøíslu¹ná spojovací hrana.
  Jinak $x$ nahradíme listem makrostromu, do~kterého spojovací hrana vede. Podobnì pro~$y$.
\:[Nyní jsou $x$ a $y$ vrcholy makrostromu.]
\:Odpovíme podle struktury pro makrostrom.
\endalgo

\s{Analýza:} Operace s~mikrostromy, spojovacími hranami a cestami jsou, jak u¾ víme,
amortizovanì konstantní. Operace s~makrostromy také, jeliko¾ trvají $\O(\log n)$,
ale provede se jich pouze $\O(n/\log n)$. Ka¾dou operaci \<Union> nebo \<Find>
rozlo¾íme $\O(1)$ tìchto dílèích operací, tak¾e bude také trvat $\O(1)$ amortizovanì.

\h{Fredericksonova clusterizace}

Mikro/makro-stromová dekompozice není jediný zpùsob, jak stromy rozkládat. Nìkdy
se hodí napøíklad následující my¹lenka: \cite{frederickson91ambivalent}

\s{Definice:} (Fredericksonova clusterizace) Nech» $G$ je graf s~vrcholy stupòù nejvý¹e~3
a $c\ge 1$. Pak $c$-clusterizací grafu $G$ nazveme libovolný rozklad
$G$ na~souvislé podgrafy (clustery) $G_1, G_2, \ldots, G_k$ takový, ¾e platí:
\itemize\ibull
\:$\forall v \in V \exists ! i: v \in C_i$.
\:$\forall i: \vert C_i\vert \le c$.
\:$\forall i$ je vnìj¹í stupeò $C_i$ (tj. poèet hran, které vedou mezi $C_i$ a zbytkem grafu)
nejvý¹e~3. Navíc pokud je právì~3, je cluster triviální, èili $\vert C_i \vert = 1$.
\:®ádné dva sousední clustery nelze spojit.
\endlist

\s{Vìta:} (Frederickson) Ka¾dá $c$-clusterizace grafu $G$ má $\O(V(G)/c)$ clusterù. Existuje
algoritmus, který jednu takovou najde v~lineárním èase.

\s{Dùkaz:} První èast rozborem pøípadù, druhá hladovì pomocí DFS. \qed

\s{Pou¾ití:} Pøedchozí variantu Union-Find problemu bychom také mohli vyøe¹it nahrazením
vrcholù stupnì $>3$ \uv{kruhovými objezdy bez jedné hrany}\foot{tzv. francouzský trik},
nalezením $(\log n)$-clusterizace, pou¾itím bitové reprezentace mno¾in uvnitø clusterù
a pøebarvovací struktury na~hrany mezi clustery.

\h{Stromoví pøedchùdci}

\s{Problém:} {\I (Least Common Ancestor alias LCA)} Chceme si pøedzpracovat zakoøenìný strom~$T$
tak, abychom dokázali pro libovolné dva vrcholy $x,y$ najít co~nejrychleji jejich nejbli¾¹ího
spoleèného pøedchùdce.

\s{Triviální øe¹ení LCA:}
\itemize\ibull
\:Vystoupáme z~$x$ i $y$ do~koøene, oznaèíme vrcholy na~cestách a kde se poprvé
  potkají, tam je hledaný pøedchùdce. To je lineární s~hloubkou a nepotøebuje
  pøedzpracování.
\:Vylep¹ení: Budeme stoupat z~$x$ a $y$ støídavì. Tak potøebujeme jen lineárnì mnoho
  krokù vzhledem ke~vzdálenosti spoleèného pøedchùdce.
\:Pøedpoèítáme v¹echny mo¾nosti: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
\:\dots\ co dál?
\endlist

\>Vìrni vtipùm o~matfyzácích a èlánku \cite{bender00lca} pøevedeme radìji tento problém na~jiný.

\s{Problém:} {\I (Range Minimum Query alias RMQ)} Chceme pøedzpracovat posloupnost èísel
$a_1,\ldots a_n$ tak, abychom umìli rychle poèítat $\min_{x\le i\le y} a_i$.%
\foot{V¹imnìte si, ¾e pro sumu místo minima je tento problém velmi snadný.}

\s{Lemma:} LCA lze pøevést na~RMQ s~lineárním èasem na~pøedzpracování a konstantním
èasem na~pøevod dotazu.

\s{Dùkaz:} Strom projdeme do~hloubky a poka¾dé, kdy¾ nav¹tívíme vrchol (v~inorderu),
zapí¹eme jeho hloubku. ${\rm LCA}(x,y)$ pak bude nejhlub¹í vrchol mezi poslední
náv¹tìvou~$x$ a první náv¹tìvou~$y$, nebo opaènì.
\qed

\s{Triviální øe¹ení RMQ:}
\itemize\ibull
\:Pøedpoèítáme v¹echny mo¾né dotazy: pøedzpracování $\O(n^2)$, dotaz $\O(1)$.
\: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} \}$,
èili minima v¹ech blokù velkých jako nìjaká mocnina dvojky. Kdy¾ se poté nìkdo zeptá
na~minimum bloku $a_i,a_{i+1},\ldots,a_{j-1}$, najdeme nejvìt¹í $k$ takové, ¾e $2^k < j-i$
a vrátíme $\min( \min\{ a_i, \ldots, a_{i+2^k-1} \}, \min\{ a_{j-2^k}, \ldots, a_{j-1} \} )$.
Tak zvládneme dotaz v~èase $\O(1)$ za~cenu pøedzpracování v~èase $\O(n\log n)$.
\endlist

My si ov¹em v¹imneme, ¾e ná¹ pøevod z~LCA vytváøí dosti speciální instance problému RMQ,
toti¾ takové, v~nich¾ je $\vert a_i - a_{i+1} \vert = 1$. Takovým instancím budeme
øíkat RMQ${\pm}1$ a budeme je umìt øe¹it ¹ikovnou dekompozicí.

\s{Dekompozice} pro RMQ${\pm}1$: Vstupní posloupnost rozdìlíme na~bloky velikosti $b=1/2\cdot \log n$,
ka¾dý dotaz umíme rozdìlit na~èást týkající se celých blokù a maximálnì dva dotazy na~èásteèné bloky.

V¹imneme si, ¾e aèkoliv blokù je mnoho, jejich mo¾ných typù (tj. posloupností klesání
a stoupání) je pouze $2^{b-1}\le\sqrt n$ a bloky tého¾ typu se li¹í pouze posunutím
o~konstantu. Vybudujeme proto kvadratickou strukturu pro jednotlivé typy a pro ka¾dý
blok si zapamatujeme, jakého je typu a jaké má posunutí. Celkem strávíme èas
$\O(n + \sqrt n \cdot \log^2 n) = \O(n)$ pøedzpracováním a $\O(1)$ dotazem.

Mimo to je¹tì vytvoøíme komprimovanou posloupnost, v~ní¾ ka¾dý blok nahradíme
jeho minimem. Tuto posloupnost délky $n/b$ budeme pou¾ívat pro èásti dotazù
týkající se celých blokù a pøipravíme si pro ni \uv{logaritmickou} variantu
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í
a $\O(1)$ na~dotaz.

Tak jsme získali algoritmus pro RMQ${\pm}1$ s~konstantním èasem na~dotaz po~lineárním
pøedzpracování a vý¹e zmínìným pøevodem i algoritmus na~LCA se stejnými parametry.
Je¹tì uká¾eme, ¾e pøevod mù¾e fungovat i v~opaèném smìru, a~tak mù¾eme získat
i konstantní/lineární algoritmus pro obecné RMQ.

\s{Definice:} {\I Kartézský strom} pro posloupnost $a_1,\ldots,a_n$ je strom,
jeho¾ koøenem je $a_j=\min_i a_i$, jeho levý podstrom je kartézský strom pro
$a_1,\ldots,a_{j-1}$ a pravý podstrom kartézský strom pro $a_{j+1},\ldots,a_n$.

\s{Lemma:} Kartézský strom je mo¾né zkonstruovat v~lineárním èase.

\s{Dùkaz:} Pou¾ijeme inkrementální algoritmus, v¾dy si budeme pamatovat
kartézský strom pro ji¾ zpracované prvky a pozici posledního zpracovaného
prvku v~tomto stromu. Kdy¾ pøidáváme dal¹í prvek, hledáme místo, kam ho
pøipojit, od~tohoto oznaèeného prvku nahoru. Pov¹imneme si, ¾e vzhledem
k~potenciálu urèenému hloubkou oznaèeného prvku je èasová slo¾itost pøidání
prvku amortizovanì konstantní.
\qed

\s{Lemma:} RMQ lze pøevést na~LCA s~lineárním èasem na~pøedzpracování a konstantním
èasem na~pøevod dotazu.

\s{Dùkaz:} Sestrojíme kartézský strom a RMQ pøevedeme na~LCA v~tomto stromu.
\qed

Výsledky této podkapitoly mù¾eme shrnout do~následující vìty:

\s{Vìta:} Problémy LCA i RMQ je mo¾né øe¹it v~konstantním èase na~dotaz
po~pøedzpracování v~lineárním èase.

\references
\bye