\input ../sgr.tex
-\prednaska{12}{Pravdìpodobnostní algoritmus na øezy}{}
+\prednaska{12}{Pravděpodobnostní algoritmus na řezy}{}
-Nahlédnìme alespoò jednou kapitolou do~svìta pravdìpodobnostních algoritmù.
-Není toti¾ výjimkou, ¾e s~pomocí generátoru náhodných èísel vyøe¹íme nìkteré
-grafové problémy daleko snáze a èasto také efektivnìji, ne¾ to dovedeme deterministicky.
-Pravdìpodobnostní pøístup si pøedvedeme na~Kargerovì-Steinovì algoritmu \cite{karger:mincut}
-pro hledání minimálního øezu v~neohodnoceném neorientovaném grafu. Pøipomeòme,
-¾e s~deterministickými algoritmy jsme zatím dosáhli èasové slo¾itosti $\O(n^{5/3}m)$
-pomocí tokù nebo $\O(nm)$ Nagamochiho-Ibarakiho algoritmem.
+Nahlédněme alespoň jednou kapitolou do~světa pravděpodobnostních algoritmů.
+Není totiž výjimkou, že s~pomocí generátoru náhodných čísel vyřešíme některé
+grafové problémy daleko snáze a Ä\8dasto také efektivnÄ\9bji, než to dovedeme deterministicky.
+Pravděpodobnostní přístup si předvedeme na~Kargerově-Steinově algoritmu \cite{karger:mincut}
+pro hledání minimálního řezu v~neohodnoceném neorientovaném grafu. Připomeňme,
+že s~deterministickými algoritmy jsme zatÃm dosáhli Ä\8dasové složitosti $\O(n^{5/3}m)$
+pomocí toků nebo $\O(nm)$ Nagamochiho-Ibarakiho algoritmem.
-\h{Náhodné kontrakce}
+\h{Náhodné kontrakce}
-Uva¾ujme nejdøíve následující algoritmus, který náhodnì vybírá
-hrany a kontrahuje je, dokud poèet vrcholù neklesne na~danou hodnotu~$\ell$.
+Uvažujme nejdříve následující algoritmus, který náhodně vybírá
+hrany a kontrahuje je, dokud počet vrcholů neklesne na~danou hodnotu~$\ell$.
\s{Algoritmus} $\hbox{\sc Contract}(G_0,\ell)$:
\algo
\:$G \leftarrow G_0$.
\:Dokud $n>\ell$:
-\::Vybereme hranu $e\in E$ rovnomìrnì náhodnì.
-\::$G \leftarrow G/e$ (kontrahujeme hranu~$e$, smyèky odstraòujeme,
- paralelní hrany ponecháme).
-\:Vrátíme jako výsledek graf~$G$.
+\::Vybereme hranu $e\in E$ rovnoměrně náhodně.
+\::$G \leftarrow G/e$ (kontrahujeme hranu~$e$, smyčky odstraňujeme,
+ paralelní hrany ponecháme).
+\:Vrátíme jako výsledek graf~$G$.
\endalgo
-Jaká je pravdìpodobnost, ¾e výsledný graf~$G$ má stejnì velký minimální øez
-jako zadaný graf~$G_0$? V¹imnìme si nejprve, ¾e ka¾dý øez v~grafu $G/e$ je i øezem
-v~grafu~$G$ (a¾ na pøeznaèení hran pøi kontrakci, ale pøedpokládejme, ¾e hrany
-mají nìjaké identifikátory, které kontrakce zachovává). Podobnì je-li v~grafu~$G$
-øez neobsahující hranu~$e$, odpovídá mu stejnì velký øez v~$G/e$. Velikost
-minimálního øezu tedy kontrakcí nikdy neklesne -- mù¾e pouze stoupnout, pokud
-skontrahujeme hranu le¾ící ve~v¹ech minimálních øezech,
-
-Zvolíme nyní pevnì jeden z~minimálních øezù~$C$ v~zadaném grafu~$G_0$ a oznaèíme~$k$ jeho
-velikost. Pokud algoritmus ani jednou nevybere hranu le¾ící v~tomto øezu, velikost
-minimálního øezu v~grafu~$G$ bude rovnì¾ rovna~$k$. Jaká je pravdìpodobnost, ¾e
+Jaká je pravděpodobnost, že výsledný graf~$G$ má stejně velký minimální řez
+jako zadaný graf~$G_0$? Všimněme si nejprve, že každý řez v~grafu $G/e$ je i řezem
+v~grafu~$G$ (až na pÅ\99eznaÄ\8denà hran pÅ\99i kontrakci, ale pÅ\99edpokládejme, že hrany
+mají nějaké identifikátory, které kontrakce zachovává). Podobně je-li v~grafu~$G$
+řez neobsahující hranu~$e$, odpovídá mu stejně velký řez v~$G/e$. Velikost
+minimálnÃho Å\99ezu tedy kontrakcà nikdy neklesne -- může pouze stoupnout, pokud
+skontrahujeme hranu ležící ve~všech minimálních řezech,
+
+Zvolíme nyní pevně jeden z~minimálních řezů~$C$ v~zadaném grafu~$G_0$ a označíme~$k$ jeho
+velikost. Pokud algoritmus ani jednou nevybere hranu ležící v~tomto řezu, velikost
+minimálnÃho Å\99ezu v~grafu~$G$ bude rovnÄ\9bž rovna~$k$. Jaká je pravdÄ\9bpodobnost, že
se tak stane?
-Oznaème $G_i$ stav grafu~$G$ pøed $i$-tým prùchodem cyklem a $n_i$ a $m_i$ poèet jeho
-vrcholù a hran. Zøejmì $n_i=n-i+1$ (ka¾dou kontrakcí pøijdeme o~jeden vrchol).
-Navíc ka¾dý vrchol má stupeò alespoò~$k$, jeliko¾ jinak by triviální øez okolo
-tohoto vrcholu byl men¹í ne¾ minimální øez. Proto platí $m_i \ge kn_i/2$. Hranu
-le¾ící v~øezu~$C$ tedy vybereme s~pravdìpodobností nejvý¹e $k/m_i \le k/(kn_i/2) = 2/n_i
-= 2/(n-i+1)$. V¹echny hrany z~øezu~$C$ proto postoupí do výsledného grafu~$G$
-s~pravdìpodobností
+Označme $G_i$ stav grafu~$G$ před $i$-tým průchodem cyklem a $n_i$ a $m_i$ počet jeho
+vrcholů a hran. Zřejmě $n_i=n-i+1$ (každou kontrakcí přijdeme o~jeden vrchol).
+Navíc každý vrchol má stupeň alespoň~$k$, jelikož jinak by triviální řez okolo
+tohoto vrcholu byl menší než minimální řez. Proto platí $m_i \ge kn_i/2$. Hranu
+ležící v~řezu~$C$ tedy vybereme s~pravděpodobností nejvýše $k/m_i \le k/(kn_i/2) = 2/n_i
+= 2/(n-i+1)$. Všechny hrany z~řezu~$C$ proto postoupí do výsledného grafu~$G$
+s~pravděpodobností
$$\eqalign{
p &\ge \prod_{i=1}^{n-\ell} \left( 1 - {2\over n-i+1} \right)
= \prod_{i=1}^{n-\ell} {n-i-1 \over n-i+1} = \cr
= {\ell\cdot(\ell-1) \over n\cdot(n-1)}. \cr
}$$
-Mù¾eme tedy zvolit pevnì~$\ell$, spustit na~zadaný graf proceduru {\sc Contract}
-a ve~vzniklém konstantnì velkém grafu pak nalézt minimální øez hrubou silou
-(to je obzvlá¹tì snadné pro $\ell=2$ -- tehdy staèí vzít v¹echny zbylé hrany).
-Takový algoritmus nalezne minimální øez s~pravdìpodobností alespoò $c/n^2$,
-kde~$c$ je konstanta závislá na~$\ell$.
-
-Nabízí se otázka, k~èemu je dobrý algoritmus, který vydá správný výsledek
-s~pravdìpodobností na~øádu $1/n^2$. To opravdu není mnoho, ale stejnì jako
-mnoho jiných randomizovaných algoritmù i tento mù¾eme iterovat: výpoèet
-zopakujeme $K$-krát a pou¾ijeme nejmen¹í z~nalezených øezù. Ten u¾ bude
-minimální s~pravdìpodobností
+Můžeme tedy zvolit pevně~$\ell$, spustit na~zadaný graf proceduru {\sc Contract}
+a ve~vzniklém konstantně velkém grafu pak nalézt minimální řez hrubou silou
+(to je obzvláště snadné pro $\ell=2$ -- tehdy stačí vzít všechny zbylé hrany).
+Takový algoritmus nalezne minimální řez s~pravděpodobností alespoň $c/n^2$,
+kde~$c$ je konstanta závislá na~$\ell$.
+
+Nabízí se otázka, k~čemu je dobrý algoritmus, který vydá správný výsledek
+s~pravděpodobností na~řádu $1/n^2$. To opravdu není mnoho, ale stejně jako
+mnoho jiných randomizovaných algoritmů i tento můžeme iterovat: výpočet
+zopakujeme $K$-krát a použijeme nejmenÅ¡Ã z~nalezených Å\99ezů. Ten už bude
+minimální s~pravděpodobností
$$
P_K \ge 1 - (1-c/n^2)^K \ge 1 - e^{-cK/n^2}.
$$
-(Druhá nerovnost platí díky tomu, ¾e $e^{-x} \ge 1-x$ pro v¹echna $x\ge 0$.)
-Pokud tedy nastavíme poèet opakování~$K$ na $\Omega(n^2)$, mù¾eme tím pravdìpodobnost
-chyby stlaèit pod libovolnou konstantu, pro $K=\Omega(n^2\log n)$ pod pøevrácenou
-hodnotu libovolného polynomu v~$n$ a pro $K=\Omega(n^3)$ u¾ bude dokonce exponenciálnì malá.
+(Druhá nerovnost platí díky tomu, že $e^{-x} \ge 1-x$ pro všechna $x\ge 0$.)
+Pokud tedy nastavíme počet opakování~$K$ na $\Omega(n^2)$, můžeme tím pravděpodobnost
+chyby stlačit pod libovolnou konstantu, pro $K=\Omega(n^2\log n)$ pod převrácenou
+hodnotu libovolného polynomu v~$n$ a pro $K=\Omega(n^3)$ už bude dokonce exponenciálně malá.
\h{Implementace}
-Odboème na chvíli k~implementaèním zále¾itostem. Jak reprezentovat graf, abychom
-stihli rychle provádìt kontrakce? Bude nám staèit obyèejná matice sousednosti,
-v~ní¾ pro ka¾dou dvojici vrcholù budeme udr¾ovat, kolik paralelních hran mezi tìmito vrcholy
-vede. Pokud chceme kontrahovat hranu~$uv$, staèí projít v¹echny hrany vedoucí
-(øeknìme) z~vrcholu~$u$ a zaøadit je k~vrcholu~$v$. To zvládneme v~èase $\O(n)$
+OdboÄ\8dme na chvÃli k~implementaÄ\8dnÃm záležitostem. Jak reprezentovat graf, abychom
+stihli rychle provádět kontrakce? Bude nám stačit obyčejná matice sousednosti,
+v~níž pro každou dvojici vrcholů budeme udržovat, kolik paralelních hran mezi těmito vrcholy
+vede. Pokud chceme kontrahovat hranu~$uv$, stačí projít všechny hrany vedoucí
+(řekněme) z~vrcholu~$u$ a zařadit je k~vrcholu~$v$. To zvládneme v~čase $\O(n)$
na jednu kontrakci.
-Pro náhodný výbìr hrany budeme udr¾ovat pole stupòù vrcholù, vybereme náhodnì
-vrchol~$v$ s~pravdìpodobností úmìrnou stupni a poté projitím pøíslu¹ného øádku
-matice sousednosti druhý vrchol~$v$ s~pravdìpodobností úmìrnou poètu hran
-mezi $u$ a~$v$. To opìt trvá èas $\O(n)$.
+Pro náhodný výběr hrany budeme udržovat pole stupňů vrcholů, vybereme náhodně
+vrchol~$v$ s~pravděpodobností úměrnou stupni a poté projitím příslušného řádku
+matice sousednosti druhý vrchol~$v$ s~pravděpodobností úměrnou počtu hran
+mezi $u$ a~$v$. To opět trvá čas $\O(n)$.
-Procedura {\sc Contract} tedy pracuje v~èase $\O((n-\ell)\cdot n)$ a celý
-$K$-krát ziterovaný algoritmus v~$\O(Kn^2)$. Pokud se spokojíme s~pøevrácenì
-polynomiální pravdìpodobností chyby, nalezneme minimální øez v~èase $\O(n^4\log n)$.
+Procedura {\sc Contract} tedy pracuje v~čase $\O((n-\ell)\cdot n)$ a celý
+$K$-krát ziterovaný algoritmus v~$\O(Kn^2)$. Pokud se spokojíme s~převráceně
+polynomiální pravděpodobností chyby, nalezneme minimální řez v~čase $\O(n^4\log n)$.
-\h{Kargerùv-Steinùv algoritmus}
+\h{Kargerův-Steinův algoritmus}
-Pøedchozí prostinký algoritmus mù¾eme je¹tì podstatnì vylep¹it.
-V¹imnìme si, ¾e bìhem kontrahování hran pravdìpodobnost toho, ¾e vybereme \uv{¹patnou}
-hranu le¾ící v~minimálním øezu, postupnì rostla z~poèáteèních $2/n$ a¾ po obrovské
-$2/3$ v~poslední iteraci (pro $\ell=2$). Pomù¾e tedy zastavit kontrahování døíve
-a~pøejít na~spolehlivìj¹í zpùsob hledání øezu.
+Předchozí prostinký algoritmus můžeme ještě podstatně vylepšit.
+Všimněme si, že během kontrahování hran pravděpodobnost toho, že vybereme \uv{špatnou}
+hranu ležící v~minimálním řezu, postupně rostla z~počátečních $2/n$ až po obrovské
+$2/3$ v~poslední iteraci (pro $\ell=2$). Pomůže tedy zastavit kontrahování dříve
+a~přejít na~spolehlivější způsob hledání řezu.
-Pokud zvolíme $\ell=\lceil n/\sqrt2 +1\rceil$, pak øez~$C$ pøe¾ije kontrahování
-s~pravdìpodobností alespoò
+Pokud zvolíme $\ell=\lceil n/\sqrt2 +1\rceil$, pak řez~$C$ přežije kontrahování
+s~pravděpodobností alespoň
$$
{\ell\cdot (\ell-1) \over n\cdot (n-1)}
\ge {(n/\sqrt2+1)\cdot n/\sqrt2 \over n\cdot (n-1)}
\ge {1\over 2}.
$$
-Jako onen spolehlivìj¹í zpùsob hledání øezu následnì zavoláme stejný algoritmus
-rekurzivnì, pøièem¾ jak kontrakci, tak rekurzi provedeme dvakrát a z~obou
-nalezených øezù vybereme ten men¹í, èím¾ pravdìpodobnost chyby sní¾íme.
+Jako onen spolehlivější způsob hledání řezu následně zavoláme stejný algoritmus
+rekurzivně, přičemž jak kontrakci, tak rekurzi provedeme dvakrát a z~obou
+nalezených řezů vybereme ten menší, čímž pravděpodobnost chyby snížíme.
-Hotový algoritmus bude vypadat následovnì:
+Hotový algoritmus bude vypadat následovně:
\s{Algoritmus} $\hbox{\sc MinCut}(G)$:
\algo
-\:Pokud $n<7$, najdeme minimální øez hrubou silou.
-\:$\ell\leftarrow \lceil n/\sqrt 2 + 1 \rceil$.\foot{To je ménì ne¾~$n$, kdykoliv $n\ge 7$.}
+\:Pokud $n<7$, najdeme minimální řez hrubou silou.
+\:$\ell\leftarrow \lceil n/\sqrt 2 + 1 \rceil$.\foot{To je ménÄ\9b než~$n$, kdykoliv $n\ge 7$.}
\:$C_1 \leftarrow \hbox{\sc MinCut}(\hbox{\sc Contract}(G,\ell))$.
\:$C_2 \leftarrow \hbox{\sc MinCut}(\hbox{\sc Contract}(G,\ell))$.
-\:Vrátíme men¹í z~øezù $C_1$, $C_2$.
+\:Vrátíme menší z~řezů $C_1$, $C_2$.
\endalgo
-Jakou bude mít tento algoritmus èasovou slo¾itost? Nejprve odhadnìme hloubku
-rekurze: v~ka¾dém kroku se velikost vstupu zmen¹í pøibli¾nì $\sqrt 2$-krát, tak¾e strom
-rekurze bude mít hloubku $\O(\log n)$. Na~$i$-té hladinì zpracováváme $2^i$
-podproblémù velikosti $n/2^{i/2}$. Pøi výpoètu ka¾dého podproblému voláme
-dvakrát proceduru {\sc Contract}, která spotøebuje èas $\O((n/2^{i/2})^2)
-= \O(n^2/2^i)$. Souèet pøes celou hladinu tedy èiní $\O(n^2)$ a pøes v¹echny
-hladiny $\O(n^2\log n)$. Oproti pùvodnímu kontrakènímu algoritmu jsme si tedy
-moc nepohor¹ili.
-
-Zbývá spoèítat, s~jakou pravdìpodobností algoritmus skuteènì nalezne minimální øez.
-Oznaème $p_i$ pravdìpodobnost, ¾e algoritmus na~$i$-té hladinì stromu
-rekurze (poèítáno od~nejhlub¹í, nulté hladiny) vydá správný výsledek
-pøíslu¹ného podproblému. Jistì je $p_0=1$ a platí rekurence
-$p_i \ge 1 - (1 - 1/2 \cdot p_{i-1})^2$. Uva¾ujme posloupnost $g_i$, pro kterou
-jsou tyto nerovnosti splnìny jako rovnosti, a~v¹imnìme si, ¾e $p_i\ge g_i$.
-Víme tedy, ¾e $g_0=1$ a $g_i = 1-(1-1/2\cdot g_{i-1})^2 = g_{i-1} - g_{i-1}^2/4$.
-
-Nyní zavedeme substituci $z_i = 4/g_i - 1$, èili $g_i=4/(z_i+1)$, a~tak získáme
+Jakou bude mít tento algoritmus časovou složitost? Nejprve odhadněme hloubku
+rekurze: v~každém kroku se velikost vstupu zmenÅ¡Ã pÅ\99ibližnÄ\9b $\sqrt 2$-krát, takže strom
+rekurze bude mít hloubku $\O(\log n)$. Na~$i$-té hladině zpracováváme $2^i$
+podproblémů velikosti $n/2^{i/2}$. Při výpočtu každého podproblému voláme
+dvakrát proceduru {\sc Contract}, která spotřebuje čas $\O((n/2^{i/2})^2)
+= \O(n^2/2^i)$. Součet přes celou hladinu tedy činí $\O(n^2)$ a přes všechny
+hladiny $\O(n^2\log n)$. Oproti původnímu kontrakčnímu algoritmu jsme si tedy
+moc nepohoršili.
+
+Zbývá spočítat, s~jakou pravděpodobností algoritmus skutečně nalezne minimální řez.
+Označme $p_i$ pravděpodobnost, že algoritmus na~$i$-té hladině stromu
+rekurze (počítáno od~nejhlubší, nulté hladiny) vydá správný výsledek
+příslušného podproblému. Jistě je $p_0=1$ a platí rekurence
+$p_i \ge 1 - (1 - 1/2 \cdot p_{i-1})^2$. Uvažujme posloupnost $g_i$, pro kterou
+jsou tyto nerovnosti splnÄ\9bny jako rovnosti, a~vÅ¡imnÄ\9bme si, že $p_i\ge g_i$.
+VÃme tedy, že $g_0=1$ a $g_i = 1-(1-1/2\cdot g_{i-1})^2 = g_{i-1} - g_{i-1}^2/4$.
+
+Nyní zavedeme substituci $z_i = 4/g_i - 1$, čili $g_i=4/(z_i+1)$, a~tak získáme
novou rekurenci pro~$z_i$:
$$
{4 \over z_i+1} = {4\over z_{i-1}+1} - {4\over (z_{i-1}+1)^2},
$$
-kterou u¾ mù¾eme snadno upravovat:
+kterou už můžeme snadno upravovat:
$$\eqalign{
{1\over z_i+1} &= {z_{i-1} \over (z_{i-1}+1)^2}, \cr
z_i+1 &= {z_{i-1}^2 + 2z_{i-1} + 1 \over z_{i-1}}, \cr
z_i+1 &= z_{i-1} + 2 + {1\over z_{i-1}}. \cr
}$$
-Jeliko¾ $z_0=3$, a~tím pádem $z_i\ge 3$ pro v¹echna~$i$, získáme z~poslední
-rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudí¾ $z_i \le 2i+3$.
-Zpìtnou substitucí obdr¾íme $g_i \ge 4/(2i+4)$, tedy $p_i \ge g_i = \Omega(1/i)$.
+Jelikož $z_0=3$, a~tím pádem $z_i\ge 3$ pro všechna~$i$, získáme z~poslední
+rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudÞ $z_i \le 2i+3$.
+Zpětnou substitucí obdržíme $g_i \ge 4/(2i+4)$, tedy $p_i \ge g_i = \Omega(1/i)$.
-Nyní si staèí vzpomenout, ¾e hloubka rekurze èiní $\O(\log n)$, a ihned získáme
-odhad pro pravdìpodobnost správného výsledku $\Omega(1/\log n)$. Ná¹ algoritmus
-tedy staèí ziterovat $\O(\log^2 n)$-krát, abychom pravdìpodobnost chyby stlaèili
-pod pøevrácenou hodnotu polynomu. Dokázali jsme následující vìtu:
+Nyní si stačí vzpomenout, že hloubka rekurze činí $\O(\log n)$, a ihned získáme
+odhad pro pravděpodobnost správného výsledku $\Omega(1/\log n)$. Náš algoritmus
+tedy stačí ziterovat $\O(\log^2 n)$-krát, abychom pravděpodobnost chyby stlačili
+pod převrácenou hodnotu polynomu. Dokázali jsme následující větu:
-\s{Vìta:} Iterováním algoritmu {\sc MinCut} nalezneme minimální øez v~neohodnoceném
-neorientovaném grafu v~èase $\O(n^2\log^3 n)$ s~pravdìpodobností chyby $\O(1/n^c)$
+\s{Věta:} Iterováním algoritmu {\sc MinCut} nalezneme minimální řez v~neohodnoceném
+neorientovaném grafu v~čase $\O(n^2\log^3 n)$ s~pravděpodobností chyby $\O(1/n^c)$
pro libovolnou konstantu $c>0$.
-\h{Cvièení}
+\h{Cvičení}
\numlist\ndotted
-\:Zvolte lep¹í reprezentaci grafu, abyste prostorovou slo¾itost sní¾ili z~$\Theta(n^2)$ na~$\O(m)$.
- Mù¾e se tím zmen¹it èasová slo¾itost?
-\:Doka¾te, ¾e z~na¹eho rozboru pravdìpodobnosti chyby plyne, ¾e v~ka¾dém grafu je nejvý¹e $\O(n^2)$
- minimálních øezù.
-\:Uka¾te, jak algoritmus upravit pro grafy s~ohodnocenými hranami.
+\:Zvolte lepÅ¡Ã reprezentaci grafu, abyste prostorovou složitost snÞili z~$\Theta(n^2)$ na~$\O(m)$.
+ Může se tÃm zmenÅ¡it Ä\8dasová složitost?
+\:Dokažte, že z~našeho rozboru pravděpodobnosti chyby plyne, že v~každém grafu je nejvýše $\O(n^2)$
+ minimálních řezů.
+\:Ukažte, jak algoritmus upravit pro grafy s~ohodnocenými hranami.
\endlist
\references
projects / ga.git / blobdiff