From 32efae3cfd48aa968b765b9d20ab4c132dccba08 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 25 Oct 2009 18:17:33 +0100 Subject: [PATCH] Korektury. --- 12-randcut/12-randcut.tex | 51 ++++++++++++++++++++------------------- 1 file changed, 26 insertions(+), 25 deletions(-) diff --git a/12-randcut/12-randcut.tex b/12-randcut/12-randcut.tex index b89cdb5..34ea5c1 100644 --- a/12-randcut/12-randcut.tex +++ b/12-randcut/12-randcut.tex @@ -4,10 +4,10 @@ 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¾ deterministicky. -Tento pøístup si pøedvedeme na~Kargerovì-Steinovì algoritmu \cite{karger:mincut} +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 deterministickými algoritmy jsme zatím dosáhli èasové slo¾itosti $\O(n^{5/3}m)$ +¾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. \h{Náhodné kontrakce} @@ -30,10 +30,10 @@ jako zadan 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 +minimálního øezu tedy kontrakcí nikdy neklesne -- mù¾e pouze stoupnout, pokud zkontrahujeme 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 a oznaèíme~$k$ jeho +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 se tak stane? @@ -43,7 +43,7 @@ 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í $k/m_i \le k/(kn_i/2) = 2/n_i -= 2/(n-i+1)$. V¹echny hrany z~øezu~$C$ tedy postoupí do výsledného grafu~$G$ += 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) @@ -69,13 +69,13 @@ $$ (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 exponenciálnì malá. +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 nimi +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. @@ -83,7 +83,7 @@ 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~$uv$. To opìt trvá èas $\O(n)$. +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~inverznì @@ -91,10 +91,11 @@ polynomi \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^2$ a¾ po obrovské -$2/3$ v~poslední iteraci (pro $\ell=2$). Mù¾eme tedy algoritmus vylep¹it tím, ¾e -se zastavíme døíve a pak pøejdeme na~spolehlivìj¹í zpùsob hledání øezu. +$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ò @@ -106,9 +107,9 @@ $$ \ge {1\over 2}. $$ -Jako onen spolehlivìj¹í zpùsob hledání øezu pak zavoláme tentý¾ algoritmus -rekurzivnì, pøièem¾ jak kontrakci, tak rekurzi provedeme dvakrát a z~výsledkù -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ì: @@ -122,40 +123,40 @@ Hotov \endalgo Jakou bude mít tento algoritmus èasovou slo¾itost? Nejprve odhadnìme hloubku -rekurze: v~ka¾dém kroku se velikost vstupu zmen¹í $\sqrt 2$-krát, tak¾e strom +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 v¹echny hladiny tedy èíní $\O(n^2)$, stejnì jako u~pùvodního kontrakèního algoritmu. -Zbývá spoèítat, s~jakou pravdìpodobností algoritmus nalezne skuteènì minimální øez. +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~nejni¾¹í, nulté hladiny) vydá správný výsledek +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 = g_{i-1} - g_{i-1}^2/4$. +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)$, získáme +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 upravit: +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/z_{i-1}). \cr +z_i+1 &= z_{i-1} + 2 + {1\over z_{i-1}}. \cr }$$ -Z~poslední rovnosti plyne, ¾e $z_i \le z_{i-1} + 2$, co¾ spoleènì s~poèáteèní -podmínkou $z_0=4$ implikuje $z_i \le 2i+4$. Zpìtnou substitucí získáme $g_i \ge 4/(2i+5)$, -tedy $p_i \ge g_i = \Omega(1/i)$. +Jeliko¾ $z_0=4$, a~tím pádem $z_i\ge 1$ pro v¹echna~$i$, získáme z~poslední +rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudí¾ $z_i \le 2i+4$. +Zpìtnou substitucí obdr¾íme $g_i \ge 4/(2i+5)$, 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 tím následující vìtu: +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^2 n)$ s~pravdìpodobností chyby $\O(1/n^c)$ -- 2.39.2