12-randcut/12-randcut.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{12}{Pravděpodobnostní algoritmus na řezy}{}
   4
   5 Nahlédněme alespoň jednou kapitolou do~světa pravděpodobnostních algoritmů.
   6 Není totiž výjimkou, že s~pomocí generátoru náhodných čísel vyřešíme některé
   7 grafové problémy daleko snáze a často také efektivněji, než to dovedeme deterministicky.
   8 Pravděpodobnostní přístup si předvedeme na~Kargerově-Steinově algoritmu \cite{karger:mincut}
   9 pro hledání minimálního řezu v~neohodnoceném neorientovaném grafu. Připomeňme,
  10 že s~deterministickými algoritmy jsme zatím dosáhli časové složitosti $\O(n^{5/3}m)$
  11 pomocí toků nebo $\O(nm)$ Nagamochiho-Ibarakiho algoritmem.
  12
  13 \h{Náhodné kontrakce}
  14
  15 Uvažujme nejdříve následující algoritmus, který náhodně vybírá
  16 hrany a kontrahuje je, dokud počet vrcholů neklesne na~$\ell$.
  17 (Konkrétní hodnotu~$\ell$ zvolíme později.)
  18
  19 \s{Algoritmus} $\hbox{\sc Contract}(G_0,\ell)$:
  20 \algo
  21 \:$G \leftarrow G_0$.
  22 \:Dokud $n>\ell$:
  23 \::Vybereme hranu $e\in E$ rovnoměrně náhodně.
  24 \::$G \leftarrow G/e$ (kontrahujeme hranu~$e$, smyčky odstraňujeme,
  25   paralelní hrany ponecháme).
  26 \:Vrátíme jako výsledek graf~$G$.
  27 \endalgo
  28
  29 Jaká je pravděpodobnost, že výsledný graf~$G$ má stejně velký minimální řez
  30 jako zadaný graf~$G_0$? Všimněme si nejprve, že každý řez v~grafu $G/e$ je i řezem
  31 v~grafu~$G$ (až na přeznačení hran při kontrakci, ale předpokládejme, že hrany
  32 mají nějaké identifikátory, které kontrakce zachovává). Podobně je-li v~grafu~$G$
  33 řez neobsahující hranu~$e$, odpovídá mu stejně velký řez v~$G/e$. Velikost
  34 minimálního řezu tedy kontrakcí nikdy neklesne -- může pouze stoupnout, pokud
  35 skontrahujeme hranu ležící ve~všech minimálních řezech,
  36
  37 Zvolíme nyní pevně jeden z~minimálních řezů~$C$ v~zadaném grafu~$G_0$ a označíme~$k$ jeho
  38 velikost. Pokud algoritmus ani jednou nevybere hranu ležící v~tomto řezu, velikost
  39 minimálního řezu v~grafu~$G$ bude rovněž rovna~$k$. Jaká je pravděpodobnost, že
  40 se tak stane?
  41
  42 Označme $G_i$ stav grafu~$G$ před $i$-tým průchodem cyklem a $n_i$ a $m_i$ počet jeho
  43 vrcholů a hran. Zřejmě $n_i=n-i+1$ (každou kontrakcí přijdeme o~jeden vrchol).
  44 Navíc každý vrchol má stupeň alespoň~$k$, jelikož jinak by triviální řez okolo
  45 tohoto vrcholu byl menší než minimální řez. Proto platí $m_i \ge kn_i/2$. Hranu
  46 ležící v~řezu~$C$ tedy vybereme s~pravděpodobností nejvýše $k/m_i \le k/(kn_i/2) = 2/n_i
  47 = 2/(n-i+1)$. Všechny hrany z~řezu~$C$ proto postoupí do výsledného grafu~$G$
  48 s~pravděpodobností
  49 $$\eqalign{
  50 p     &\ge \prod_{i=1}^{n-\ell} \left( 1 - {2\over n-i+1} \right)
  51        = \prod_{i=1}^{n-\ell} {n-i-1 \over n-i+1} = \cr
  52       &= {n-2\over n} \cdot {n-3\over n-1} \cdot {n-4\over n-2} \cdot \cdots \cdot {\ell+1\over \ell+3} \cdot {\ell\over \ell+2} \cdot {\ell-1 \over \ell+1}
  53        = {\ell\cdot(\ell-1) \over n\cdot(n-1)}. \cr
  54 }$$
  55
  56 Ještě musíme ošetřit případ, kdy bychom hranu řezu smazali, protože se mezitím
  57 stala smyčkou. Ovšem smyčky vznikají pouze z~hran paralelních s~právě kontrahovanou
  58 hranou. Jelikož v~libovolném svazku paralelních hran buďto všechny leží v~$C$,
  59 nebo ani jedna neleží, museli jsme v~takovém případě řez~$C$ rozbít už dříve.
  60 Odhad pravděpodobnosti to tedy neovlivní.
  61
  62 Můžeme tedy zvolit pevně~$\ell$, spustit na~zadaný graf proceduru {\sc Contract}
  63 a ve~vzniklém konstantně velkém grafu pak nalézt minimální řez hrubou silou
  64 (to je obzvláště snadné pro $\ell=2$ -- tehdy stačí vzít všechny zbylé hrany).
  65 Takový algoritmus nalezne minimální řez s~pravděpodobností alespoň $c/n^2$,
  66 kde~$c$ je konstanta závislá na~$\ell$.
  67
  68 Nabízí se otázka, k~čemu je dobrý algoritmus, který vydá správný výsledek
  69 s~pravděpodobností na~řádu $1/n^2$. To opravdu není mnoho, ale stejně jako
  70 mnoho jiných randomizovaných algoritmů i tento můžeme iterovat: výpočet
  71 zopakujeme $K$-krát a použijeme nejmenší z~nalezených řezů. Ten už bude
  72 minimální s~pravděpodobností
  73 $$
  74 P_K \ge 1 - (1-c/n^2)^K \ge 1 - e^{-cK/n^2}.
  75 $$
  76 (Druhá nerovnost platí díky tomu, že $e^{-x} \ge 1-x$ pro všechna $x\ge 0$.)
  77 Pokud tedy nastavíme počet opakování~$K$ na $\Omega(n^2)$, můžeme tím pravděpodobnost
  78 chyby stlačit pod libovolnou konstantu, pro $K=\Omega(n^2\log n)$ pod převrácenou
  79 hodnotu libovolného polynomu v~$n$ a pro $K=\Omega(n^3)$ už bude dokonce exponenciálně malá.
  80
  81 \h{Implementace}
  82
  83 Odbočme na chvíli k~implementačním záležitostem. Jak reprezentovat graf, abychom
  84 stihli rychle provádět kontrakce? Bude nám stačit obyčejná matice sousednosti,
  85 v~níž pro každou dvojici vrcholů budeme udržovat, kolik paralelních hran mezi těmito vrcholy
  86 vede. Pokud chceme kontrahovat hranu~$uv$, stačí projít všechny hrany vedoucí
  87 (řekněme) z~vrcholu~$u$ a zařadit je k~vrcholu~$v$. To zvládneme v~čase $\O(n)$
  88 na jednu kontrakci.
  89
  90 Pro náhodný výběr hrany budeme udržovat pole stupňů vrcholů, vybereme náhodně
  91 vrchol~$v$ s~pravděpodobností úměrnou stupni a poté projitím příslušného řádku
  92 matice sousednosti druhý vrchol~$v$ s~pravděpodobností úměrnou počtu hran
  93 mezi $u$ a~$v$. To opět trvá čas $\O(n)$.
  94
  95 Procedura {\sc Contract} tedy pracuje v~čase $\O((n-\ell)\cdot n)$ a celý
  96 $K$-krát ziterovaný algoritmus v~$\O(Kn^2)$. Pokud se spokojíme s~převráceně
  97 polynomiální pravděpodobností chyby, nalezneme minimální řez v~čase $\O(n^4\log n)$.
  98
  99 \h{Kargerův-Steinův algoritmus}
 100
 101 Předchozí prostinký algoritmus můžeme ještě podstatně vylepšit.
 102 Všimněme si, že během kontrahování hran pravděpodobnost toho, že vybereme \uv{špatnou}
 103 hranu ležící v~minimálním řezu, postupně rostla z~počátečních $2/n$ až po obrovské
 104 $2/3$ v~poslední iteraci (pro $\ell=2$). Pomůže tedy zastavit kontrahování dříve
 105 a~přejít na~spolehlivější způsob hledání řezu.
 106
 107 Pokud zvolíme $\ell=\lceil n/\sqrt2 +1\rceil$, pak řez~$C$ přežije kontrahování
 108 s~pravděpodobností alespoň
 109 $$
 110 {\ell\cdot (\ell-1) \over n\cdot (n-1)}
 111 \ge {(n/\sqrt2+1)\cdot n/\sqrt2 \over n\cdot (n-1)}
 112 = {n/\sqrt2+1 \over \sqrt2 \cdot (n-1)}
 113 = {n+\sqrt 2 \over 2\cdot (n-1)}
 114 \ge {1\over 2}.
 115 $$
 116
 117 Jako onen spolehlivější způsob hledání řezu následně zavoláme stejný algoritmus
 118 rekurzivně, přičemž jak kontrakci, tak rekurzi provedeme dvakrát a z~obou
 119 nalezených řezů vybereme ten menší, čímž pravděpodobnost chyby snížíme.
 120
 121 Hotový algoritmus bude vypadat následovně:
 122
 123 \s{Algoritmus} $\hbox{\sc MinCut}(G)$:
 124 \algo
 125 \:Pokud $n<7$, najdeme minimální řez hrubou silou.
 126 \:$\ell\leftarrow \lceil n/\sqrt 2 + 1 \rceil$.\foot{To je méně než~$n$, kdykoliv $n\ge 7$.}
 127 \:$C_1 \leftarrow \hbox{\sc MinCut}(\hbox{\sc Contract}(G,\ell))$.
 128 \:$C_2 \leftarrow \hbox{\sc MinCut}(\hbox{\sc Contract}(G,\ell))$.
 129 \:Vrátíme menší z~řezů $C_1$, $C_2$.
 130 \endalgo
 131
 132 Jakou bude mít tento algoritmus časovou složitost? Nejprve odhadněme hloubku
 133 rekurze: v~každém kroku se velikost vstupu zmenší přibližně $\sqrt 2$-krát, takže strom
 134 rekurze bude mít hloubku $\O(\log n)$. Na~$i$-té hladině zpracováváme $2^i$
 135 podproblémů velikosti $n/2^{i/2}$. Při výpočtu každého podproblému voláme
 136 dvakrát proceduru {\sc Contract}, která spotřebuje čas $\O((n/2^{i/2})^2)
 137 = \O(n^2/2^i)$. Součet přes celou hladinu tedy činí $\O(n^2)$ a přes všechny
 138 hladiny $\O(n^2\log n)$. Oproti původnímu kontrakčnímu algoritmu jsme si tedy
 139 moc nepohoršili.
 140
 141 Zbývá spočítat, s~jakou pravděpodobností algoritmus skutečně nalezne minimální řez.
 142 Označme $p_i$ pravděpodobnost, že algoritmus na~$i$-té hladině stromu
 143 rekurze (počítáno od~nejhlubší, nulté hladiny) vydá správný výsledek
 144 příslušného podproblému. Jistě je $p_0=1$ a platí rekurence
 145 $p_i \ge 1 - (1 - 1/2 \cdot p_{i-1})^2$. Uvažujme posloupnost $g_i$, pro kterou
 146 jsou tyto nerovnosti splněny jako rovnosti, a~všimněme si, že $p_i\ge g_i$.
 147 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$.
 148
 149 Nyní zavedeme substituci $z_i = 4/g_i - 1$, čili $g_i=4/(z_i+1)$, a~tak získáme
 150 novou rekurenci pro~$z_i$:
 151 $$
 152 {4 \over z_i+1} = {4\over z_{i-1}+1} - {4\over (z_{i-1}+1)^2},
 153 $$
 154 kterou už můžeme snadno upravovat:
 155 $$\eqalign{
 156 {1\over z_i+1} &= {z_{i-1} \over (z_{i-1}+1)^2}, \cr
 157 z_i+1 &= {z_{i-1}^2 + 2z_{i-1} + 1 \over z_{i-1}}, \cr
 158 z_i+1 &= z_{i-1} + 2 + {1\over z_{i-1}}. \cr
 159 }$$
 160 Jelikož $z_0=3$, a~tím pádem $z_i\ge 3$ pro všechna~$i$, získáme z~poslední
 161 rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudíž $z_i \le 2i+3$.
 162 Zpětnou substitucí obdržíme $g_i \ge 4/(2i+4)$, tedy $p_i \ge g_i = \Omega(1/i)$.
 163
 164 Nyní si stačí vzpomenout, že hloubka rekurze činí $\O(\log n)$, a ihned získáme
 165 odhad pro pravděpodobnost správného výsledku $\Omega(1/\log n)$. Náš algoritmus
 166 tedy stačí ziterovat $\O(\log^2 n)$-krát, abychom pravděpodobnost chyby stlačili
 167 pod převrácenou hodnotu polynomu. Dokázali jsme následující větu:
 168
 169 \s{Věta:} Iterováním algoritmu {\sc MinCut} nalezneme minimální řez v~neohodnoceném
 170 neorientovaném grafu v~čase $\O(n^2\log^3 n)$ s~pravděpodobností chyby $\O(1/n^c)$
 171 pro libovolnou konstantu $c>0$.
 172
 173 \h{Cvičení}
 174
 175 \numlist\ndotted
 176 \:Zvolte lepší reprezentaci grafu, abyste prostorovou složitost snížili z~$\Theta(n^2)$ na~$\O(m)$.
 177   Může se tím zmenšit časová složitost?
 178 \:Dokažte, že z~našeho rozboru pravděpodobnosti chyby plyne, že v~každém grafu je nejvýše $\O(n^2)$
 179   minimálních řezů.
 180 \:Ukažte, jak algoritmus upravit pro grafy s~ohodnocenými hranami.
 181 \endlist
 182
 183 \references
 184 \bye