From d38fdf9a1342b6360679919f099f08e8ddba6829 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 14 Dec 2007 21:17:41 +0100 Subject: [PATCH] Drobna (a prijemna) vylepseni kapitoly o Goldbergovi. --- 4-goldberg/4-goldberg.tex | 56 +++++++++++++++++++-------------------- 1 file changed, 27 insertions(+), 29 deletions(-) diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex index e2c9294..469984c 100755 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -1,3 +1,5 @@ +%version 1.5 + \input lecnotes.tex \prednaska{4}{Goldbergùv algoritmus}{(zapsali R. Tupec, @@ -7,41 +9,40 @@ J. Z \noindent Pøedstavíme si nový algoritmus pro~hledání maximálního toku v~síti, který se uká¾e stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) a po~nìkolika vylep¹eních bude i lep¹í. -\noindent %todo pøeformulovat:BEGIN -Tento algoritmus narozdíl od~Dinicova algoritmu zaèíná s~pøebytky v~sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevádìní. Abychom se pøi~tomto pøevádìní nezacyklili, definujeme vý¹ku vrcholu a pøevádíme pouze s~kopce. -%todo pøeformulovat:END +\noindent +Tento algoritmus narozdíl od~Dinicova algoritmu zaèíná s~pøebytky v~sousedních vrcholech zdroje a sna¾í se jich zbavit pomocí pøevádìní. Pokud bychom toto pøevádìní dìlali \uv{tupým zpùsobem}, mohl by se algoritmus zacyklit.Proto pro~ka¾dý vrchol budeme definovat vý¹ku a jak uvidíme, s~její pomocí se vyhneme zacyklení. \s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$ -je {\I vlna} v~síti ($V, E, z, s, c$) tehdy, kdy¾ $ \forall uv \in E : f(uv) \leq c(uv) $, kde $c(uv)$ je kapacita hrany $uv$ a $ \forall v \ne z, s : f^{\Delta}(v) \geq 0 $. Funkcí $f^{\Delta}(v)$ rozumíme pøebytek, který pøebývá ve~vrcholu $v$, co¾ je souèet v¹eho, co do~vrcholu $v$ pøiteèe, mínus souèet v¹eho, co z~$v$ odteèe. To mù¾eme zapsat jako +je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ $ \forall uv \in E : f(uv) \leq c(uv) $, kde $c(uv)$ je kapacita hrany~$uv$, a $ \forall v \ne z, s : f^{\Delta}(v) \geq 0 $. Funkcí $f^{\Delta}(v)$ rozumíme pøebytek, který pøebývá ve~vrcholu~$v$, co¾ je souèet v¹eho, co do~vrcholu~$v$ pøiteèe, mínus souèet v¹eho, co z~$v$ odteèe. To mù¾eme zapsat jako $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$ -Tok je vlna, kde $ f^{\Delta}(v) = 0 , \forall v \ne z,s $. +Ka¾dý tok je vlna, kde $\forall v \ne z,s: f^{\Delta}(v) = 0$. \noindent Algoritmus pou¾ívá sít rezerv, kterou jsme nadefinovali ji¾ v~pøedchozí kapitole vìnované Dinicovi. \noindent -Dále budeme provádìt dvì operace na~vrcholech sítì. K~tomu budeme potøebovat pøiøadit v¹em vrcholùm vý¹ky pomocí funkce $h : V \rightarrow \bb{N}$. +Dále budeme provádìt dvì operace na~vrcholech sítì. K~tomu budeme potøebovat pøiøadit v¹em vrcholùm vý¹ku pomocí funkce $h : V \rightarrow \bb{N}$. -\s{Operace:} Pro~hranu $uv \in E$ definujme {\I pøevedení pøebytku}: +\s{Operace:} Pro~hranu~$uv \in E$ definujme {\I pøevedení pøebytku}: \noindent Pokud platí, ¾e \numlist \ndotted - \:ve~vrcholu $u$ je nenulový pøebytek, tj. $f^{\Delta}(u) > 0$, - \:vrchol $u$ je vý¹ ne¾ vrchol $v$, tj. $h(u) > h(v)$, a + \:ve~vrcholu~$u$ je nenulový pøebytek, tj. $f^{\Delta}(u) > 0$, + \:vrchol~$u$ je vý¹ ne¾ vrchol~$v$, tj. $h(u) > h(v)$, a \:hrana $uv$ má nenulovou rezervu, tj. $r(uv)>0$, \endlist \noindent pøevedeme tok o~velikosti $\delta:=\min(f^{\Delta}(u),r(uv))$ z~$u$ do~$v$ tímto zpùsobem: \numlist \ndotted - \:$f^{\Delta}(u):=f^{\Delta}(u)-\delta$ a $f^{\Delta}(v):=f^{\Delta}(v)+\delta$, - \:$r(uv):=r(uv)-\delta$ a $r(vu)=r(vu)+\delta$. + \:$f^{\Delta}(u) \leftarrow f^{\Delta}(u)-\delta$ a $f^{\Delta}(v) \leftarrow f^{\Delta}(v)+\delta$, + \:$r(uv) \leftarrow r(uv)-\delta$ a $r(vu) \leftarrow r(vu)+\delta$. \endlist Øekneme, ¾e pøevedení je {\I nasycené}, pokud je po~pøevodu rezerva na~hranì $uv$ nulová, tedy $r(uv)=0$. -Naopak pøevedení {\I nenasycené}, pokud po~pøevodu $f^{\Delta}(u) = 0$. Pokud $r(uv)=0$ a $f^{\Delta}(u) = 0$, +Naopak pøevedení je {\I nenasycené}, pokud po~pøevodu $f^{\Delta}(u) = 0$. Pokud $r(uv)=0$ a $f^{\Delta}(u) = 0$, budeme pøevedení pova¾ovat za~{\I nasycené}. -\s{Operace:} Pro~vrchol $u \in V$ definujme {\I zvednutí vrcholu}: -Pokud bìhem výpoètu narazíme ve~vrcholu $u$ na~pøebytek, který nelze nikam pøevést, zvìt¹íme vý¹ku vrcholu $u$ o~$1$, tj. $h(u)=h(u)+1$. +\s{Operace:} Pro~vrchol~$u \in V$ definujme {\I zvednutí vrcholu}: +Pokud bìhem výpoètu narazíme ve~vrcholu~$u$ na~pøebytek, který nelze nikam pøevést, zvìt¹íme vý¹ku vrcholu~$u$ o~$1$, tj. $h(u) \leftarrow h(u)+1$. \s{Algoritmus:} (Goldbergùv) @@ -67,8 +68,8 @@ Pro~prvn \s{Invariant S (o~Spádu):} Neexistuje hrana se~spádem vìt¹ím ne¾ jedna a nenulovou rezervou, neboli $\forall uv \in E, r(uv)>0 : h(u) \leq h(v)+1$. -\proof %todo pøeformulovat:BEGIN -Podívejme se, kdy by mohla vzniknout nenasycená hrana se~spádem vìt¹ím ne¾ 1. V~druhé fázi algoritmu k~tomu nedojde. Pokud ji¾ existuje vrchol $v$ s~kladným pøebytkem, dále existuje nenasycená hrana $(v,u)$ a $h(v)=h(u)+1$, vrchol $v$ algoritmus nezvedá a rovnou pøebytek posílá po~této hranì. Uva¾me tedy je¹tì druhý pøípad, kdy existuje nasycená hrana $(u,v)$ se~spádem vìt¹ím ne¾ jedna a tuto hranu se pokusíme odsytit. Jen¾e to také nejde, proto¾e kdybychom cokoli poslali proti smìru této hrany, bude to proti smìru funkce $h$, ale to nejde. +\proof %todo pøeformulovat:BEGIN OK +Podívejme se, kdy by mohla vzniknout nenasycená hrana se~spádem vìt¹ím ne¾ 1. Bìhem inicializace k~tomu evidentnì nedojede, proto¾e v¹echny hrany jsou nenasycené nebo mají kapacitu nula, proto je mù¾eme vypustit. Bìhem práce algoritmu k~tomu v¹ak také nedojde, jak uvidíme z~rozebrání následujících pøípadù. Pokud ji¾ existuje vrchol~$v$ s~kladným pøebytkem, dále existuje nenasycená hrana $vu$ a $h(v)=h(u)+1$, vrchol~$v$ algoritmus nezvedne, ale pøebytek po¹le po~této hranì. Uva¾me tedy je¹tì druhý pøípad, kdy existuje nasycená hrana $uv$ se~spádem vìt¹ím ne¾ jedna a tuto hranu se pokusíme odsytit. Jen¾e pokud bychom chtìli nìco poslat v protismìru, sna¾ili bychom se o pøelití proti smìru funkce $h$. \qed %todo pøeformulovat:END \s{Lemma K (o~Korektnosti):} Kdy¾ se algoritmus zastaví, je $f$ maximální tok. @@ -84,21 +85,19 @@ Nejprve uk \s{Invariant C (Cesta domù, do~zdroje):} Je-li $v \in V \setminus \{z,s\}$ a $f^{\Delta}(v) > 0$, pak existuje nenasycená cesta z~$v$ do~$z$. \proof -Mìjme nìjaký vrchol $v \in V$ takový, ¾e $f^{\Delta}(v) > 0$. +Mìjme nìjaký vrchol~$v \in V$ takový, ¾e $f^{\Delta}(v) > 0$. Potom definujme mno¾inu $A := \{ u \in V : \exists$ nenasycená cesta z~$v$ do~$u \}$. Mìjme vrcholy $a \in A$ a $b \in V \setminus A$ takové, ¾e $ba\in E$. O~nich víme, ¾e $f(ba)=0$, proto¾e pokud by tomu tak nebylo, muselo by platit $r(ab)>0$, a tudí¾ by $b$ patøilo do~mno¾iny $A$. \noindent Seètìme pøebytky ve~v¹ech vrcholech mno¾iny $A$. Proto¾e pøebytek ka¾dého vrcholu se spoèítá jako souèet tokù do~nìj vstupujících minus souèet tokù z~nìj vystupujících a v¹echny hrany, jejich¾ oba vrcholy le¾í v~$A$, se jedenkrát pøiètou a jedenkrát odeètou, platí: $$\sum_{u \in A}f^{\Delta}(u)=\sum_{\scriptstyle{ab \in E \cap {\bb A}} \atop \scriptstyle{{\bb A} = \bar{A}\times A}} f(a,b)-\sum_{{\scriptstyle ba \in E \cap {\bb A}} \atop {\scriptstyle {\bb A} = A\times \bar{A}}} f(b,a).$$ -%todo pøeformulovat:BEGIN -Proto¾e v¹ak do~$A$ nic neteèe, nebo» obsahuje zdroj (pokud není izolovaný, existují nenasycené zpìtné hrany), tento výraz musí být men¹í nebo roven nule. Odtud vyplývá, ¾e pokud nìco odtéká ven z~$A$, nebo $A$ obsahuje $s$, pak $\exists u \in A, f^{\Delta}(u)<0$. Toto $u$ v¹ak musí být zdroj, proto¾e v¹echny ostatní vrcholy mají kladný pøebytek. -\qed %todo pøeformulovat:END +My v¹ak víme, ¾e do~$A$ nic neteèe, a proto $\sum_{v \in A}{f^\Delta(v) \le 0}$. Zároveò v¹ak v~$A$ je vrchol s~kladným pøebytkem, toti¾ $v$, proto v~$A$ musí být také vrchol se záporným pøebytkem a jediný takový je $z$. +\qed \s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\le 2n$. -\proof %todo pøeformulovat:BEGIN -Víme, ¾e poèet hran v~cestì ze~$z$ do~$\forall v \in V$ je maximálnì $n-1$. -Pokud by existoval vrchol $v$ s~vý¹kou $h(v)>2n$, musel by být zvednut alespoò $2n$-krát. To ale znamená, ¾e by po~$2n-1$ zvednutích musel mít stále pøebytek. Pokud tento pøebytek nelze pøevést do~¾ádného jiného vrcholu ${u} \in E$, musí platit $h(v)\le h({u})$ a tedy $v$ bude zvednut po~$2n$-té. To ale znamená, ¾e by platilo $h(v)-h(z)=n$. Dále víme z~Invariantu~C, ¾e existuje nenasycená cesta z~$v$ do~$z$. Potom ale na~cestì ze~$z$ do~$v$ existuje hrana se~spádem vìt¹ím ne¾ 1, a to je spor s~Invariantem S. -\qed %todo pøeformulovat:END +\proof +Víme, ¾e poèet hran na~cestì ze~$z$ do~$\forall v \in V$ je maximálnì $n-1$. Pokud by existoval vrchol~$v$ s~vý¹kou $h(v)>2n$, museli jsme tento vrchol zvednout alespoò $(2n+1)$-krát. Snadno si uvìdomíme, ¾e $z$ nikdy nezvedáme, a tudí¾ by na cestì ze $z$ do $v$ musela být hrana se spádem vìt¹ím ne¾ $1$, co¾ je spor s~Invariantem~S. +\qed \s{Lemma Z (poèet Zvednutí):} Poèet v¹ech zvednutí je maximálnì $2n^{2}$. @@ -109,7 +108,7 @@ Sta \s{Lemma S (naSycená pøevedení):} Poèet v¹ech nasycených pøevedení je maximálnì $NM$. \proof -Mìjme hranu $uv \in E$, kterou jsme právì nasytili. Tedy platí $h(v)h(u)$. Proto, abychom tuto hranu opìt nasytili, musíme opìt zmìnit nerovnost vý¹ek na~$h(v)h(u)$. Proto, abychom tuto hranu opìt nasytili, musíme opìt zmìnit nerovnost vý¹ek na~$h(v) 0$. Kdy¾ mìníme pøebytek nìjakého vrcholu, mù¾eme ná¹ seznam v~konstantním èase aktualizovat (napø. tak, ¾e si ka¾dý vrchol pamatuje pozici, na~které v~seznamu je). A v~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. Dále si $\forall u \in V$ budeme pamatovat $L(u) := $ seznam $uv \in E$ takových, ¾e $r(uv) > 0$ a $h(v) < h(u)$. Díky tomu mù¾eme pøistupovat k~patøièným sousedùm $u$ v~èase $\O(1)$, stejnì jako provádìt operace pøidání do~$L(u)$ resp. smazání v~nìm. Pøi~pøevádìní nìjakého vrcholu $v$ vyhodíme $v$ nejvý¹e jednou, a to opìt v~èase $\O(1)$. %todo ? cotoje ? -A koneènì zvedání vrcholu $v$ nám zabere èas $\O(N)$, proto¾e musíme obejít v¹echny hrany $uv$, kterých je nejvý¹e $N-1$, porovnat vý¹ky a pøípadnì odebrat $uv$ z~seznamu $L(u)$ resp. pøidat do $L(v)$. Abysme pro odebrání hrany $uv$ ze~seznamu $L(u)$ nemuseli procházet celý seznam, budeme si $\forall v \in V$ pamatovat je¹tì $L^{-1}(v) := $ seznam ukazatelù na~hrany $uv$ v~seznamech $L(u)$. +Budeme si pamatovat seznam $P$ v¹ech vrcholù $v \ne z,s$ takových, ¾e $f^{\Delta}(v) > 0$. Kdy¾ mìníme pøebytek nìjakého vrcholu, mù¾eme ná¹ seznam v~konstantním èase aktualizovat (napø. tak, ¾e si ka¾dý vrchol pamatuje pozici, na~které v~seznamu je). A v~konstantním èase také umíme odpovìdìt, zda existuje nìjaký vrchol s~pøebytkem. Dále si $\forall u \in V$ budeme pamatovat $L(u) := $ seznam $uv \in E$ takových, ¾e $r(uv) > 0$ a $h(v) < h(u)$. Díky tomu mù¾eme pøistupovat k~patøièným sousedùm $u$ v~èase $\O(1)$, stejnì jako provádìt operace pøidání do~$L(u)$ resp. smazání v~nìm. Ka¾dé pøevedení po~hranì $uv$ nás stojí konstantní èas na~aktualizaci rezerv hran $uv$ a $vu$, stejnì tak i na aktualizaci pøebytkù ve~vrcholech $u$ a $v$. V~pøípadì, ¾e se jedná o~nasycené pøevedení, musíme je¹tì odstranit hranu~$uv$ z~$L(u)$, co¾ také stihneme v~èase $\O(1)$. A koneènì zvedání vrcholu~$v$ nám zabere èas $\O(N)$, proto¾e musíme obejít v¹echny hrany~$uv$, kterých je $\O(N)$, porovnat vý¹ky a pøípadnì odebrat $uv$ z~seznamu $L(u)$ resp. pøidat do $L(v)$. Abysme pro odebrání hrany~$uv$ ze~seznamu $L(u)$ nemuseli procházet celý seznam, budeme si $\forall v \in V$ pamatovat je¹tì $L^{-1}(v) := $ seznam ukazatelù na~hrany~$uv$ v~seznamech $L(u)$. \s{Vìta:} Goldbergùv algoritmus najde maximální tok v~èase $\O(N^2M)$. @@ -138,7 +136,7 @@ A kone Z~lemmatu~Z vyplývá, ¾e celkový poèet zvednutí je maximálnì $2N^2$, pøièem¾ ka¾dé zvednutí jsme schopni provést v~èase $\O(N)$. Tak¾e dohromady pro~zvedání spotøebujeme èas $\O(N^3)$, co¾ je pro souvislé sítì urèitì $\O(N^2M)$. Z~lemmatu~S pro~zmìnu vyplývá, ¾e nasycená pøevedení nás stojí $\O(NM)$, a na~závìr z~lemmatu~N dostáváme èasovou slo¾itost $\O(N^2M)$ pro~pøevedení nenasycená. Proto celková slo¾itost algoritmu je $\O(N^2M)$. \qed %todo ? pro zmìnu vs. prozmenu ? -Dokázali jsme, ¾e algoritmus má èasovou slo¾itost $\O(N^2M)$ pro libovolnou posloupnost zvedání a pøevádìni. Nabízí se otázka, zda není mo¾né algoritmus zrychlit. Uká¾eme, ¾e pokud v~$5.$ kroku algoritmu budeme v¾dy brát vrchol $u$ takový, ¾e $h(u)$ je maximální, poèet nenasycených pøevedení se sní¾í. +Dokázali jsme, ¾e algoritmus má èasovou slo¾itost $\O(N^2M)$ pro libovolnou posloupnost zvedání a pøevádìni. Nabízí se otázka, zda není mo¾né vhodným výbìrem tìchto operací výpoèet zrychlit. Uká¾eme, ¾e pokud v~$5.$ kroku algoritmu budeme v¾dy brát vrchol~$u$ takový, ¾e $h(u)$ je maximální, poèet nenasycených pøevedení se sní¾í. \s{Lemma N':} Poèet nenasycených pøevedení v~upravené verzi Goldbergova algoritmu je $\O(N^2\sqrt{M})$, co¾ je maximálnì $\O(N^3)$. Díky tomu je i slo¾itost celého algoritmu $\O(N^3)$. -- 2.39.5