X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=12-apx%2F12-apx.tex;h=aa6fb39d9c98aa537d9a72339e90addef9be0ab9;hb=29c8e82fe084bb1496a7df2e9bb5f456f8988683;hp=8567c72d202168e9c76e8c4562d7447e7ce2b14f;hpb=11f70ce017a9492477ec69d359fcf99598407b12;p=ads2.git diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex index 8567c72..aa6fb39 100644 --- a/12-apx/12-apx.tex +++ b/12-apx/12-apx.tex @@ -1,45 +1,72 @@ \input lecnotes.tex -\prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda, M. Mare¹)} +\prednaska{12}{Aproximaèní algoritmy}{\vbox{\hbox{(F. Ha¹ko, J. Menda, M. Mare¹,} + \hbox{ Michal Kozák, Vojta Tùma)}}} -\>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. +\>Na~minulých pøedná¹kách jsme se zabývali rùznými tì¾kými rozhodovacími +problémy. Tato se zabývá postupy, jak se v~praxi vypoøádat s~øe¹ením tìchto +problémù. -\h{Prvý spôsob: ©peciálny prípad} +\h{Co dìlat, kdy¾ potkáme NP-úplný problém} +\algo +\:Nepanikaøit. +\:Spokojit se s~málem. +\:Rozmyslet, jestli opravdu potøebujeme obecný algoritmus. Mnohdy potøebujeme pouze +speciálnìj¹í pøípady, které mohou být øe¹itelné v~polynomiálním èase. +\:Spokojit se s~pøibli¾ným øe¹ením, (pou¾ít aproximaèní algoritmus). +\:Pou¾ít heuristiku -- napøíklad genetické algoritmy nebo randomizované algoritmy. +Velmi pomoci mù¾e i jen výhodnìj¹í poøadí pøi~prohledávání èi oøezávání nìkterých +napohled nesmyslných vìtví výpoètu. +\endalgo + +\h{První zpùsob: Speciální pøípad} -\>È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. +\>Èasto si vystaèíme s~vyøe¹ením speciálního pøípadu NP-úplného problému, který +le¾í v~$P$. Napøíklad pøi øe¹ení grafové úlohy nám mù¾e staèit øe¹ení +pro~speciální druh grafù (stromy, bipartitní grafy, \dots). Barvení grafu je lehké +napø. pro~dvì barvy èi pro intervalové grafy. 2-SAT, jako speciální pøípad SATu, +se dá øe¹it v~lineárním èase. -\s{Problém: Maximálna nezávislá mno¾ina v strome (nie rozhodovacia)} +\>Uká¾eme si dva takové pøípady (budeme øe¹ení hledat, nejen rozhodovat, zda existuje) -\>{\I Vstup:} zakorenený strom~$T$ +\s{Problém: Maximální nezávislá mno¾ina ve~stromì (ne rozhodovací)} -\>{\I Výstup:} Maximálna (èo do poètu vrcholov) nezávislá mno¾ina vrcholov~$M$ +\>{\I Vstup:} Zakoøenìný strom~$T$. -\>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: +\>{\I Výstup:} Maximální (co do~poètu vrcholù) nezávislá mno¾ina vrcholù~$M$~v~$T$. + +\>BÚNO mù¾eme pøedpokládat, ¾e v~$M$ jsou v¹echny listy $T$. Pokud by nìkterý +list $l$ v~$M$ nebyl, tak se podíváme na~jeho otce: \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). +\:Pokud otec není v~$M$, tak list $l$ pøidáme do~$M$, èím¾ se nezávislost +mno¾iny zachovala a velikost stoupla o~1. +\:Pokud tam otec je, tak ho z~$M$ vyjmeme a na~místo nìho vlo¾íme $l$. +Nezávislost ani velikost $M$ se nezmìnily. \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. +\>Nyní listy spolu s~jejich otci z~$T$ odebereme a postup opakujeme. $T$ se +mù¾e rozpadnout na~les, ale to nevadí $\to$ tentý¾ postup aplikujeme na~v¹echny stromy v~lese. \s{Algoritmus:} +\>MaxNz$(T)$ \algo -\: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)$. +\:Polo¾íme $L$:=$\{$listy stromu $T\}$. +\:Polo¾íme $O$:=$\{$otcové vrcholù z~$L\}$. +\:Vrátíme $L \cup$ MaxNz$(T\setminus(O \cup L))$. \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 naprogramovat v~$\O(n)$ (udr¾ujeme si frontu listù). \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á. +\>Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ +a cenami $c_1,\ldots,c_n$ a~batoh, který unese hmostnost~$H$. Najdìte takovou +podmno¾inu pøedmìtù, jejich¾ celková hmotnost je maximálnì $H$ a celková cena +je maximální 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$. +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$ pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost @@ -47,16 +74,18 @@ podmno 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 $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 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¾inu, v~èase $\O(nC)$ pak v¹echny. +Tímto zpùsobem v~èase $\O(C)$ spoèteme $A_k(c)$ pro fixní $k$ a v¹echna $c$, +v~èase $\O(nC)$ pak v¹echny $A_k(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)$. +\>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¾ bude index posledního pøedmìtu, @@ -66,70 +95,121 @@ a tak d prvku k~prvnímu. \>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í.} +problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ($C$~mù¾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í.} Ani takové +algoritmy ale nejsou k dispozici pro v¹echny problémy (napø. u problému obchodního +cestujícího nám vùbec nepomù¾e, ¾e váhy hran budou malá èísla). \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$ 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 +spoèteme ze~$Z_{k-1}$ --- udr¾ujme si $Z_{k-1}$ jako setøídìný spojový seznam, +výpoèet dal¹ího seznamu udìláme slitím dvou seznamù $Z_{k-1}$ a $Z_{k-1}$ se +v¹emi prvky zvý¹enými o hmotnost $k$ zahazujíce duplicitní a pøíli¹ velké hodnoty --- +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» 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} - -\>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow {\bb 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», 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 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. - -\>{\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$, 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'$ nastavíme takto: +\h{Druhý zpùsob: Aproximace} + +\>V pøedcházejících problémech jsme se zamìøili na~speciální pøípady. Obèas v¹ak +takové ¹tìstí nemáme a musíme vyøe¹it celý NP-úplný problém. Mù¾eme si v¹ak +pomoct tím, ¾e se ho nebudeme sna¾it vyøe¹it optimálnì -- namísto optimálního +øe¹ení najdeme nìjaké, které je nejvý¹e $c$-krát hor¹í pro nìjakou konstantu $c$. + +\s{Problém: Obchodní cestující} + +\>{\I Vstup:} Neorientovaný graf~$G$, ka¾dá hrana +je ohodnocená funkcí $w: E(G)\rightarrow {\bb R }^+_0$. + +\>{\I Výstup:} Hamiltonovská kru¾nice (obsahující v¹echny vrcholy grafu), a~to ta nejkrat¹í +(podle ohodnocení). + +\>Tento problém je hned na~první pohled nároèný -- u¾ sama existence +hamiltonovské kru¾nice je NP-úplná. Najdeme aproximaèní algoritmus nejprve za pøedpokladu, +¾e vrcholy splòují trojúhelníkovou nerovnost (tj. $\forall x,y,z \in V: w(xz)\le +w(xy)+w(yz)$), potom uká¾eme, ¾e v úplnì obecném pøípadé by samotná existence +aproximaèního algoritmu implikovala ${\rm P=NP }$. + +\>{\I a) trojúhelníková nerovnost:} + +Existuje pìkný algoritmus, který najde hamiltonovskou kru¾nici o délce $\leq +2\cdot opt$, kde $opt$ je délka nejkrat¹í hamiltonovské kru¾nice. +Vedle pøedpokladu trojúhelníkové +nerovnosti budeme potøebovat, aby ná¹ graf byl úplný. Souhrnnì mù¾eme +pøedpokládat, ¾e úlohu øe¹íme v nìjakém metrickém protoru, ve kterém jsou obì +podmínky podle definice splnìny. + +Najdeme nejmen¹í kostru grafu a obchodnímu cestujícímu poradíme, a» jde po~ní -- kostru +zakoøeníme a projdeme jako strom do hloubky, pøièem¾ se zastavíme a¾ v koøeni po projití +v¹ech vrcholù. Problém v¹ak je, ¾e prùchod po kostøe obsahuje +nìkteré vrcholy i hrany vícekrát, a proto musíme nahradit nepovolené vracení se. +Máme-li na nìjaký vrchol vstoupit podruhé, prostì ho ignorujeme a pøesuneme se +rovnou na dal¹í nenav¹tívený -- dovolit si to mù¾eme, graf je úplný a obsahuje +hrany mezi v¹emi dvojicemi vrcholù +(jinak øeèeno, poøadí vrcholù kru¾nice bude preorder výpis prùchodem do hloubky). +Pokud platí trojúhelníková nerovnost, tak si tìmito zkratkami neu¹kodíme. +Nech» minimální kostra má váhu~$T$. Pokud bychom pro¹li celou kostru, bude mít +sled váhu~$2T$ (ka¾dou hranou kostry jsme ¹li tam a zpátky), a pøeskakování +vrcholù celkovou váhu nezvìt¹uje (pøi pøeskoku +nahradíme cestu $xyz$ jedinou hranou $xz$, pøièem¾ z trojúhelníkové nerovnosti +máme $xz \leq xy + xz$), tak¾e váha nalezené +hamiltonovské kru¾nice bude také nanejvý¹ $2T$. + +Kdy¾ máme hamiltonovskou kru¾nici $C$ a z~ní vy¹krtneme hranu, dostaneme kostru +grafu~$G$ s~váhou men¹í ne¾ $C$ -- ale ka¾dá kostra je alespoò tak tì¾ká +jako minimální kostra $T$. Tedy optimální hamiltonovská kru¾nice je urèitì tì¾¹í +ne¾ minimální kostra $T$. Kdy¾ tyto dvì nerovnosti slo¾íme +dohromady, algoritmus nám vrátí hamiltonovskou kru¾nici $T'$ s~váhou nanejvý¹ +dvojnásobnou vzhledem k optimální hamiltonovské kru¾nici ($T' \leq 2T < 2C$). Takovéto +algoritmy se nazývají {\I 2-aproximaèní}, kdy¾ øe¹ení je maximálnì dvojnásobné +od~optimálního.\foot{Hezkým trikem se v obecných metrických prostorech umí +$1{,}5$-aproximace. Ve~nìkterých metrických prostorech (tøeba v euklidovské +rovinì) se aproximaèní pomìr dá dokonce srazit na +libovolnì blízko k 1. Zaplatíme ale na èase -- èím pøesnìj¹í výsledek +po algoritmu chceme, tím déle to bude trvat.} + +\>{\I b) bez~trojúhelníkové nerovnosti:} + +Zde se budeme naopak sna¾it ukázat, ¾e ¾ádný polynomiální aproximaèní +algoritmus neexistuje. + +\s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální +$(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího bez~trojúhelníkové nerovnosti, tak ${\rm P = NP }$. + +\proof Uká¾eme, ¾e v~takovém pøípadì doká¾eme v~polynomiálním èase zjistit, +zda v grafu existuje hamiltonovská kru¾nice. + +\>Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici. Doplníme +$G$ na~úplný graf~$G'$ a~váhy hran~$G'$ nastavíme takto: \itemize\ibull -\: $w(e) = 1$, ak $e \in E(G)$ -\: $w(e) = c \ll 1$, ak $e \not\in E(G)$ +\: $w(e) = 1$, kdy¾ $e \in E(G)$ +\: $w(e) = c \gg 1$, kdy¾ $e \not\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» +\>Konstantu $c$ potøebujeme zvolit tak velkou, abychom jasnì poznali, jestli +je ka¾dá hrana z nalezené hamiltonovské kru¾nice hranou grafu $G$ (pokud by +nebyla, bude kru¾nice obsahovat aspoò jednu hranu s váhou $c$, která vy¾ene +souèet poznatelnì vysoko). Pokud existuje hamiltonovská kru¾nice v~$G'$ slo¾ená jen +z~hran, které byly +pùvodnì v~$G$, pak optimální øe¹ení bude mít váhu~$n$, jinak bude urèitì +minimálnì $n-1+c$. Kdy¾ máme aproximaèní algoritmus s~pomìrem~$1+\varepsilon$, +musí tedy být $$ \eqalign{ -(1+\varepsilon).n &< n-1+c \cr +(1+\varepsilon)\cdot 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. +\>Kdyby takový algoritmus existoval, máme polynomiální algoritmus +na~hamiltonovskou kru¾nici. \qed -\h{Aproximaèní schéma pro problém batohu} +\s{Poznámka:} O existenci pseudopolynomiálního algoritmu +platí analogická vìta, a doká¾e se analogicky -- existující hrany budou +mít váhu 1, neexistující váhu 2. -\s{POZOR:} Verze algoritmu, kterou jsem øíkal na~pøedná¹ce, obsahovala jednu -pomìrnì zásadní chybu, které jsem si nev¹iml: Verze se zaokrouhlováním dolù -mohla produkovat nepøípustná (pøíli¹ tì¾ká) øe¹ení, verze se zaokrouhlováním nahoru pro zmìnu -nìkdy spoèítala øe¹ení pøíli¹ daleká od~optima. Algoritmus lze opravit (budeme-li -zvlá¹» zpracovávat lehké a tì¾ké pøedmìty), ale radìji budeme místo hmotností -kvantovat ceny. Tak dojdeme k~následujícímu aproximaènímu algoritmu. --M.M. +\h{Aproximaèní schéma pro problém batohu} Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$, pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen. @@ -139,36 +219,40 @@ 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:} -Oznaèíme si $c_{max}$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M$ -a zobrazíme interval cen $[0, c_{max}]$ na $[0,M]$. +Oznaèíme si $c_{max}$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < c_{max}$ +a zobrazíme interval cen $[0, c_{max}]$ na $[0,M]$ (tedy ka¾dou cenu znásobíme +$M/c_{max}$). 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 +ceny zaokrouhlili na~násobky èísla $c_{max}/M$ (prvky z intervalu +$[i\cdot c_{max}/M,(i+1)\cdot c_{max}/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím +tedy zmìnili o~nejvý¹e $c_{max}/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak 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\ge n/\varepsilon$. +$\varepsilon\cdot OPT$, musíme zvolit $M\ge n/\varepsilon$.\foot{Pøipomìòme, ¾e toto je¹tì není dùkaz, nebo» velkoryse pøehlí¾íme chyby dané zaokrouhlováním. Dùkaz provedeme ní¾e.} \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=\lceil n/\varepsilon\rceil$. -\:Kvantujeme ceny: $\hat{c}_i = \lfloor c_i \cdot M/c_{max} \rfloor$. +\:Kvantujeme ceny: $\forall i: \hat{c}_i \leftarrow \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. \:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání. \endalgo \>Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu -se souètem cen $\hat{C}\le nM \le n^2/\varepsilon$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$. +se souètem cen $\hat{C}\le nM = \O(n^2/\varepsilon)$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$. Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$. -Nejprve si rozmyslíme, jak dopadne optimální øe¹ení $OPT$ pùvodního zadání, -kdy¾ ceny v~nìm pou¾itých pøedmìtù nakvantujeme (mno¾inu indexù tìchto pøedmìtù si oznaèíme~$Y$): +Nejprve si rozmyslíme, jakou cenu budou mít pøedmìty které daly optimální øe¹ení +v pùvodním zadání (tedy mají v pùvodním zadání dohromady cenu $OPT$), +kdy¾ jejich ceny nakvantujeme (mno¾inu indexù tìchto pøedmìtù si oznaèíme~$Y$): $$ \eqalign{ \widehat{OPT} &= \sum_{i\in Y} \hat{c}_i = @@ -179,7 +263,7 @@ $$ OPT \cdot {M\over c_{max}} - n. } $$ -Nyní naopak spoèítejme, jak dopadne øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu +Nyní spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu na~pùvodní ceny (to je výsledek na¹eho algoritmu): $$ \eqalign{ @@ -203,6 +287,13 @@ Algoritmus tedy v 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~závislosti na~$1/\varepsilon$, tak¾e -schéma je {\I plnì polynomiální} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation Scheme}). +schéma je {\I plnì polynomiální} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation +Scheme}). U nìkterých problémù se stává, ¾e aproximaèní schéma závisí na +$1/\varepsilon$ exponenciálnì, co¾ tak pøíjemné není. Shròme, co jsme zjistili, do následující vìty: + +\s{Vìta:} +Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne +{\I $(1 - \varepsilon)$-aproximaci} problému batohu s $n$ pøedmìty v èase +$\O(n^3/\varepsilon)$. \bye