2 \prednaska{9}{Co si poèít s tì¾kým problémem}{}
4 V~pøedchozí kapitole jsme zjistili, ¾e leckteré rozhodovací problémy
5 jsou \NP-úplné. Z~toho plyne, ¾e jsou ekvivalentní, ale bohu¾el také,
6 ¾e ani jeden z~nich zatím neumíme vyøe¹it v~polynomiálním èase.
8 Èasto se stane, ¾e problém, který v~¾ivotì potkáme, patøí mezi \NP-úplné.
9 Pøesnìji øeèeno spí¹ ne¾ s~rozhodovacím problémem se potkáme s~problémem
10 {\I optimalizaèním,} ve~kterém jde o~nalezení {\I nejlep¹ího} objektu
11 s~danou vlastností. To mù¾e být tøeba nejvìt¹í nezávislá mno¾ina v~grafu
12 nebo obarvení grafu nejmen¹ím mo¾ným poètem barev. Kdybychom umìli efektivnì
13 øe¹it optimalizaèní problém, umíme samozøejmì øe¹it i pøíslu¹ný rozhodovací,
14 tak¾e pokud $\P\ne\NP$, jsou i optimalizaèní problémy tì¾ké.
16 Ale co naplat, svìt nám takové úlohy pøedkládá a my je potøebujeme vyøe¹it.
17 Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto mo¾nosti, co si
21 \:{\I Spokojit se s~málem.} Nejsou vstupy, pro které problém potøebujeme
22 øe¹it, dostateènì malé, abychom si mohli dovolit pou¾ít algoritmus
23 s~exponenciální slo¾itostí? Zvlá¹» kdy¾ takový algoritmus vylep¹íme
24 proøezáváním neperspektivních vìtví výpoètu a tøeba ho i paralelizujeme.
25 \:{\I Vyøe¹it speciální pøípad.} Nemají na¹e vstupy nìjaký speciální
26 tvar, kterého bychom mohli vyu¾ít? Grafové problémy jsou èasto v~\P{}
27 tøeba pro stromy nebo i obecnìji pro bipartitní grafy. U~èíselných
28 problémù zase nìkdy pomù¾e, jsou-li èísla na vstupu dostateènì malá.
29 \:{\I Øe¹ení aproximovat.} Opravdu potøebujeme optimální øe¹ení? Nestaèilo
30 by nám o~kousíèek hor¹í? Èasto existuje polynomiální algoritmus, který
31 nalezne nejhùøe $c$-krát hor¹í øe¹ení ne¾ je optimum, kde $c$~je konstanta.
32 \:{\I Pou¾ít heuristiku.} Neumíme-li nic lep¹ího, mù¾eme sáhnout po~nìkteré
33 z~mnoha heuristických technik, které sice nic nezaruèují, ale obvykle
34 nìjaké uspokojivé øe¹ení najdou. Mù¾e pomoci tøeba hladový algoritmus
35 nebo genetické algoritmy. Èasto platí, ¾e èím déle heuristiku necháme
36 bì¾et, tím lep¹í øe¹ení najde.
37 \:{\I Kombinace pøístupù.} Mnohdy lze pøedchozí pøístupy kombinovat:
38 napøíklad pou¾ít aproximaèní algoritmus a poté jeho výsledek
39 je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které od~optima
40 zaruèenì není moc daleko, a~pokud budeme mít ¹tìstí, bude se od~nìj li¹it
44 \>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.
46 \h{Nejvìt¹í nezávislá mno¾ina ve stromu}
48 Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je snadné, pokud graf je strom.
50 \s{Lemma:} Buï~$T$ zakoøenìný strom a $\ell$ jeho libovolný list. Pak alespoò jedna
51 z~nejvìt¹ích nezávislých mno¾in obsahuje~$\ell$.
54 Mìjme nejvìt¹í nezávislou mno¾inu~$M$, která list~$\ell$ neobsahuje. Podívejme
55 se na otce~$p$ listu~$\ell$ (kdyby neexistoval, je celý strom jednovrcholový
56 a tvrzení triviální). Le¾í~$p$ v~$M$? Pokud ne, mohli bychom do~$M$ pøidat
57 list~$\ell$ a dostali bychom vìt¹í nezávislou mno¾inu. V~opaèném pøípadì z~$M$
58 odebereme otce~$p$ a nahradíme ho listem~$\ell$, èím¾ dostaneme stejnì velkou
59 nezávislou mno¾inu obsahující~$\ell$.
62 Algoritmus bude pøímoèaøe pou¾ívat toto lemma. Dostane na vstupu strom,
63 ten zakoøení a zvolí libovolný list. Tento list umístí do nezávislé mno¾iny
64 a jeho otce odebere, proto¾e se nemù¾e v~nezávislé mno¾inì vyskytovat.
65 Toto bude opakovat, dokud nìjaké vrcholy zbývají. (Graf se v~prùbìhu mù¾e
66 rozpadnout na více komponent, ale to nevadí.)
68 Tento algoritmus jistì pracuje v~polynomiálním èase. ©ikovnou implementací
69 mù¾eme slo¾itost sní¾it a¾ na lineární. Napøíklad tak, ¾e budeme udr¾ovat seznam
70 listù. My si uká¾eme jinou lineární implementaci zalo¾enou na prohledávání do hloubky.
71 Bude pracovat s~polem znaèek~$M$, v~nìm¾ na poèátku bude v¹ude \<false> a postupnì
72 obdr¾í \<true> v¹echny prvky hledané nezávislé mno¾iny.
75 \algin Strom~$T$ s~koøenem~$v$, pole znaèek~$M$.
77 \:Pokud je~$v$ list, skonèíme.
78 \:Pro v¹echny syny~$w$ vrcholu~$v$:
79 \::Zavoláme se rekurzivnì na podstrom s~koøenem~$w$.
80 \::Pokud $M[w]=\<true>$, polo¾íme $M[v] \= \<false>$.
83 \h{Barvení intervalového grafu}
85 Mìjme~$n$ pøedná¹ek s~urèenými èasy zaèátku a konce. Chceme je rozvrhnout
86 do co~nejmen¹ího poètu poslucháren tak, aby nikdy neprobíhaly dvì pøedná¹ky
87 naráz v~jedné místnosti.
89 Chceme tedy obarvit co nejmen¹ím poètem barev graf, jeho¾ vrcholy jsou èasové
90 intervaly a dvojice intervalù je spojena hranou, pokud má neprázdný prùnik.
91 Takovým grafùm se øíká {\I intervalové} a pro jejich barvení existuje pìkný
92 polynomiální algoritmus.
94 Podobnì jako jsme geometrické problémy øe¹ili zametáním roviny, zde budeme
95 \uv{zametat pøímku bodem}, tedy procházet ji zleva doprava, a~v¹ímat si
96 událostí, co¾ budou zaèátky a konce intervalù. Pro jednoduchost pøedpokládejme,
97 ¾e v¹echny souøadnice zaèátkù a koncù jsou navzájem rùzné.
99 Kdykoliv interval zaène, pøidìlíme mu barvu. A¾ skonèí, o~barvì si poznamenáme,
100 ¾e je momentálnì volná, a~dal¹ím intervalùm budeme pøednostnì pøidìlovat
101 volné barvy. Øeèeno v~pseudokódu:
103 \algo{BarveníIntervalù}
104 \algin Intervaly $\left[ x_1, y_1 \right], \ldots, \left[ x_n, y_n \right]$.
105 \:$b \= 0$ \cmt{poèet zatím pou¾itých barev}
106 \:$B \= \emptyset$ \cmt{které barvy jsou momentálnì volné}
107 \:Setøídíme mno¾inu v¹ech $x_i$ a $y_i$.
108 \:Procházíme v¹echna $x_i$ a $y_i$ ve~vzestupném poøadí:
109 \::Narazíme-li na $x_i$:
110 \:::Je-li $B\ne\emptyset$, odebereme jednu barvu z~$B$ a ulo¾íme ji do~$c_i$.
111 \:::Jinak $b\=b+1$ a $c_i\=b$.
112 \::Narazíme-li na $y_i$:
113 \:::Vrátíme barvu $c_i$ do~$B$.
114 \algout Obarvení $c_1,\ldots,c_n$.
118 Tento algoritmus má èasovou slo¾itost $\O(n\log n)$ kvùli tøídìní souøadnic.
119 Samotné obarvování je lineární.
121 Je¹tì ov¹em potøebujeme dokázat, ¾e jsme pou¾ili minimální mo¾ný poèet barev.
122 Uva¾ujme okam¾ik, kdy promìnná~$b$ naposledy vzrostla. Tehdy zaèal interval
123 a mno¾ina~$B$ byla prázdná, co¾ znamená, ¾e jsme $b-1$ pøedchozích barev museli
124 pøidìlit intervalùm, je¾ zaèaly a dosud neskonèily. Existuje tedy $b$ rùzných
125 intervalù, které mají spoleèný bod (v~grafu tvoøí kliku), tak¾e ka¾dé obarvení
126 potøebuje alespoò~$b$ barev.
128 \h{Problém batohu s~malými èísly}
130 Pøipomeòme si {\I problém batohu.} Jeho optimalizaèní verze vypadá takto:
131 Je dána mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ a cenami $c_1,\ldots,c_n$
132 a nosnost batohu~$H$. Hledáme podmno¾inu pøedmìtù~$P \subseteq \{1,\ldots,n\}$,
133 která se vejde do batohu (tedy $h(P)=\sum_{i\in P} h_i \le H$) a její cena
134 $c(P) = \sum_{i\in P} c_i$ je nejvìt¹í mo¾ná.
136 Uká¾eme algoritmus, jeho¾ èasová slo¾itost bude polynomiální v~poètu
137 pøedmìtù~$n$ a souètu v¹ech cen $C=\sum_i c_i$.
139 Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
140 pøedmìtù. Oznaème $A_k(c)$ (kde $0\le c\le C$) minimum z~hmotností tìch podmno¾in
141 jejich¾ cena je právì~$c$; pokud ¾ádná taková podmno¾ina neexistuje, polo¾íme $A_k(c)=\infty$.
143 Tato $A_k$ spoèteme indukcí podle~$k$: Pro $k=0$ je
144 urèitì $A_0(0)=0$ a $A_0(1)=\ldots=A_0(C)=\infty$. Pokud ji¾ známe
145 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
146 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili,
147 a~pak je $A_k(c)=A_{k-1}(c)$, nebo pou¾ili, a~tehdy bude $A_k(c) =
148 A_{k-1}(c-c_k) + h_k$ (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou
149 mo¾ností si vybereme tu, která dává mno¾inu s~men¹í hmotností:
151 A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
153 Pøechod od $A_{k-1}$ k~$A_k$ tedy trvá $\O(C)$, od~$A_1$ a¾ k~$A_n$ se dopoèítáme v~èase $\O(Cn)$.
155 Jakmile získáme~$A_n$, známe pro ka¾dou cenu pøíslu¹nou nejlehèí podmno¾inu.
156 Maximální cena mno¾iny, která se vejde do batohu, je tedy nejvìt¹í~$c^*$, pro nì¾
157 je $A_n(c^*) \le H$. Jeho nalezení nás stojí èas $\O(C)$.
159 Zbývá zjistit, které pøedmìty do~nalezené mno¾iny patøí. Upravíme algoritmus,
160 aby si pro ka¾dé $A_k(c)$ pamatoval je¹tì $B_k(c)$, co¾ bude index posledního pøedmìtu,
161 který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
162 poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
163 a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
166 Máme tedy algoritmus, který vyøe¹í problém batohu v~èase $\O(nC)$. Tato funkce
167 ov¹em není polynomem ve~velikosti vstupu, jeliko¾ reprezentujeme-li vstup binárnì,
168 $C$~mù¾e být a¾ exponenciálnì velké vzhledem k~délce jeho zápisu. To je pìkný
169 pøíklad tzv. {\I pseudopolynomiálního} algoritmu, tedy algoritmu, jeho¾ slo¾itost
170 je polynomem v~poètu èísel na vstupu a jejich velikosti. Pro nìkteré \NP-úplné
171 problémy takové algoritmy existují, pro jiné (napø. pro nezávislou mno¾inu) by
172 z~jejich existence plynulo $\P=\NP$.
174 \s{Verze bez cen:} Jednodu¹¹í verzi problému batohu, která nerozli¹uje mezi
175 hmotnostmi a cenami, zvládneme i jiným algoritmem, opìt zalo¾eným na dynamickém
178 Indukcí podle~$k$ vytváøíme mno¾iny~$Z_k$ obsahující v¹echny hmotnosti
179 men¹í ne¾~$H$, kterých nabývá nìjaká podmno¾ina prvních~$k$ prvkù. Jistì je $Z_0=\{0\}$.
180 Podobnou úvahou jako v~pøedchozím algoritmu dostaneme, ¾e ka¾dou dal¹í~$Z_k$ mù¾eme
181 zapsat jako sjednocení $Z_{k-1}$ s~kopií $Z_{k-1}$ posunutou o~$h_k$, ignorujíce hodnoty
182 vìt¹í ne¾~$H$. Nakonec ze~$Z_n$ vyèteme výsledek.
184 V¹echny mno¾iny pøitom mají nejvý¹e~$H+1$ prvkù, tak¾e pokud si je budeme udr¾ovat
185 jako setøídìné seznamy, spoèítáme sjednocení sléváním v~èase $\O(H)$ a celý algoritmus
186 dobìhne v~èase $\O(Hn)$.
188 \h{Aproximace problému obchodního cestujícího}
190 V~{\I problému obchodního cestujícího} je zadán neorientovaný graf~$G$, jeho¾
191 hrany jsou ohodnoceny délkami $\ell(e)\ge 0$. V~tomto
192 grafu chceme nalézt nejkrat¹í z~hamiltonovských kru¾nic, tedy tìch, které nav¹tíví
195 Není pøekvapivé, ¾e tento problém je tì¾ký -- u¾ sama existence hamiltonovské
196 kru¾nice je \NP-úplná. Uká¾eme ov¹em, ¾e pokud je graf úplný a platí v~nìm trojúhelníková
197 nerovnost (tj. $\ell(x,z) \le \ell(x,y) + \ell(y,z)$ pro v¹echny trojice vrcholù $x,y,z$),
198 mù¾eme problém obchodního cestujícího 2-aproximovat, tedy najít v~polynomiálním
199 èase kru¾nici, která je pøinejhor¹ím dvakrát del¹í ne¾ ta optimální.
201 Grafy s~trojúhelníkovou nerovností pøitom nejsou nijak neobvyklé -- odpovídají
202 toti¾ koneèným metrickým prostorùm.
204 Algoritmus bude snadný: Najdeme nejmen¹í kostru a obchodnímu cestujícímu poradíme,
205 a» ji obejde. To mù¾eme popsat napøíklad tak, ¾e kostru zakoøeníme, prohledáme ji
206 do hloubky a zaznamenáme, jak jsme procházeli hranami. Ka¾dou hranou kostry pøitom
207 projdeme dvakrát -- jednou dolù, podruhé nahoru. Tím v¹ak nedostaneme kru¾nici,
208 nýbr¾ jen nìjaký uzavøený sled, proto¾e vrcholy nav¹tìvujeme vícekrát. Sled tedy
209 upravíme tak, ¾e kdykoliv se dostává do ji¾ nav¹tíveného vrcholu, pøeskoèí ho
210 a pøesune se a¾ do nejbli¾¹ího dal¹ího nenav¹tíveného. Tím ze sledu vytvoøíme
211 hamiltonovskou kru¾nici a jeliko¾ v~grafu platí trojúhelníková nerovnost,
212 celková délka nevzrostla. (Poøadí vrcholù na kru¾nici mù¾eme získat také tak,
213 ¾e bìhem prohledávání budeme vypisovat vrcholy v~preorderu. Rozmyslete si,
216 \s{Vìta:} Nalezená kru¾nice není del¹í ne¾ dvojnásobek optima.
219 Oznaème $T$ délku minimální kostry, $A$ délku kru¾nice vydané na¹ím algoritmem
220 a $O$ (optimum) délku nejkrat¹í hamiltonovské kru¾nice. Z~toho, jak jsme kru¾nici
221 vytvoøili, víme, ¾e $A\le 2T$. Platí ov¹em také $T\le O$, jeliko¾ z~ka¾dé
222 hamiltonovské kru¾nice vznikne vynecháním hrany kostra a ta nemù¾e být men¹í
223 ne¾ minimální kostra. Slo¾ením obou nerovností získáme $A\le 2T\le 2O$.
226 Sestrojili jsme tedy 2-aproximaèní algoritmus pro problém obchodního cestujícího.
227 Dodejme je¹tì, ¾e trochu slo¾itìj¹ím trikem lze tento problém $1.5$-aproximovat
228 a ¾e v~nìkterých metrických prostorech (tøeba v~euklidovské rovinì) lze v~polynomiálním
229 èase najít $(1+\varepsilon)$-aproximaci pro libovolné $\varepsilon>0$. Ov¹em èím
230 men¹í~$\varepsilon$, tím déle algoritmus pobì¾í.
232 Trojúhelníková nerovnost nicménì byla pro tento algoritmus naprosto nezbytná.
233 To není náhoda -- hned doká¾eme, ¾e bez tohoto pøedpokladu je libovolná
234 aproximace stejnì tì¾ká jako pøesné øe¹ení.
236 \s{Vìta:} Pokud pro~nìjaké reálné~$t\ge 1$ existuje polynomiální
237 $t$-aproximaèní algoritmus pro~problém obchodního cestujícího
238 bez~trojúhelníkové nerovnosti, pak je $\P = \NP$.
240 \proof Uká¾eme, ¾e pomocí takového aproximaèního algoritmu doká¾eme v~polynomiálním
241 èase zjistit, zda v grafu existuje hamiltonovská kru¾nice, co¾ je \NP-úplný problém.
243 Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici (zkrácenì HK).
244 Doplníme $G$ na~úplný graf~$G'$. V¹em pùvodním hranám nastavíme délku na~1,
245 tìm novým na nìjaké dost velké èíslo~$c$. Kolik to bude, urèíme za chvíli.
247 Graf~$G'$ je úplný, tak¾e v~nìm urèitì nìjaké HK existují. Ty, které se
248 vyskytují i v~pùvodním grafu~$G$, mají délku pøesnì~$n$. Jakmile ale
249 pou¾ijeme jedinou hranu, která z~$G$ nepochází, vzroste délka kru¾nice
252 Podle délky nejkrat¹í HK tedy doká¾eme rozpoznat, zda existuje HK v~$G$.
253 Potøebujeme ov¹em zjistit i pøes zkreslení zpùsobené aproximací. Musí tedy
254 platit $tn < n-1+c$. To snadno zajistíme volbou hodnoty~$c$ vìt¹í ne¾ $(t-1) n + 1$.
256 Na¹e konstrukce pøidala polynomiálnì mnoho hran s~polynomiálnì velkým ohodnocením,
257 tak¾e graf~$G'$ je polynomiálnì velký vzhledem ke~$G$. Rozhodujeme tedy
258 existenci HK v~polynomiálním èase a $\P=\NP$.
261 \s{Poznámka:} Podobnì mù¾eme dokázat, ¾e pokud $\P\ne\NP$, neexistuje pro problém
262 obchodního cestujícího ani pseudopolynomiální algoritmus. Staèí pùvodním hranám
263 pøiøadit délku~1 a novým délku~2.
265 \h{Aproximaèní schéma pro problém batohu}
267 Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$,
268 pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen.
269 Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
270 ceny byly násobky nìjakého èísla~$p$, mohli bychom je tímto èíslem
271 vydìlit. Tak bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
272 stejná mno¾ina pøedmìtù jako u~zadání pùvodního.
274 Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky
275 nìjak zaokrouhlit. Optimální øe¹ení nové úlohy pak sice nemusí odpovídat optimálnímu
276 øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací.
278 \def\cmax{c_{\rm max}}
280 \s{Základní my¹lenka:}
281 Oznaèíme $\cmax$ maximum z~cen~$c_i$. Zvolíme nìjaké pøirozené èíslo~$M < \cmax$
282 a zobrazíme interval cen $[0, \cmax]$ na $\{0, \ldots, M \}$ (tedy ka¾dou cenu znásobíme pomìrem
283 $M/\cmax$ a zaokrouhlíme).
284 Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé
285 ceny zaokrouhlili na~násobky èísla $\cmax/M$ (prvky z intervalu
286 $[i\cdot \cmax/M,(i+1)\cdot \cmax/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím
287 tedy zmìnili o~nejvý¹e $\cmax/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak
288 nejvý¹e o~$n\cdot \cmax/M$. Navíc odstraníme-li ze vstupu
289 pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $c^* \ge \cmax$,
290 tak¾e chyba na¹í aproximace nepøesáhne $n\cdot c^*/M$. Má-li tato chyba být shora omezena
291 $\varepsilon\cdot c^*$, musíme zvolit $M\ge n/\varepsilon$.
293 Na~této my¹lence \uv{kvantování cen} je zalo¾en následující algoritmus.
295 \algo{AproximaceBatohu}
296 \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$.
297 \:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$.
298 \:Kvantujeme ceny: Pro $i=1,\ldots,n$ polo¾íme $\hat{c}_i \= \lfloor c_i \cdot M/\cmax \rfloor$.
299 \:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$
300 a pùvodní hmotnosti i kapacitu batohu.
301 \:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání.
305 Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
306 se souètem cen $\hat{C}\le nM = \O(n^2/\varepsilon)$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$.
307 Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$.
309 Oznaème~$P$ mno¾inu pøedmìtù pou¾itých v~optimálním øe¹ení pùvodní úlohy a $c(P)$
310 cenu tohoto øe¹ení. Podobnì~$Q$ bude mno¾ina pøedmìtù v~optimálním øe¹ení
311 nakvantované úlohy a $\hat{c}(Q)$ jeho hodnota v~nakvantovaných cenách. Potøebujeme
312 odhadnout ohodnocení mno¾iny~$Q$ v~pùvodních cenách, tedy $c(Q)$, a~srovnat
315 Nejprve uká¾eme, jakou cenu má optimální øe¹ení~$P$ pùvodní úlohy
316 v~nakvantovaných cenách:
319 \hat{c}(P) &= \sum_{i\in P} \hat{c}_i =
320 \sum_{i\in P} \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge
321 \sum_{i\in P} \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr
323 \left(\sum_{i\in P} c_i \cdot {M\over \cmax}\right) - n =
324 c(P) \cdot {M\over \cmax} - n.
327 Nyní naopak spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
328 na~pùvodní ceny (to je výsledek na¹eho algoritmu):
331 c(Q) &= \sum_{i\in Q} c_i \ge
332 \sum_{i\in Q} \hat{c}_i \cdot {\cmax\over M} =
333 \left(\sum_i \hat{c}_i\right) \cdot {\cmax\over M} =
334 \hat{c}(Q) \cdot {\cmax\over M} \ge
335 \hat{c}(P) \cdot {\cmax\over M}.
338 Poslední nerovnost platí proto, ¾e $\hat{c}(Q)$ je optimální øe¹ení kvantované úlohy,
339 zatímco $\hat{c}(P)$ je nìjaké dal¹í øe¹ení té¾e úlohy, které nemù¾e být lep¹í.%
340 \foot{Zde nás zachraòuje, ¾e aèkoliv u~obou úloh le¾í optimum obecnì jinde, obì mají
341 stejnou mno¾inu {\I pøípustných øe¹ení,} tedy tìch, která se vejdou do batohu. Kdybychom
342 místo cen kvantovali hmotnosti, nebyla by to pravda a algoritmus by nefungoval.}
343 Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
346 c(Q) &\ge \left( { c(P) \cdot M\over \cmax} - n\right) \cdot {\cmax\over M} \ge
347 c(P) - {n\cdot \cmax\over n / \varepsilon} \ge c(P) - \varepsilon \cmax \ge \cr
348 &\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P).
351 Na~pøechodu mezi øádky jsme vyu¾ili toho, ¾e ka¾dý pøedmìt se vejde do batohu,
352 tak¾e optimum musí být alespoò tak cenné jako nejcennìj¹í z~pøedmìtù.
354 Shròme, co jsme dokázali:
357 Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne
358 {\I $(1 - \varepsilon)$-aproximaci} problému batohu s $n$ pøedmìty v èase
359 $\O(n^3/\varepsilon)$.
361 Dodejme je¹tì, ¾e algoritmùm, které dovedou pro ka¾dé $\varepsilon > 0$ najít
362 v~polynomiálním èase $(1-\varepsilon)$-aproximaci optimálního øe¹ení, øíkáme
363 {\I polynomiální aproximaèní schémata} (PTAS -- Polynomial-Time Approximation Scheme).
364 V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e
365 schéma je {\I plnì polynomiální} (FPTAS -- Fully Polynomial-Time Approximation Scheme).
369 \ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu.
370 (To je mno¾ina vrcholù, která obsahuje alespoò jeden vrchol z~ka¾dé hrany.)}
372 \exx{Naleznìte polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí
375 \hint{Vzpomeòte si na sí» z~algoritmu na nejvìt¹í párování. Jak v~ní vypadají øezy?}
377 \ex{Uka¾te, jak v~polynomiálnì najít nejvìt¹í nezávislou mno¾inu v~intervalovém grafu.}
379 \exx{Vyøe¹te v~polynomiálním èase 2-SAT, tedy splnitelnost formulí zadaných v~CNF,
380 jejich¾ klauzule obsahují nejvý¹e 2 literály.}
382 \hint{Na ka¾dou klauzuli se mù¾eme podívat jako na implikaci.}
384 \ex{Problém E3,E3-SAT je zesílením 3,3-SATu. Chceme zjistit splnitelnost formule v~CNF, její¾ ka¾dá
385 klauzule obsahuje právì tøi rùzné promìnné a ka¾dá promìnná se nachází v~právì tøech klauzulích.
386 Uka¾te, ¾e tento problém lze øe¹it efektivnì z~toho prostého dùvodu, ¾e ka¾dá taková formule je
389 \hint{Pou¾ijte Hallovu vìtu.}
391 \ex{Pokusíme se øe¹it problém dvou loupe¾níkù hladovým algoritmem. Probíráme
392 pøedmìty od~nejdra¾¹ího k~nejlevnìj¹ímu a ka¾dý dáme tomu loupe¾níkovi, který
393 má zrovna ménì. Je nalezené øe¹ení optimální?}
395 \ex{Problém tøí loupe¾níkù: Je dána mno¾ina pøedmìtù s~cenami, chceme ji rozdìlit na 3
396 èásti o~stejné cenì. Navrhnìte pseudopolynomiální algoritmus.}
398 \ex{Problém \alg{MaxCut}: vrcholy zadaného grafu chceme rozdìlit do dvou mno¾in tak,
399 aby mezi mno¾inami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf
400 s~co nejvíce hranami. Rozhodovací verze tohoto problému je \NP-úplná, zkuste jej
401 v~polynomiálním èase 2-aproximovat.}
403 \exx{V~problému \alg{MaxE3-SAT} dostaneme formuli v~CNF, její¾ ka¾dá klauzule obsahuje
404 právì~3 rùzné promìnné, a~chceme nalézt ohodnocení promìnných, pøi nìm¾ je splnìno co nejvíce
405 klauzulí. Rozhodovací verze je \NP-úplná. Uka¾te, ¾e pøi náhodném ohodnocení promìnných
406 je splnìno v~prùmìru $7/8$ klauzulí. Z~toho odvoïte deterministickou $7/8$-aproximaci
407 v~polynomiálním èase.
410 \hint{Linearita støední hodnoty.}
412 \ex{Hledejme vrcholové pokrytí následujícím hladovým algoritmem. V~ka¾dém kroku
413 vybereme vrchol nejvy¹¹ího stupnì, pøidáme ho do pokrytí a odstraníme ho z~grafu
414 i se v¹emi ji¾ pokrytými hranami. Je nalezené pokrytí nejmen¹í? Nebo alespoò $\O(1)$-aproximace
417 \exx{Uva¾ujme následující algoritmus pro nejmen¹í vrcholové pokrytí grafu. Graf projdeme
418 do hloubky, do výstupu vlo¾íme v¹echny vrcholy vzniklého DFS stromu kromì listù. Doka¾te,
419 ¾e vznikne vrcholové pokrytí a ¾e 2-aproximuje to nejmen¹í.}
421 \hint{Najdìte v~$G$ párování obsahující alespoò tolik hran, kolik je polovina poètu
422 vrcholù vráceného pokrytí. Jak velikost párování souvisí s~velikostí nejmen¹ího vrcholového
425 \exx{V~daném orientovaném grafu hledáme acyklický podgraf s~co nejvíce hranami.
426 Navrhnìte polynomiální 2-aproximaèní algoritmus.}
428 \hint{Libovolné oèíslování vrcholù rozdìlí hrany na \uv{dopøedné} a \uv{zpìtné}.}
projects / ads2.git / blob