12-apx/12-apx.tex

   1 \input lecnotes.tex
   2 \prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda, M. Mare¹)}
   3
   4 \>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.
   5
   6 \h{Prvý spôsob: ©peciálny prípad}
   7
   8 \>È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.
   9
  10 \s{Problém: Maximálna nezávislá mno¾ina v strome (nie rozhodovacia)}
  11
  12 \>{\I Vstup:} zakorenený strom~$T$
  13
  14 \>{\I Výstup:} Maximálna (èo do poètu vrcholov) nezávislá mno¾ina vrcholov~$M$
  15
  16 \>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:
  17 \itemize\ibull
  18 \: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).
  19 \:Ak tam otec je, tak ho z~$M$ vyjmeme a~namiesto neho vlo¾íme~$l$ (veµkos» nezávislej mno¾iny sa nezmen¹ila).
  20 \endlist
  21 \>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.
  22
  23 \s{Algoritmus:}
  24 \algo
  25 \:Polo¾íme $M_1$:=$\{$listy stromu $T\}$.
  26 \:Polo¾íme $M_2$:=$\{$otcovia vrcholov z~$M_1\}$.
  27 \:Vrátime $M_1 \cup$ MaxNz$(T\setminus(M_1 \cup M_2)$.
  28 \endalgo
  29 \>{\I Poznámka:} Toto doká¾eme naprogramova» v $\O(n)$ (vrcholy máme vo fronte a prechádzame).
  30
  31 \s{Problém: Batoh}
  32
  33 \>Je daná mno¾ina $n$~predmetov s~hmotnos»ami $h_1,\ldots,h_n$
  34 a cenami $c_1,\ldots,c_n$ a~batoh, ktorý unesie hmotnos»~$H$. Nájdite takú
  35 podmno¾inu predmetov, ktorých celková hmotnos» je najviac~$H$ a~celková cena je
  36 maximálna mo¾ná.
  37
  38 \>Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
  39 Jednak místo rozhodovacího problému øe¹íme optimalizaèní, jednak pøedmìty
  40 mají ceny (pøedchozí verze odpovídala tomu, ¾e ceny jsou rovny hmotnostem).
  41 Uká¾eme si algoritmus pro øe¹ení tohoto obecného problému, jeho¾ èasová
  42 slo¾itost bude polynomiální v~poètu pøedmìtù~$n$ a souètu v¹ech cen~$C=\sum_i c_i$.
  43
  44 \>Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
  45 pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost
  46 podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$:
  47 Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe
  48 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
  49 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili
  50 (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$
  51 (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou mo¾ností si vybereme tu,
  52 která dává mno¾inu s~men¹í hmotností. Tedy:
  53 $$
  54 A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
  55 $$
  56 Tímto zpùsobem v~èase $\O(C)$ spoèteme jednu mno¾inu, v~èase $\O(nC)$ pak v¹echny.
  57
  58 \>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do batohu. To bude
  59 nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) < \infty$. Jeho nalezení nás stojí èas $\O(C)$.
  60
  61 \>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,
  62 aby si pro ka¾dé $A_k(c)$ pamatoval $B_k(c)$, co¾ bude index posledního pøedmìtu,
  63 který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
  64 poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
  65 a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
  66 prvku k~prvnímu.
  67
  68 \>Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í
  69 problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ( $C$~mu¾e být a¾ exponenciálnì
  70 velké vzhledem k~velikosti vstupu), ale pouze ve~velikosti èísel na~vstupu.
  71 Takovým algoritmùm se øíká {\I pseudopolynomiální.}
  72
  73 \s{Verze bez cen:} Na verzi s~cenami rovnými hmotnostem se dá pou¾ít
  74 i jiný algoritmus zalo¾ený na~dynamickém programování: poèítáme mno¾iny
  75 $Z_k$ obsahující v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá
  76 nìjaká podmno¾ina prvních~$k$ prvkù. Pøitom $Z_0=\{0\}$, $Z_k$
  77 spoèteme ze~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
  78 mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$.
  79
  80 \h{Druhý spôsob: Aproximácia}
  81
  82 \>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.
  83
  84 \s{Problém: Obchodný cestujúci}
  85
  86 \>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow {\bb R}^+_0$
  87
  88 \>{\I Vystup:} Hamiltonovská kru¾nica (v¹etky vrcholy grafu), a~to tá najkrat¹ia (podµa ohodnotenia).
  89
  90 \>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.
  91
  92 \>{\I a) trojuholníková nerovnos»:} $\forall x,y,z \in V: w(xz)\le w(xy)+w(yz)$
  93
  94 \>Existuje pekný algoritmus, ktory nájde Hamiltonovsku kru¾nicu, èo je
  95 maximálne dvakrát tak veµká ako optimálna.
  96
  97 \>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$.
  98
  99 \>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.
 100
 101 \>{\I b) bez~trojuholníkovej nerovnosti:}
 102
 103 \>Tu sa budeme naopak sna¾i» ukáza», ¾e ¾iaden polynomiálny aproximaèný algoritmus neexistuje.
 104
 105 \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$.
 106
 107 \proof Uká¾eme, ¾e v~tom prípade doká¾eme v~polynomiálnom èase nájs» Hamiltonovskú kru¾nicu.
 108
 109 \>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:
 110 \itemize\ibull
 111 \: $w(e) = 1$, ak $e \in E(G)$
 112 \: $w(e) = c \ll 1$, ak $e \in E(G)$
 113 \endlist
 114 \>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»
 115 $$
 116 \eqalign{
 117 (1+\varepsilon).n &< n-1+c \cr
 118 \varepsilon n+1 &< c
 119 }
 120 $$
 121 \>Ak by taký algoritmus existoval, tak na~neho máme polynomiálny algoritmus
 122 na~Hamiltonovsku kru¾nicu. Inak neexistuje ani pseudo-polynomialny algoritmus.
 123 \qed
 124
 125 \h{Aproximaèní schéma pro problém batohu}
 126
 127 \s{POZOR:} Verze algoritmu, kterou jsem øíkal na~pøedná¹ce, obsahovala jednu
 128 pomìrnì zásadní chybu, které jsem si nev¹iml: Verze se zaokrouhlováním dolù
 129 mohla produkovat nepøípustná (pøíli¹ tì¾ká) øe¹ení, verze se zaokrouhlováním nahoru pro zmìnu
 130 nìkdy spoèítala øe¹ení pøíli¹ daleká od~optima. Algoritmus lze opravit (budeme-li
 131 zvlá¹» zpracovávat lehké a tì¾ké pøedmìty), ale radìji budeme místo hmotností
 132 kvantovat ceny. Tak dojdeme k~následujícímu aproximaènímu algoritmu. --M.M.
 133
 134 Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$,
 135 pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen.
 136 Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
 137 ceny byly dìlitelné nìjakým èíslem~$p$, mohli bychom je tímto èíslem
 138 vydìlit. Tím bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
 139 stejná mno¾ina pøedmìtù jako u~zadání pùvodního.
 140
 141 Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky
 142 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í.
 143
 144 \s{Základní my¹lenka:}
 145
 146 Oznaèíme si $c_{max}$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M$
 147 a zobrazíme interval cen $[0, c_{max}]$ na $[0,M]$.
 148 Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé
 149 ceny zaokrouhlili na~násobky èísla $c_{max}/M$. Ka¾dé $c_i$ jsme tím
 150 zmìnili o~nejvý¹e $c_{max}/M$, celkovou cenu libovolné podmno¾iny pøedmìtù tedy
 151 nejvý¹e o~$n\cdot c_{max}/M$. Teï si je¹tì v¹imnìme, ¾e pokud ze~zadání odstraníme
 152 pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $OPT\ge c_{max}$,
 153 tak¾e chyba v~souètu je nejvý¹e $n\cdot OPT/M$. Má-li tato chyba být shora omezena
 154 $\varepsilon\cdot OPT$, musíme zvolit $M\ge n/\varepsilon$.
 155
 156 \s{Algoritmus:}
 157 \algo
 158 \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$.
 159 \:Spoèítáme $c_{max}=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$.
 160 \:Kvantujeme ceny: $\hat{c}_i = \lfloor c_i \cdot M/c_{max} \rfloor$.
 161 \:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$
 162 a pùvodní hmotnosti i kapacitu batohu.
 163 \:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání.
 164 \endalgo
 165
 166 \>Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
 167 se souètem cen $\hat{C}\le nM \le n^2/\varepsilon$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$.
 168 Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$.
 169
 170 Nejprve si rozmyslíme, jak dopadne optimální øe¹ení $OPT$ pùvodního zadání,
 171 kdy¾ ceny v~nìm pou¾itých pøedmìtù nakvantujeme (mno¾inu indexù tìchto pøedmìtù si oznaèíme~$Y$):
 172 $$
 173 \eqalign{
 174 \widehat{OPT} &= \sum_{i\in Y} \hat{c}_i =
 175 \sum_i \left\lfloor c_i\cdot {M\over c_{max}} \right\rfloor \ge
 176 \sum_i \left( c_i\cdot {M\over c_{max}} - 1 \right) \ge \cr
 177 &\ge
 178 \biggl(\sum_i c_i \cdot {M\over c_{max}}\biggr) - n =
 179 OPT \cdot {M\over c_{max}} - n.
 180 }
 181 $$
 182 Nyní naopak spoèítejme, jak dopadne øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
 183 na~pùvodní ceny (to je výsledek na¹eho algoritmu):
 184 $$
 185 \eqalign{
 186 ALG &= \sum_{i\in Q} c_i \ge
 187 \sum_i \hat{c}_i \cdot {c_{max}\over M} =
 188 \biggl(\sum_i \hat{c}_i\biggr) \cdot {c_{max}\over M} \ge^*
 189 \widehat{OPT} \cdot {c_{max}\over M}.
 190 }
 191 $$
 192 Nerovnost $\ge^*$ platí proto, ¾e $\sum_{i\in Q} \hat{c}_i$ je optimální øe¹ení
 193 kvantované úlohy, zatímco $\sum_{i\in Y} \hat{c}_i$ je nìjaké dal¹í øe¹ení té¾e úlohy,
 194 které nemù¾e být lep¹í. Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
 195 $$
 196 \eqalign{
 197 ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} \ge
 198 OPT - {n\cdot c_{max}\over n / \varepsilon} \ge OPT - \varepsilon c_{max} \ge \cr
 199 &\ge OPT - \varepsilon OPT = (1-\varepsilon)\cdot OPT.
 200 }
 201 $$
 202 Algoritmus tedy v¾dy vydá øe¹ení, které je nejvý¹e $(1-\varepsilon)$-krát hor¹í ne¾ optimum,
 203 a~doká¾e to pro libovolné~$\varepsilon$ v~èase polynomiálním v~$n$. Takovému algoritmu øíkáme
 204 {\I polynomiální aproximaèní schéma} (jinak té¾ PTAS\foot{Polynomial-Time Approximation Scheme}).
 205 V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e
 206 schéma je {\I plnì polynomiální} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation Scheme}).
 207
 208 \bye