X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=12-apx%2F12-apx.tex;h=9a307fdc72ed8c86531d4c795477446ac5e8483b;hb=e2f7cc0614f5c80a64cff78ceee8165af57f7cc4;hp=3625a401918b8e19a62bc218a54107dff06d836e;hpb=d1f95d7e91aa65daa2bb8c4a3d45cc19f965774d;p=ads2.git diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex index 3625a40..9a307fd 100644 --- a/12-apx/12-apx.tex +++ b/12-apx/12-apx.tex @@ -1,57 +1,122 @@ \input lecnotes.tex -\prednaska{12}{Aproximaèní algoritmy}{(???)} +\prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda)} -\h{Pseudopolynomiální algoritmus pro problém batohu} +\>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. -\s{POZOR:} Na~pøedná¹ce byla jen verze bez cen, nauète se, prosím, obì. --M.M. +\h{Prvý spôsob: ©peciálny prípad} -\s{Problém batohu:} Je dána mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ -a cenami $c_1,\ldots,c_n$ a batoh, který unese hmotnost~$H$. Naleznìte takovou -podmno¾inu pøedmìtù, jejich¾ celková hmotnost je nejvý¹e~$H$ a celková cena je -maximální mo¾ná. +\>È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. -Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry: +\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$ + +\>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). +\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. + +\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)$ +\endalgo +\>{\I Poznámka:} toto doká¾eme naprogramova» v \O(n) (vrcholy máme vo fronte a prechádzame). + +\s{Problém: Batoh} + +\>Je daná mno¾ina $n$~predmetov s~hmotnos»ami $h_1,\ldots,h_n$ +a cenami $c_1,\ldots,c_n$ a~batoh, ktorý unesie hmotnos»~$H$. Nájdite takú +podmno¾inu predmetov, ktorých celková hmotnos» je najviac~$H$ a~celková cena je +maximálna mo¾ná. + +\>Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry: Jednak místo rozhodovacího problému øe¹íme optimalizaèní, jednak pøedmìty mají ceny (pøedchozí verze odpovídala tomu, ¾e ceny jsou rovny hmotnostem). Uká¾eme si algoritmus pro øe¹ení tohoto obecného problému, jeho¾ èasová slo¾itost bude polynomiální v~poètu pøedmìtù~$n$ a souètu v¹ech cen~$C=\sum_i c_i$. -Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$ +\>Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$ pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost -podmno¾iny, jeji¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$: +podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$: Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì -pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto pøedmìt $k$ nepou¾ili -(a pak je $A_k(c)=A_{k-1}(c)$) nebo pou¾ili a tehdy bude $A_k(c) = A_{k-1}(c-c_k) + h_k$ +pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili +(a pak je $A_k(c)=A_{k-1}(c)$), nebo pou¾ili a tehdy bude $A_k(c) = A_{k-1}(c-c_k) + h_k$ (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou mo¾ností si vybereme tu, která dává mno¾inu s~men¹í hmotností. Tedy: $$ A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k). $$ -Tímto zpùsobem v~èase $\O(C)$ spoèteme jednu mno¾ínu, v~èase $\O(nC)$ pak v¹echny. +Tímto zpùsobem v~èase $\O(C)$ spoèteme jednu mno¾inu, v~èase $\O(nC)$ pak v¹echny. -Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do batohu. To bude -nejvìt¹í~$c^*$, pro které je $A_n(c^*) < \infty$. To nás stojí èas $\O(C)$. +\>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do batohu. To bude +nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) < \infty$. Jeho nalezení nás stojí èas $\O(C)$. -A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus, -aby si pro ka¾dé $A_k(c)$ pamatoval $B_k(c)$, co¾ je index posledního pøedmìtu, -který do~pøíslu¹né mno¾iny pøidal. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$ +\>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus, +aby si pro ka¾dé $A_k(c)$ pamatoval $B_k(c)$, co¾ bude index posledního pøedmìtu, +který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$ poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního prvku k~prvnímu. -Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í -problém batohu. To není polynom ve~velikosti vstupu ($C$~mu¾e být a¾ exponenciálnì +\>Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í +problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ( $C$~mu¾e být a¾ exponenciálnì velké vzhledem k~velikosti vstupu), ale pouze ve~velikosti èísel na~vstupu. Takovým algoritmùm se øíká {\I pseudopolynomiální.} \s{Verze bez cen:} Na verzi s~cenami rovnými hmotnostem se dá pou¾ít i jiný algoritmus zalo¾ený na~dynamickém programování: poèítáme mno¾iny -$Z_k$, které obsahují v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá -nìjaká podmno¾ina prvních~$k$ prvkù batohu. Pøitom $Z_0=\{0\}$, $Z_k$ -spoèteme z~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny +$Z_k$ obsahující v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá +nìjaká podmno¾ina prvních~$k$ prvkù. Pøitom $Z_0=\{0\}$, $Z_k$ +spoèteme ze~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$. +\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. + +\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 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. + +\>{\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. + +\>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. + +\>{\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. + +\>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'$ +\itemize\ibull +\: $w(e) = 1$, ak $e \in E(G)$ +\: $w(e) = c \ll 1$, ak $e \in E(G)$ +\endlist +\>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 +} +$$ +\>Ak by taký algoritmus existoval, tak na~neho máme polynomiálny algoritmus +na~Hamiltonovsku kru¾nicu. Inak neexistuje ani pseudo-polynomialny algoritmus. + \h{Aproximaèní schéma pro problém batohu} \s{POZOR:} Verze algoritmu, kterou jsem øíkal na~pøedná¹ce, obsahovala jednu @@ -70,25 +135,24 @@ stejn 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ò dobrou aproximací -optima. +øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací. \s{Základní my¹lenka:} Oznaèíme si $c_{max}$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M$ -a zobrazme interval cen $[0, c_{max}]$ na $[0,M]$. +a zobrazíme interval cen $[0, c_{max}]$ na $[0,M]$. Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé ceny zaokrouhlili na~násobky èísla $c_{max}/M$. Ka¾dé $c_i$ jsme tím zmìnili o~nejvý¹e $c_{max}/M$, celkovou cenu libovolné podmno¾iny pøedmìtù tedy -nejvý¹e o~$n\cdot c_{max}/M$. Teï si je¹tì v¹imneme, ¾e pokud ze~zadání odstraníme -pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy ceny $OPT\ge c_{max}$, +nejvý¹e o~$n\cdot c_{max}/M$. Teï si je¹tì v¹imnìme, ¾e pokud ze~zadání odstraníme +pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $OPT\ge c_{max}$, tak¾e chyba v~souètu je nejvý¹e $n\cdot OPT/M$. Má-li tato chyba být shora omezena -$\varepsilon\cdot OPT$, musíme zvolit $M\approx n/\varepsilon$. +$\varepsilon\cdot OPT$, musíme zvolit $M\ge n/\varepsilon$. \s{Algoritmus:} \algo \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$. -\:Spoèítáme $c_{max}=\max_i c_i$ a zvolíme $M=\lfloor n/\varepsilon\rfloor$. +\:Spoèítáme $c_{max}=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$. \:Kvantujeme ceny: $\hat{c}_i = \lfloor c_i \cdot M/c_{max} \rfloor$. \:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$ a pùvodní hmotnosti i kapacitu batohu. @@ -126,7 +190,7 @@ kvantovan které nemù¾e být lep¹í. Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$: $$ \eqalign{ -ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} = +ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} \ge OPT - {n\cdot c_{max}\over n / \varepsilon} \ge OPT - \varepsilon c_{max} \ge \cr &\ge OPT - \varepsilon OPT = (1-\varepsilon)\cdot OPT. } @@ -134,7 +198,7 @@ $$ Algoritmus tedy v¾dy vydá øe¹ení, které je nejvý¹e $(1-\varepsilon)$-krát hor¹í ne¾ optimum, a~doká¾e to pro libovolné~$\varepsilon$ v~èase polynomiálním v~$n$. Takovému algoritmu øíkáme {\I polynomiální aproximaèní schéma} (jinak té¾ PTAS\foot{Polynomial-Time Approximation Scheme}). -V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~zavislosti na~$1/\varepsilon$, tak¾e +V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e schéma je {\I plnì polynomiální} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation Scheme}). \bye