From 796377ce2cddf5e553dafd8641f277655c37dfa8 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 15 Jan 2008 20:34:25 +0100 Subject: [PATCH] Korektury kapitoly o aproximaci. --- 12-apx/12-apx.tex | 52 +++++++++++++++++++++++++---------------------- 1 file changed, 28 insertions(+), 24 deletions(-) diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex index 9a307fd..3b0b38f 100644 --- a/12-apx/12-apx.tex +++ b/12-apx/12-apx.tex @@ -1,31 +1,32 @@ \input lecnotes.tex -\prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda)} +\prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda, M. Mare¹)} \>Na~minulých predná¹kach sme sa zaoberali rôzne »a¾kými rozhodovacími problémami. Táto sa zaoberá postupmi ako sa v~praxi vysporiada» s~rie¹ením týchto problémov. \h{Prvý spôsob: ©peciálny prípad} -\>Èasto si vystaèíme s~vyrie¹ením ¹peciálneho prípadu NP~problému, ktorý le¾í v~P. Napríklad, ak rie¹ime grafovú úlohu, tak nám mô¾e staèi» rie¹enie pre~¹peciálny graf (strom, bipartitný graf,$\ldots$). Farbenie grafu je µahké pre~nejaký malý poèet farieb. 2SAT, ako ¹peciálny prípad SAT-u sa dá rie¹i» v~lineárnom èase. +\>Èasto si vystaèíme s~vyrie¹ením ¹peciálneho prípadu NP-úplného problému, ktorý le¾í v~P. Napríklad, ak rie¹ime grafovú úlohu, tak nám mô¾e staèi» rie¹enie pre~¹peciálny druh grafov (strom, bipartitný graf, \dots). Farbenie grafu je µahké pre~nejaký malý poèet farieb. 2SAT, ako ¹peciálny prípad SAT-u, sa dá rie¹i» v~lineárnom èase. \s{Problém: Maximálna nezávislá mno¾ina v strome (nie rozhodovacia)} \>{\I Vstup:} zakorenený strom~$T$ -\>{\I Vstup:} nezávislá mno¾ina vrcholov~$M$ + +\>{\I Výstup:} Maximálna (èo do poètu vrcholov) nezávislá mno¾ina vrcholov~$M$ \>BUNV mô¾eme predpoklada», ¾e v~$M$ sú v¹etky listy~$T$. Ak by nejaký list $l$ nebol v~$M$, tak sa pozrieme na jeho otca: \itemize\ibull -\:ak otec nie je v~$M$, tak vytvoríme novú nezávislú mno¾inu~$M'$ obsahujúcu aj~$l$ (veµkos» nezávislej mno¾iny stúpla o~1). -\:ak tam otec je, tak ho z~$M$ vyjmeme a~namiesto neho vlo¾íme~$l$ (veµkos» nezávislej mno¾iny sa nezmen¹ila). +\:Ak otec nie je v~$M$, tak vytvoríme novú nezávislú mno¾inu~$M'$ obsahujúcu aj~$l$ (veµkos» nezávislej mno¾iny stúpla o~1). +\:Ak tam otec je, tak ho z~$M$ vyjmeme a~namiesto neho vlo¾íme~$l$ (veµkos» nezávislej mno¾iny sa nezmen¹ila). \endlist -\>Tieto listy aj ich otcov z~$T$ odstránime a~postup opakujeme. $T$ sa mô¾e rozpadnú» na~les; potom tento postup aplikujeme na~v¹etky stromy v~lese. +\>Tieto listy aj ich otcov z~$T$ odstránime a~postup opakujeme. $T$~sa mô¾e rozpadnú» na~les; potom tento postup aplikujeme na~v¹etky stromy v~lese. \s{Algoritmus:} \algo -\:Polo¾íme $M1:={listy stromu T}$. -\:Polo¾íme $M2:={otcovia vrcholov z~M1}$. -\:Vrátime $M1 \cup MaxNz(T\setminus(M1 \cup M2)$ +\:Polo¾íme $M_1$:=$\{$listy stromu $T\}$. +\:Polo¾íme $M_2$:=$\{$otcovia vrcholov z~$M_1\}$. +\:Vrátime $M_1 \cup$ MaxNz$(T\setminus(M_1 \cup M_2)$. \endalgo -\>{\I Poznámka:} toto doká¾eme naprogramova» v \O(n) (vrcholy máme vo fronte a prechádzame). +\>{\I Poznámka:} Toto doká¾eme naprogramova» v $\O(n)$ (vrcholy máme vo fronte a prechádzame). \s{Problém: Batoh} @@ -78,31 +79,34 @@ maj \h{Druhý spôsob: Aproximácia} -\>V predchádzajúcich problémoch sme sa zamerali na ¹peciálne prípady. Obèas v¹ak také ¹tastie nemáme a~musíme vyrie¹i» NP-úplný problém. Mo¾eme ustúpi» tak, ¾e nebudeme rie¹i» nieèo, èo je úplne optimálne, ale je to nejaky pomer optimalnosti ({\I aproximácia}), t.j. vieme o~koµko maximálne je na¹e rie¹enie hor¹ie ako optimálne. +\>V predchádzajúcich problémoch sme sa zamerali na ¹peciálne prípady. Obèas v¹ak také ¹tastie nemáme a~musíme vyrie¹i» celý NP-úplný problém. Mo¾eme si v¹ak pomôc» tým, ¾e sa nebudeme sna¾i» vyrie¹i» ho optimálne -- iba v nejakom pomere k~optimálnosti ({\I aproximácia}), t.j. budeme vedie», o~koµko maximálne je na¹e rie¹enie hor¹ie ako optimálne. + +\s{Problém: Obchodný cestujúci} -\s{Problém: Obchodný cestujuci} +\>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow {\bb R}^+_0$ -\>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow R^+_0$ \>{\I Vystup:} Hamiltonovská kru¾nica (v¹etky vrcholy grafu), a~to tá najkrat¹ia (podµa ohodnotenia). -\>Tento problém je hneï na~prvý pohµad nároèný - u¾ problém, èi existuje Hamiltonovská kru¾nica je NP-úplný. BUNV nech graf~$G$ je úplný (doplnime zvy¹né hrany ohodnotené $max(w)+1$ alebo viac, nie v¹ak nekoneènom, lebo by neplatila trojuholníková nerovnos»). Vyrie¹me tento problém najprv za~predpokladu, ¾e vrcholy grafu spåòajú trojuholníkovú nerovnos», potom bez nej. +\>Tento problém je hneï na~prvý pohµad nároèný -- u¾ problém, èi existuje Hamiltonovská kru¾nica, je NP-úplný. BUNV nech graf~$G$ je úplný (doplnime zvy¹né hrany ohodnotené $max(w)+1$ alebo viac, nie v¹ak nekoneènom, lebo by neplatila trojuholníková nerovnos», ktorú neskôr budeme potrebova»). Vyrie¹me tento problém najprv za~predpokladu, ¾e vrcholy grafu spåòajú trojuholníkovú nerovnos», potom bez nej. \>{\I a) trojuholníková nerovnos»:} $\forall x,y,z \in V: w(xz)\le w(xy)+w(yz)$ \>Existuje pekný algoritmus, ktory nájde Hamiltonovsku kru¾nicu, èo je -maximálne dvakrát tak veµká ako najoptimálnej¹ia. +maximálne dvakrát tak veµká ako optimálna. \>Nájdeme najmen¹iu kostru a~obchodnému cestujúcemu poradíme, nech ide po~nej (staèí zakoreni» a~prejs» do~håbky). Problémom v¹ak je, ¾e daný sled obsahuje ka¾dý vrchol viackrát a~preto musíme nahradi» nepovolené vracania sa, t.j.~pre ka¾dý vrchol nájs» e¹te nenav¹tívený vrchol v~na¹om slede a~ís» priamo naò. Keï¾e platí trojuholníková nerovnos», tak si týmito skratkami neu¹kodíme. Nech minimálna kostra má váhu~$T$. Váha obídeného sledu tak bude~$2T$. Skrátenia urèite nezväè¹ujú, tak¾e váha nájdene Hamiltonovskej kru¾nice bude nanajvý¹~$2T$. -\>Ak máme Hamiltonovskú kru¾nicu~$C$ a~z~nej vy¹krtneme hranu, tak máme kostru grafu~$G$ s~váhou najviac~$w(C)$, teda to aspoò takú, aká je váha minimálnej kostry - $T$. To je optimálny prípad Hamiltonovskej kru¾nice. Ak to teda zlo¾íme dohromady, algoritmus nám vráti Hamiltonovskú kru¾nicu s~váhou najviac dvojnásobnou od~optimálnej Hamiltonovskej kru¾nice. Takéto algoritmy sa nazývajú {\I 2-aproximaèné}, keï¾e rie¹enie je maximálne dvojnásobné od~optimálneho. +\>Ak máme Hamiltonovskú kru¾nicu~$C$ a~z~nej vy¹krtneme hranu, tak máme kostru grafu~$G$ s~váhou najviac~$w(C)$, teda to aspoò takú, aká je váha minimálnej kostry --~$T$. To je optimálny prípad Hamiltonovskej kru¾nice. Ak to teda zlo¾íme dohromady, algoritmus nám vráti Hamiltonovskú kru¾nicu s~váhou najviac dvojnásobnou od~optimálnej Hamiltonovskej kru¾nice. Takéto algoritmy sa nazývajú {\I 2-aproximaèné}, keï¾e rie¹enie je maximálne dvojnásobné od~optimálneho. + +\>{\I b) bez~trojuholníkovej nerovnosti:} -\>{\I b) bez~trojuholníkovej nerovnosti} \>Tu sa budeme naopak sna¾i» ukáza», ¾e ¾iaden polynomiálny aproximaèný algoritmus neexistuje. -\s{Veta:} Ak existuje polynomiálny $(1+\varepsilon)$-aproximaèný algoritmus pre~algoritmus obchodného cestujúceho bez~trojuholníkovej nerovnosti pre~µubovoµné $\varepsilon>0$, potom $P~=~NP$. -\>Dôkaz: Uká¾eme, ¾e v~tom prípade doká¾eme v~polynomiálnom èase nájs» Hamiltonovskú kru¾nicu. +\s{Veta:} Ak existuje polynomiálny $(1+\varepsilon)$-aproximaèný algoritmus pre~algoritmus obchodného cestujúceho bez~trojuholníkovej nerovnosti pre~µubovoµné $\varepsilon>0$, tak potom $P = NP$. + +\proof Uká¾eme, ¾e v~tom prípade doká¾eme v~polynomiálnom èase nájs» Hamiltonovskú kru¾nicu. -\>Dostali sme graf $G$, v~ktorom hµadáme Hamiltonovskú kru¾nicu. Doplníme $G$ na~uplný graf~$G'$ a~váhy hrán~$G'$ +\>Dostali sme graf $G$, v~ktorom hµadáme Hamiltonovskú kru¾nicu. Doplníme $G$ na~uplný graf~$G'$ a~váhy hrán~$G'$ nastavíme takto: \itemize\ibull \: $w(e) = 1$, ak $e \in E(G)$ \: $w(e) = c \ll 1$, ak $e \in E(G)$ @@ -110,12 +114,13 @@ maxim \>Ak existuje Hamiltonovská kru¾nica v~$G'$ zlo¾ená iba z~hrán, ktoré boli pôvodne v~$G$, tak optimálné rie¹enie bude ma» váhu $n$, inak bude urèite minimálne $n-1+c$. Ak máme aproximaèný algoritmus s~pomerom $1+\varepsilon$, musí by» $$ \eqalign{ -(1+\varepsilon)\cdot n < n-1+c -c > \varepsilon\cdot n+1 +(1+\varepsilon).n &< n-1+c \cr +\varepsilon n+1 &< c } $$ \>Ak by taký algoritmus existoval, tak na~neho máme polynomiálny algoritmus na~Hamiltonovsku kru¾nicu. Inak neexistuje ani pseudo-polynomialny algoritmus. +\qed \h{Aproximaèní schéma pro problém batohu} @@ -134,8 +139,7 @@ vyd stejná mno¾ina pøedmìtù jako u~zadání pùvodního. Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky -nìjak zaokrouhlit. Øe¹ení nové úlohy pak sice nebude pøesnì odpovídat optimálnímu -øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací. +nìjak zaokrouhlit. Øe¹ení nové úlohy pak sice nebude pøesnì odpovídat optimálnímu øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací. \s{Základní my¹lenka:} -- 2.39.2