From cc9e2e8641a08edb0abd7f385f115e4ee630a0af Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 1 Nov 2010 21:15:32 +0100 Subject: [PATCH] Haldove operaci pro mazani minima rikejme ExtractMin, ne DeleteMin ExtractMin je zabehnutejsi nazev a take o neco logictejsi, protoze naznacuje, ze minimum nejen mazeme, ale take ho pri tom zjistime. --- 13-dijkstra/13-dijkstra.tex | 90 ++++++++++++++++++++----------------- 6-borjar/6-borjar.tex | 4 +- ga.bib | 33 ++++++++++++++ 3 files changed, 84 insertions(+), 43 deletions(-) diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex index 9fc3dd4..35da445 100644 --- a/13-dijkstra/13-dijkstra.tex +++ b/13-dijkstra/13-dijkstra.tex @@ -12,20 +12,21 @@ prov pro hledání cest jsou nedílnou souèástí základních kursù programování a algoritmù, my se budeme vìnovat zejména rùzným jejich vylep¹ením. -Mìjme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena -{\I délkou} $\ell(e)$, co¾ je nìjaké reálné èíslo. Pro libovolnou -posloupnost hran~$P$ (speciálnì tedy pro sled nebo cestu) definujeme -její délku $\ell(P)$ jako souèet délek v¹ech hran posloupnosti. -Za {\I vzdálenost} $d(u,v)$ dvou vrcholù prohlásíme nejmen¹í mo¾nou -délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho, +Uva¾ujme tedy nìjaký orientovaný graf, jeho¾ ka¾dá hrana~$e$ je opatøena +{\I délkou} $\ell(e)\in{\bb R}$. Mno¾inì hran (tøeba sledu nebo cestì) +pak pøiøadíme délku rovnou souètu délek jednotlivých hran. + +Pro vrcholy $u,v$ definujeme jejich {\I vzdálenost} $d(u,v)$ jako nejmen¹í +mo¾nou délku cesty z~$u$ do~$v$ (jeliko¾ cest je v~grafu koneènì mnoho, minimum v¾dy existuje). Pokud z~$u$ do~$v$ ¾ádná cesta nevede, polo¾íme $d(u,v) := \infty$. -Obvykle se studují následující tøi varianty problému: +Obvykle se studují následující tøi problémy: \itemize\ibull \:{\bo 1-1} neboli {\bo P2PSP} (Point to Point Shortest Path) -- chceme nalézt nejkrat¹í - ze~v¹ech cest z~daného vrcholu~$u$ do~daného vrcholu~$v$. + cestu z~daného vrcholu~$u$ do~daného vrcholu~$v$. (Pokud je nejkrat¹ích cest + více, tak libovolnou z~nich.) \:{\bo 1-n} neboli {\bo SSSP} (Single Source Shortest Paths) -- pro daný vrchol~$u$ chceme nalézt nejkrat¹í cesty do~v¹ech ostatních vrcholù. \:{\bo n-n} neboli {\bo APSP} (All Pairs Shortest Paths) -- zajímají nás nejkrat¹í cesty @@ -35,13 +36,13 @@ Obvykle se studuj Pøekvapivì, tak obecnì, jak jsme si uvedené problémy definovali, je neumíme øe¹it v~polynomiálním èase: pro grafy, které mohou obsahovat hrany záporných délek bez jakýchkoliv omezení, je toti¾ hledání nejkrat¹í cesty NP-tì¾ké -(lze na~nìj snadno pøevést existence hamiltonovské cesty). V¹echny známé +(lze na~nìj snadno pøevést existenci hamiltonovské cesty). V¹echny známé polynomiální algoritmy toti¾ místo nejkrat¹í cesty hledají nejkrat¹í sled --- nekontrolují toti¾ nijak, zda cesta neprojde jedním vrcholem vícekrát. +-- nijak nekontrolují, zda cesta neprojde jedním vrcholem vícekrát. Na¹tìstí pro nás je to v~grafech bez cyklù záporné délky toté¾: pokud se v~nalezeném sledu vyskytne cyklus, mù¾eme jej \uv{vystøihnout} a tím získat -sled, který není del¹í, a~který má ménì hran. Ka¾dý nejkrat¹í sled tedy +sled, který není del¹í a~který má ménì hran. Ka¾dý nejkrat¹í sled tak mù¾eme upravit na~stejnì dlouhou cestu. V~grafech bez záporných cyklù je tedy jedno, zda hledáme sled nebo cestu; naopak vyskytne-li se záporný cyklus dosa¾itelný z~poèáteèního vrcholu, @@ -50,14 +51,13 @@ nejkrat Navíc se nám bude hodit, ¾e ka¾dý prefix nejkrat¹í cesty je opìt nejkrat¹í cesta. Jinými slovy pokud nìkterá z~nejkrat¹ích cest z~$u$ do~$v$ vede pøes nìjaký vrchol~$w$, pak její èást z~$u$ do~$w$ je jednou z~nejkrat¹ích -cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í -cestu.) +cest z~$u$ do~$w$. (V~opaèném pøípadì bychom mohli úsek $u\ldots w$ vymìnit za~krat¹í.) -Díky této vlastnosti mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom -nejkrat¹ích cest}~${\cal T}(u)$. To je strom definovaný na~vrcholech zadaného -grafu~$G$, zakoøenìný v~$u$ a orientovaný smìrem od~koøene, takový, ¾e pro ka¾dý -vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou z~nejkrat¹ích -cest z~$u$ do~$v$ v~grafy~$G$. +Díky této {\I prefixové vlastnosti} mù¾eme pro ka¾dý vrchol~$u$ sestrojit jeho {\I strom +nejkrat¹ích cest}~${\cal T}(u)$. To je nìjaký podgraf grafu~$G$, který má tvar +stromu zakoøenìného v~$u$ a orientovaného smìrem od~koøene, a~platí pro nìj, ¾e +pro ka¾dý vrchol~$v$ je (jediná) cesta z~$u$ do~$v$ v~tomto stromu jednou +z~nejkrat¹ích cest z~$u$ do~$v$ v~pùvodním grafu. \s{Pozorování:} Strom nejkrat¹ích cest v¾dy existuje. @@ -65,7 +65,7 @@ cest z~$u$ do~$v$ v~grafy~$G$. Nech» $u=v_1,\ldots,v_n$ jsou v¹echny vrcholy grafu~$G$. Indukcí budeme dokazovat, ¾e pro ka¾dé~$i$ existuje strom~${\cal T}_i$, v~nìm¾ se nacházejí nejkrat¹í cesty z~vrcholu~$u$ do vrcholù $v_1,\ldots,v_i$. Pro $i=1$ staèí uvá¾it -strom obsahující pouze vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme +strom obsahující jediný vrchol~$u$. Ze~stromu ${\cal T}_{i-1}$ pak vyrobíme strom ${\cal T}_i$ takto: Nalezneme v~$G$ nejkrat¹í cestu z~$u$ do~$v_i$ a oznaèíme~$z$ poslední vrchol na~této cestì, který se je¹tì vyskytuje v~${\cal T}_{i-1}$. Úsek nejkrat¹í cesty od~$z$ do~$v_i$ pak pøidáme do~${\cal T}_{i-1}$ @@ -98,11 +98,6 @@ $h(v) + \ell(v,w)$, tedy d sledu do~$v$ o~hranu $(v,w)$. Pokud je tato hodnota men¹í ne¾~$h(w)$, tak jí $h(w)$ pøepí¹eme. -Relaxace tedy zachovává to, ¾e ohodnocení odpovídá délkám nìjakých sledù, -a~souèasnì toto ohodnocení mù¾e zlep¹ovat. Budeme se tedy sna¾it nìjaké -poèáteèní ohodnocení (nabízí se $h(u)=0$, $h(v)=\infty$ pro $v\ne u$) -postupnými relaxacemi pøetvoøit na~ohodnocení vzdálenostmi. - Abychom zabránili opakovaným relaxacím tého¾ vrcholu, které nic nezmìní, budeme rozli¹ovat tøi stavy vrcholù: {\I nevidìn} (je¹tì jsme ho nenav¹tívili), {\I otevøen} (zmìnilo se ohodnocení, èasem chceme relaxovat) a {\I uzavøen} @@ -117,7 +112,7 @@ N \::$v\leftarrow\hbox{libovolný otevøený vrchol}$. \::$\(v)\leftarrow\$. \::Relaxujeme~$v$: -\:::Pro v¹echny hrany $(v,w)$ opakujeme: +\:::Pro v¹echny hrany $vw$ opakujeme: \::::Je-li $h(w) < h(v) + \ell(v,w)$: \:::::$h(w)\leftarrow h(v) + \ell(v,w)$. \:::::$\(w)\leftarrow\$. @@ -125,37 +120,50 @@ N \endalgo Podobnì jako u~minimálních koster, i zde se jedná o~meta-algoritmus, proto¾e -v~kroku~4 nespecifikuje, podle jakého pravidla se vrchol~$v$ vybírá. Pøesto +v~kroku~4 nespecifikuje, který z~otevøených vrcholù vybírá. Pøesto ale mù¾eme dokázat nìkolik zajímavých tvrzení, která na~konkrétním zpùsobu výbìru nezávisejí. \s{Vìta:} Spustíme-li meta-algoritmus na graf bez záporných cyklù, pak: \numlist\nparen -\:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu -- doká¾eme indukcí podle poètu krokù algoritmu. -\:$h(v)$ dokonce odpovídá délce nìjaké cesty -- staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus. -\:Algoritmus se v¾dy zastaví -- cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro - ka¾dý~$v$, je koneènì mnoho. -\:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$ -- - implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol, - který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran. +\:Ohodnocení $h(v)$ v¾dy odpovídá délce nìjakého sledu. +\:$h(v)$ dokonce odpovídá délce nìjaké cesty. +\:Algoritmus se v¾dy zastaví. +\:Po zastavení jsou oznaèeny jako uzavøené právì ty vrcholy, které jsou dosa¾itelné z~$u$. \:Po zastavení mají koneèné~$h(v)$ právì v¹echny uzavøené vrcholy. -\:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$ -- kdyby to nebyla pravda, +\:Pro ka¾dý dosa¾itelný vrchol je na~konci $h(v)$ rovno $d(u,v)$. +\endlist + +\proof + +\numlist\nparen +\:Doká¾eme indukcí podle poètu krokù algoritmu. +\:Staèí rozmyslet, v~jaké situaci by vytvoøený sled mohl obsahovat cyklus. +\:Cest, a~tím pádem i mo¾ných hodnot~$h(v)$ pro ka¾dý~$v$, je koneènì mnoho. +\:Implikace $\Rightarrow$ je triviální, pro $\Leftarrow$ staèí uvá¾it neuzavøený vrchol, + který je dosa¾itelný z~$u$ cestou o~co nejmen¹ím poètu hran. +\:$h(v)$ nastavujeme na~koneènou hodnotu právì v~okam¾icích, kdy se vrchol stává otevøeným. + Ka¾dý otevøený vrchol je èasem uzavøen. +\:Kdyby tomu tak nebylo, vyberme si ze~\uv{¹patných} vrcholù~$v$ takový, pro nìj¾ obsahuje nejkrat¹í cesta z~$u$ do~$v$ nejmen¹í mo¾ný poèet hran. Vrchol~$v$ je zajisté rùzný od~$u$, tak¾e má na~této cestì nìjakého pøedchùdce~$w$. Pøitom~$w$ u¾ musí být ohodnocen správnì a relaxace, která mu toto ohodnocení nastavila, ho musela prohlásit za~otevøený. Jen¾e ka¾dý otevøený vrchol je pozdìji uzavøen, tak¾e~$w$ poté musel být je¹tì alespoò jednou relaxován, co¾ muselo sní¾it~$h(v)$ na správnou vzdálenost. +\qeditem \endlist -\>Meta-algoritmus tedy pro libovolnou implementaci kroku~4 spoèítá správné vzdálenosti. -\qed +\>Dokázali jsme tedy, ¾e meta-algoritmus pro libovolnou implementaci kroku~4 +spoèítá správné vzdálenosti. + +\medskip \s{Cvièení:} \itemize\ibull \:Nech» do algoritmu doplníme udr¾ování pøedchùdcù tak, ¾e v~kroku~9 - pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$u$. Doka¾te, ¾e pøedchùdci + pøenastavíme pøedchùdce vrcholu~$w$ na vrchol~$v$. Doka¾te, ¾e pøedchùdci dosa¾itelných vrcholù budou tvoøit strom a ¾e tento strom bude stromem nejkrat¹ích cest z~vrcholu~$u$. \:Doka¾te, ¾e pro graf, v~nìm¾ je alespoò jeden záporný cyklus dosa¾itelný @@ -166,10 +174,10 @@ v \h{Bellmanùv-Fordùv-Mooreùv algoritmus} -Bellman, Ford a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM), +Bellman \cite{bellman:bfm}, Ford \cite{ford:bfm} a Moore objevili nezávisle na sobì algoritmus (øíkejme mu BFM), který lze v~øeèi na¹eho meta-algoritmu formulovat takto: Otevøené vrcholy udr¾ujeme ve~frontì (v¾dy relaxujeme vrchol na poèátku fronty, novì otevírané -zaøazujeme na~konec. Co toto pravidlo zpùsobí? +zaøazujeme na~konec). Co toto pravidlo zpùsobí? \s{Vìta:} Èasová slo¾itost algoritmu~BFM je $\O(nm)$. @@ -183,7 +191,7 @@ d tedy nejvý¹e~$n$. Relaxace ka¾dého vrcholu pøitom trvá lineárnì se stupnìm vrcholu, tak¾e celá -fáze probìhne v~èase $\O(m)$. +fáze probìhne v~èase $\O(m)$. V¹echny fáze pak v~$\O(nm)$. \qed \s{Cvièení:} @@ -199,7 +207,7 @@ f \h{Dijkstrùv algoritmus} Pokud jsou v¹echny délky hran nezáporné, mù¾eme pou¾ít efektivnìj¹í pravidlo -pro výbìr vrcholu navr¾ené Dijkstrou. To øíká, ¾e v¾dy relaxujeme ten z~otevøených +pro výbìr vrcholu navr¾ené Dijkstrou \cite{dijkstra:mstandpath}. To øíká, ¾e v¾dy relaxujeme ten z~otevøených vrcholù, jeho¾ ohodnocení je nejmen¹í. \s{Vìta:} Dijkstrùv algoritmus uzavírá vrcholy v~poøadí podle neklesající diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index f1b0c01..92761e8 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -96,7 +96,7 @@ udr \:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$. \:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$. \:Opakujeme, dokud $H\neq\emptyset$: -\::$vw\leftarrow \(H)$, pøièem¾ $v\not\in T, w\in T$. +\::$vw\leftarrow \(H)$, pøièem¾ $v\not\in T, w\in T$. \::$T\leftarrow T\cup\{vw\}$ \::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí dosud nejsou v~$T$, upravíme haldu: \:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$. @@ -109,7 +109,7 @@ hranou~$uv$ a provedeme \. \s{Èasová slo¾itost:} Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede -nanejvý¹ $n$-krát, za~\ v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání +nanejvý¹ $n$-krát, za~\ v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání vrcholù do~$H$ a~nalézání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$ (nanejvý¹ $m$-krát provedu porovnání vah a \ v~kroku~\the\algcnt\ za~$\O(1)$). diff --git a/ga.bib b/ga.bib index edac83d..1c11d69 100644 --- a/ga.bib +++ b/ga.bib @@ -533,3 +533,36 @@ year={1997}, organization={Society for Industrial and Applied Mathematics} } + +@article{ bellman:bfm, + author = {Richard Bellman}, + title = {On a Routing Problem}, + journal = {Quarterly of Applied Mathematics}, + volume = {16}, + number = {1}, + year = {1958}, + pages = {87--90}, + url = {http://wisl.ece.cornell.edu/ECE794/Jan29/bellman1958.pdf}, +} + +@techreport{ ford:bfm, + title = {Network Flow Theory}, + author = {Ford Jr., L. R.}, + institution = {The RAND Corperation, Santa Moncia, California}, + number = {P-923}, + month = {August}, + type = {Paper}, + year = {1956}, +} + +@article{ dijkstra:mstandpath, + title={{A note on two problems in connexion with graphs}}, + author = "Dijkstra, E. W.", + journal={Numerische Mathematik}, + volume={1}, + number={1}, + pages={269--271}, + year={1959}, + publisher={Springer Verlag} +} + -- 2.39.5