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