From b22f556c389cf5ca14786b3fc614fc74b8ad9a8b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 15 Jan 2012 15:19:38 +0100 Subject: [PATCH] APX: Aproximace problemu batohu --- 9-apx/9-apx.tex | 214 +++++++++++++++++++++++------------------------- 1 file changed, 101 insertions(+), 113 deletions(-) diff --git a/9-apx/9-apx.tex b/9-apx/9-apx.tex index c23cb22..c382f01 100644 --- a/9-apx/9-apx.tex +++ b/9-apx/9-apx.tex @@ -185,97 +185,77 @@ dob \h{Aproximace problému obchodního cestujícího} -\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. +V~{\I problému obchodního cestujícího} je zadán neorientovaný graf~$G$, jeho¾ +hrany jsou ohodnoceny délkami~$\ell: E(G) \rightarrow {\bb R}^+_0$. V~tomto +grafu chceme nalézt nejkrat¹í z~hamiltonovských kru¾nic, tedy tìch, které nav¹tíví +v¹echny vrcholy. + +Není pøekvapivé, ¾e tento problém je tì¾ký -- u¾ sama existence hamiltonovské +kru¾nice je \NP-úplná. Uká¾eme ov¹em, ¾e pokud je graf úplný a platí v~nìm trojúhelníková +nerovnost (tj. $\ell(x,z) \le \ell(x,y) + \ell(y,z)$ pro v¹echny trojice vrcholù $x,y,z$), +mù¾eme problém obchodního cestujícího 2-aproximovat, tedy najít v~polynomiálním +èase kru¾nici, která je pøinejhor¹ím dvakrát del¹í ne¾ ta optimální. + +Grafy s~trojúhelníkovou nerovností pøitom nejsou nijak neobvyklé -- odpovídají +toti¾ v¹em koneèným metrickým prostorùm. + +Algoritmus bude snadný: Najdeme nejmen¹í kostru a obchodnímu cestujícímu poradíme, +a» jde po~ní. To mù¾eme popsat napøíklad tak, ¾e kostru zakoøeníme, prohledáme ji +do hloubky a zaznamenáme, jak jsme procházeli hranami. Ka¾dou hranou kostry tedy +projdeme dvakrát -- jednou dolù, podruhé nahoru. Tím v¹ak nedostaneme kru¾nici, +nýbr¾ jen nìjaký uzavøený sled, proto¾e vrcholy nav¹tìvujeme vícekrát. Sled tedy +upravíme tak, ¾e kdykoliv se dostává do ji¾ nav¹tíveného vrcholu, pøeskoèí ho +a pøesune se a¾ do nejbli¾¹ího dal¹ího nenav¹tíveného. Tím ze sledu vytvoøíme +hamiltonovskou kru¾nici a jeliko¾ v~grafu platí trojúhelníková nerovnost, +celková délka nevzrostla. (Poøadí vrcholù na kru¾nici mù¾eme získat také tak, +¾e bìhem prohledávání budeme vypisovat vrcholy v~preorderu. Rozmyslete si, +¾e je toté¾.) + +\s{Vìta:} Nalezená kru¾nice není del¹í ne¾ dvojnásobek optima. + +\proof +Oznaème $T$ délku minimální kostry, $A$ délku kru¾nice vydané na¹ím algoritmem +a $O$ (optimum) délku nejkrat¹í hamiltonovské kru¾nice. Z~toho, jak jsme kru¾nici +vytvoøili, víme, ¾e $A\le 2T$. Platí ov¹em také $T\le O$, jeliko¾ z~ka¾dé +hamiltonovské kru¾nice vznikne vynecháním hrany kostra a ta nemù¾e být men¹í +ne¾ minimální kostra. Slo¾ením obou nerovností získáme $A\le 2T\le 2O$. +\qed + +Sestrojili jsme tedy 2-aproximaèní algoritmus pro problém obchodního cestujícího. +Dodejme je¹tì, ¾e trochu slo¾itìj¹ím trikem lze tento problém $1.5$-aproximovat +a ¾e v~nìkterých metrických prostorech (tøeba v~euklidovské rovinì) lze v~polynomiálním +èase najít $(1+\varepsilon)$-aproximaci pro libovolné $\varepsilon>0$. Ov¹em èím +men¹í~$\varepsilon$, tím déle algoritmus pobì¾í. + +Bez trojúhelníkové nerovnosti ov¹em ná¹ problém aproximovat vùbec nejde: \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$, kdy¾ $e \in E(G)$ -\: $w(e) = c \gg 1$, kdy¾ $e \not\in E(G)$ -\endlist - -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)\cdot n &< n-1+c \cr -\varepsilon n+1 &< c -} -$$ -Kdyby takový algoritmus existoval, máme polynomiální algoritmus -na~hamiltonovskou kru¾nici. +$(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího +bez~trojúhelníkové nerovnosti, pak je $\P = \NP$. + +\proof Uká¾eme, ¾e pomocí takového aproximaèního algoritmu doká¾eme v~polynomiálním +èase zjistit, zda v grafu existuje hamiltonovská kru¾nice, co¾ je \NP-úplný problém. + +Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici (zkrácenì HK). +Doplníme $G$ na~úplný graf~$G'$. Délky v¹ech pùvodních hran nastavíme na~1, novým +hranám pøisoudíme délku~$c$ pro nìjakou vhodnì zvolenou konstantu~$c\gg 1$. + +V~grafu~$G'$ jistì alespoò jedna HK existuje. Z~ka¾dé HK v~$G$ se stala +HK v~$G'$ o~délce pøesnì~$n$. V¹echny ostatní HK v~$G'$ obsahují alespoò +jednu hranu, která nepochází z~$G$, tak¾e mají délku alespoò $n-1+c$. + +Nastavíme konstantu~$c$ tak, aby i pøes zkreslení zpùsobené aproximací +bylo podle odpovìdi algoritmu poznat, zda nìjaká kru¾nice délky~$n$ existuje. +Potøebujeme, aby platilo $(1+\varepsilon)\cdot n < n-1+c$, tedy staèí zvolit +$c$ vìt¹í ne¾ $\varepsilon n + 1$. + +Pøidali jsme tedy polynomiálnì mnoho hran s~polynomiálnì velkým ohodnocením, +tak¾e graf~$G'$ je polynomiálnì velký vzhledem ke~$G$ a ná¹ algoritmus rozhoduje +existenci HK v~polynomiálním èase. \qed -\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{Poznámka:} Podobnì mù¾eme dokázat, ¾e pokud $\P\ne\NP$, neexistuje ani +pseudopolynomiální algoritmus. Staèí pùvodním hranám pøiøadit váhu~1 a novým váhu~2. \h{Aproximaèní schéma pro problém batohu} @@ -287,7 +267,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 +nìjak zaokrouhlit. Optimální øe¹ení nové úlohy pak sice nemusí 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:} @@ -295,22 +275,24 @@ n \def\cmax{c_{\rm max}} Oznaèíme si $\cmax$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < \cmax$ -a zobrazíme interval cen $[0, \cmax]$ na $[0,M]$ (tedy ka¾dou cenu znásobíme -$M/\cmax$). +a zobrazíme interval cen $[0, \cmax]$ na $\{0, \ldots, M \}$ (tedy ka¾dou cenu znásobíme pomìrem +$M/\cmax$ a zaokrouhlíme). Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé ceny zaokrouhlili na~násobky èísla $\cmax/M$ (prvky z intervalu $[i\cdot \cmax/M,(i+1)\cdot \cmax/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím tedy zmìnili o~nejvý¹e $\cmax/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak -nejvý¹e o~$n\cdot \cmax/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 $\\ge \cmax$, -tak¾e chyba v~souètu je nejvý¹e $n\cdot \/M$. Má-li tato chyba být shora omezena -$\varepsilon\cdot \$, 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.} +nejvý¹e o~$n\cdot \cmax/M$. Navíc odstraníme-li ze vstupu +pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $c^* \ge \cmax$, +tak¾e chyba na¹í aproximace nepøesáhne $n\cdot c^*/M$. Má-li tato chyba být shora omezena +$\varepsilon\cdot c^*$, musíme zvolit $M\ge n/\varepsilon$. + +Na~této my¹lence \uv{kvantování cen} je zalo¾en následující algoritmus. \s{Algoritmus:} \algo \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$. \:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$. -\:Kvantujeme ceny: $\forall i: \hat{c}_i \leftarrow \lfloor c_i \cdot M/\cmax \rfloor$. +\:Kvantujeme ceny: Pro $i=1,\ldots,n$ polo¾íme $\hat{c}_i \= \lfloor c_i \cdot M/\cmax \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í. @@ -321,15 +303,21 @@ Kroky 1--3 a 5 jist 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$. -Nech» pùvodní úloha má nìjaké optimální øe¹ení~$P$ s~cenou $c(P)$. Rozmysleme -si, jakou cenu $\hat{c}(P)$ bude tato mno¾ina pøedmìtù mít v~nakvantovaném zadání: +Oznaème~$P$ mno¾inu pøedmìtù pou¾itých v~optimálním øe¹ení pùvodní úlohy a $c(P)$ +cenu tohoto øe¹ení. Podobnì~$Q$ bude mno¾ina pøedmìtù v~optimálním øe¹ení +nakvantované úlohy a $\hat{c}(Q)$ jeho hodnota v~nakvantovaných cenách. Potøebujeme +odhadnout ohodnocení mno¾iny~$Q$ v~pùvodních cenách, tedy $c(Q)$, a~srovnat +ho s~$c(P)$. + +Nejprve uká¾eme, jakou cenu má optimální øe¹ení~$P$ pùvodní úlohy +v~nakvantovaných cenách: $$ \eqalign{ \hat{c}(P) &= \sum_{i\in P} \hat{c}_i = -\sum_i \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge -\sum_i \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr +\sum_{i\in P} \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge +\sum_{i\in P} \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr &\ge -\biggl(\sum_i c_i \cdot {M\over \cmax}\biggr) - n = +\left(\sum_{i\in P} c_i \cdot {M\over \cmax}\right) - n = c(P) \cdot {M\over \cmax} - n. } $$ @@ -338,36 +326,36 @@ na~p $$ \eqalign{ c(Q) &= \sum_{i\in Q} c_i \ge -\sum_i \hat{c}_i \cdot {\cmax\over M} = -\biggl(\sum_i \hat{c}_i\biggr) \cdot {\cmax\over M} \ge +\sum_{i\in Q} \hat{c}_i \cdot {\cmax\over M} = +\left(\sum_i \hat{c}_i\right) \cdot {\cmax\over M} = +\hat{c}(Q) \cdot {\cmax\over M} \ge \hat{c}(P) \cdot {\cmax\over M}. } $$ -Poslední nerovnost platí proto, ¾e $\sum_{i\in Q} \hat{c}_i$ je optimální øe¹ení -kvantované úlohy, zatímco $\sum_{i\in P} \hat{c}_i$ je nìjaké dal¹í øe¹ení té¾e úlohy, -které nemù¾e být lep¹í.% +Poslední nerovnost platí proto, ¾e $\hat{c}(Q)$ je optimální øe¹ení kvantované úlohy, +zatímco $\hat{c}(P)$ je nìjaké dal¹í øe¹ení té¾e úlohy, které nemù¾e být lep¹í.% \foot{Zde nás zachraòuje, ¾e aèkoliv u~obou úloh le¾í optimum obecnì jinde, obì mají stejnou mno¾inu {\I pøípustných øe¹ení,} tedy tìch, která se vejdou do batohu. Kdybychom místo cen kvantovali hmotnosti, nebyla by to pravda a algoritmus by nefungoval.} Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$: $$ \eqalign{ -c(Q) &\ge \biggl( { c(P) \cdot M\over \cmax} - n\biggr) \cdot {\cmax\over M} \ge +c(Q) &\ge \left( { c(P) \cdot M\over \cmax} - n\right) \cdot {\cmax\over M} \ge c(P) - {n\cdot \cmax\over n / \varepsilon} \ge c(P) - \varepsilon \cmax \ge \cr &\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P). } $$ -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~závislosti na~$1/\varepsilon$, tak¾e -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: +Dokázali jsme tedy tuto vìtu: \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)$. +Dodejme je¹tì, ¾e algoritmùm, které dovedou pro ka¾dé $\varepsilon > 0$ najít +v~polynomiálním èase $(1-\varepsilon)$-aproximaci optimálního øe¹ení, øíkáme +{\I polynomiální aproximaèní schémata} (PTAS -- 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í} (FPTAS -- Fully Polynomial-Time Approximation Scheme). + \bye -- 2.39.2