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é zaruèenì není
40 moc daleko od optima, a~pokud budeme mít ¹tìstí, bude k~nìmu velmi blízko.
43 \>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.
45 \h{Nejvìt¹í nezávislá mno¾ina ve stromu}
47 Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je snadné, pokud graf je strom.
49 \s{Lemma:} Buï~$T$ zakoøenìný strom a $\ell$ jeho libovolný list. Pak alespoò jedna
50 z~nejvìt¹ích nezávislých mno¾in obsahuje~$\ell$.
53 Mìjme nejvìt¹í nezávislou mno¾inu~$M$, která list~$\ell$ neobsahuje. Podívejme
54 se na otce~$p$ listu~$\ell$ (kdyby neexistoval, je celý strom jednovrcholový
55 a tvrzení triviální). Le¾í~$p$ v~$M$? Pokud ne, mohli bychom do~$M$ pøidat
56 list~$\ell$ a dostali bychom vìt¹í nezávislou mno¾inu. V~opaèném pøípadì z~$M$
57 odebereme otce~$p$ a nahradíme ho listem~$\ell$, èím¾ dostaneme stejnì velkou
58 nezávislou mno¾inu obsahující~$\ell$.
61 Algoritmus bude pøímoèaøe pou¾ívat toto lemma. Dostane na vstupu strom,
62 ten zakoøení a zvolí libovolný list. Tento list umístí do nezávislé mno¾iny
63 a jeho otce odebere, proto¾e se nemù¾e v~nezávislé mno¾inì vyskytovat.
64 Toto bude opakovat, dokud nìjaké vrcholy zbývají. (Graf se v~prùbìhu mù¾e
65 rozpadnout na více komponent, ale to nevadí.)
67 Tento algoritmus jistì pracuje v~polynomiálním èase. ©ikovnou implementací
68 mù¾eme slo¾itost sní¾it a¾ na lineární. Napøíklad tak, ¾e budeme udr¾ovat seznam
69 listù. My si uká¾eme jinou lineární implementaci zalo¾enou na prohledávání do hloubky.
70 Bude pracovat s~polem znaèek~$M$, v~nìm¾ na poèátku bude v¹ude \<false> a postupnì
71 obdr¾í \<true> v¹echny prvky hledané nezávislé mno¾iny.
74 \algin Strom~$T$ s~koøenem~$v$, pole znaèek~$M$.
76 \:Pokud je~$v$ list, skonèíme.
77 \:Pro v¹echny syny~$w$ vrcholu~$v$:
78 \::Zavoláme se rekurzivnì na podstrom s~koøenem~$w$.
79 \::Pokud $M[w]=\<true>$, polo¾íme $M[v] \= \<false>$.
82 \h{Barvení intervalového grafu}
84 Mìjme~$n$ pøedná¹ek s~urèenými èasy zaèátku a konce. Chceme je rozvrhnout
85 do co~nejmen¹ího poètu poslucháren tak, aby nikdy neprobíhaly dvì pøedná¹ky
86 naráz v~jedné místnosti.
88 Chceme tedy obarvit co nejmen¹ím poètem barev graf, jeho¾ vrcholy jsou èasové
89 intervaly a dvojice intervalù je spojena hranou, pokud má neprázdný prùnik.
90 Takovým grafùm se øíká {\I intervalové} a pro jejich barvení existuje pìkný
91 polynomiální algoritmus.
93 Podobnì jako jsme geometrické problémy øe¹ili zametáním roviny, zde budeme
94 \uv{zametat pøímku bodem}, tedy procházet ji zleva doprava, a~v¹ímat si
95 událostí, co¾ budou zaèátky a konce intervalù. Pro jednoduchost pøedpokládejme,
96 ¾e v¹echny souøadnice zaèátkù a koncù jsou navzájem rùzné.
98 Kdykoliv interval zaène, pøidìlíme mu barvu. A¾ skonèí, o~barvì si poznamenáme,
99 ¾e je momentálnì volná, a~dal¹ím intervalùm budeme pøednostnì pøidìlovat
100 volné barvy. Øeèeno v~pseudokódu:
102 \algo{BarveníIntervalù}
103 \algin Intervaly $\left[ x_1, y_1 \right], \ldots, \left[ x_n, y_n \right]$.
104 \:$b \= 0$ \cmt{poèet zatím pou¾itých barev}
105 \:$B \= \emptyset$ \cmt{které barvy jsou momentálnì volné}
106 \:Setøídíme mno¾inu v¹ech $x_i$ a $y_i$.
107 \:Procházíme v¹echna $x_i$ a $y_i$ ve~vzestupném poøadí:
108 \::Narazíme-li na $x_i$:
109 \:::Je-li $B\ne\emptyset$, odebereme jednu barvu z~$B$ a ulo¾íme ji do~$c_i$.
110 \:::Jinak $b\=b+1$ a $c_i\=b$.
111 \::Narazíme-li na $y_i$:
112 \:::Vrátíme barvu $c_i$ do~$B$.
113 \algout Obarvení $c_1,\ldots,c_n$.
117 Tento algoritmus má èasovou slo¾itost $\O(n\log n)$ kvùli tøídìní souøadnic.
118 Samotné obarvování je lineární.
120 Je¹tì ov¹em potøebujeme dokázat, ¾e jsme pou¾ili minimální mo¾ný poèet barev.
121 Uva¾ujme okam¾ik, kdy promìnná~$b$ naposledy vzroste. Tehdy zaèal interval
122 a mno¾ina~$B$ byla prázdná, co¾ znamená, ¾e jsme $b-1$ pøedchozích barev museli
123 pøidìlit intervalùm, je¾ zaèaly a dosud neskonèily. Existuje tedy $b$ rùzných
124 intervalù, které mají spoleèný bod (v~grafu tvoøí kliku), tak¾e ka¾dé obarvení
125 potøebuje alespoò~$b$ barev.
127 \h{Problém batohu s~malými èísly}
129 Pøipomeòme si problém batohu. Jeho optimalizaèní verze vypadá takto:
130 Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ a cenami $c_1,\ldots,c_n$
131 a nosnost batohu~$H$. Hledáme podmno¾inu pøedmìtù~$P \subseteq \{1,\ldots,n\}$,
132 která se vejde do batohu (tedy $h(P)=\sum_{i\in P} h_i \le H$) a její cena
133 $c(P) = \sum_{i\in P} c_i$ je nejvìt¹í mo¾ná.
135 Uká¾eme algoritmus, jeho¾ èasová slo¾itost bude polynomiální v~poètu
136 pøedmìtù~$n$ a souètu v¹ech cen $C=\sum_i c_i$.
138 Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
139 pøedmìtù. Oznaème $A_k(c)$ (kde $0\le c\le C$) minimum z~hmotností tìch podmno¾in
140 jejich¾ cena je právì~$c$; pokud ¾ádná taková podmno¾ina neexistuje, polo¾íme $A_k(c)=\infty$.
142 Tato $A_k$ spoèteme indukcí podle~$k$: Pro $k=0$ je
143 urèitì $A_0(0)=0$ a $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe
144 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
145 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili
146 (a pak je $A_k(c)=A_{k-1}(c)$), nebo pou¾ili a tehdy bude $A_k(c) =
147 A_{k-1}(c-c_k) + h_k$ (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou
148 mo¾ností si vybereme tu, která dává mno¾inu s~men¹í hmotností:
150 A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
152 Pøechod od $A_{k-1}$ k~$A_k$ tedy trvá $\O(C)$, pro v¹echna~$k$ pak $\O(Cn)$.
154 Jakmile spoèteme~$A_n$, známe pro ka¾dou cenu nejlehèí podmno¾inu s~touto cenou.
155 Maximální cena mno¾iny, která se vejde do batohu, je tedy nejvìt¹í~$c^*$, pro nì¾
156 je $A_n(c^*) \le H$. Jeho nalezení nás stojí èas $\O(C)$.
158 Zbývá zjistit, které pøedmìty do~nalezené mno¾iny patøí. Upravíme algoritmus,
159 aby si pro ka¾dé $A_k(c)$ pamatoval $B_k(c)$, co¾ bude index posledního pøedmìtu,
160 který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
161 poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
162 a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
165 Máme tedy algoritmus, který vyøe¹í problém batohu v~èase $\O(nC)$. Tato funkce
166 ov¹em není polynomem ve~velikosti vstupu, jeliko¾ reprezentujeme-li vstup binárnì,
167 $C$~mù¾e být a¾ exponenciálnì velké vzhledem k~velikosti jeho zápisu. To je pìkný
168 pøíklad tzv. {\I pseudopolynomiálního} algoritmu, tedy algoritmu, jeho¾ slo¾itost
169 je polynomem v~poètu èísel na vstupu a jejich velikosti. Pro nìkteré \NP-úplné
170 problémy takové algoritmy existují, pro jiné (napø. pro nezávislou mno¾inu) nikoliv.
172 \s{Verze bez cen:} Jednodu¹¹í verzi problému batohu, která nerozli¹uje mezi
173 hmotnostmi a cenami, zvládneme i jiným algoritmem, opìt zalo¾eným na dynamickém
176 Indukcí podle~$k$ vytváøíme mno¾iny~$Z_k$ obsahující v¹echny hmotnosti
177 men¹í ne¾~$H$, kterých nabývá nìjaká podmno¾ina prvních~$k$ prvkù. Jistì je $Z_0=\{0\}$.
178 Podobnou úvahou jako v~pøedchozím algoritmu dostaneme, ¾e ka¾dou dal¹í~$Z_k$ mù¾eme
179 zapsat jako sjednocení $Z_{k-1}$ s~kopií $Z_{k-1}$ posunutou o~$h_k$, pøièem¾ hodnoty
180 vìt¹í ne¾~$H$ zahodíme. Nakonec ze~$Z_n$ vyèteme výsledek.
182 V¹echny mno¾iny pøitom mají nejvý¹e~$H+1$ prvkù, tak¾e pokud si je budeme udr¾ovat
183 jako setøídìné seznamy, spoèítáme sjednocení sléváním v~èase $\O(H)$ a celý algoritmus
184 dobìhne v~èase $\O(Hn)$.
186 \h{Aproximace problému obchodního cestujícího}
188 V~{\I problému obchodního cestujícího} je zadán neorientovaný graf~$G$, jeho¾
189 hrany jsou ohodnoceny délkami~$\ell: E(G) \rightarrow {\bb R}^+_0$. V~tomto
190 grafu chceme nalézt nejkrat¹í z~hamiltonovských kru¾nic, tedy tìch, které nav¹tíví
193 Není pøekvapivé, ¾e tento problém je tì¾ký -- u¾ sama existence hamiltonovské
194 kru¾nice je \NP-úplná. Uká¾eme ov¹em, ¾e pokud je graf úplný a platí v~nìm trojúhelníková
195 nerovnost (tj. $\ell(x,z) \le \ell(x,y) + \ell(y,z)$ pro v¹echny trojice vrcholù $x,y,z$),
196 mù¾eme problém obchodního cestujícího 2-aproximovat, tedy najít v~polynomiálním
197 èase kru¾nici, která je pøinejhor¹ím dvakrát del¹í ne¾ ta optimální.
199 Grafy s~trojúhelníkovou nerovností pøitom nejsou nijak neobvyklé -- odpovídají
200 toti¾ v¹em koneèným metrickým prostorùm.
202 Algoritmus bude snadný: Najdeme nejmen¹í kostru a obchodnímu cestujícímu poradíme,
203 a» jde po~ní. To mù¾eme popsat napøíklad tak, ¾e kostru zakoøeníme, prohledáme ji
204 do hloubky a zaznamenáme, jak jsme procházeli hranami. Ka¾dou hranou kostry tedy
205 projdeme dvakrát -- jednou dolù, podruhé nahoru. Tím v¹ak nedostaneme kru¾nici,
206 nýbr¾ jen nìjaký uzavøený sled, proto¾e vrcholy nav¹tìvujeme vícekrát. Sled tedy
207 upravíme tak, ¾e kdykoliv se dostává do ji¾ nav¹tíveného vrcholu, pøeskoèí ho
208 a pøesune se a¾ do nejbli¾¹ího dal¹ího nenav¹tíveného. Tím ze sledu vytvoøíme
209 hamiltonovskou kru¾nici a jeliko¾ v~grafu platí trojúhelníková nerovnost,
210 celková délka nevzrostla. (Poøadí vrcholù na kru¾nici mù¾eme získat také tak,
211 ¾e bìhem prohledávání budeme vypisovat vrcholy v~preorderu. Rozmyslete si,
214 \s{Vìta:} Nalezená kru¾nice není del¹í ne¾ dvojnásobek optima.
217 Oznaème $T$ délku minimální kostry, $A$ délku kru¾nice vydané na¹ím algoritmem
218 a $O$ (optimum) délku nejkrat¹í hamiltonovské kru¾nice. Z~toho, jak jsme kru¾nici
219 vytvoøili, víme, ¾e $A\le 2T$. Platí ov¹em také $T\le O$, jeliko¾ z~ka¾dé
220 hamiltonovské kru¾nice vznikne vynecháním hrany kostra a ta nemù¾e být men¹í
221 ne¾ minimální kostra. Slo¾ením obou nerovností získáme $A\le 2T\le 2O$.
224 Sestrojili jsme tedy 2-aproximaèní algoritmus pro problém obchodního cestujícího.
225 Dodejme je¹tì, ¾e trochu slo¾itìj¹ím trikem lze tento problém $1.5$-aproximovat
226 a ¾e v~nìkterých metrických prostorech (tøeba v~euklidovské rovinì) lze v~polynomiálním
227 èase najít $(1+\varepsilon)$-aproximaci pro libovolné $\varepsilon>0$. Ov¹em èím
228 men¹í~$\varepsilon$, tím déle algoritmus pobì¾í.
230 Bez trojúhelníkové nerovnosti ov¹em ná¹ problém aproximovat vùbec nejde:
232 \s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální
233 $(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího
234 bez~trojúhelníkové nerovnosti, pak je $\P = \NP$.
236 \proof Uká¾eme, ¾e pomocí takového aproximaèního algoritmu doká¾eme v~polynomiálním
237 èase zjistit, zda v grafu existuje hamiltonovská kru¾nice, co¾ je \NP-úplný problém.
239 Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici (zkrácenì HK).
240 Doplníme $G$ na~úplný graf~$G'$. Délky v¹ech pùvodních hran nastavíme na~1, novým
241 hranám pøisoudíme délku~$c$ pro nìjakou vhodnì zvolenou konstantu~$c\gg 1$.
243 V~grafu~$G'$ jistì alespoò jedna HK existuje. Z~ka¾dé HK v~$G$ se stala
244 HK v~$G'$ o~délce pøesnì~$n$. V¹echny ostatní HK v~$G'$ obsahují alespoò
245 jednu hranu, která nepochází z~$G$, tak¾e mají délku alespoò $n-1+c$.
247 Nastavíme konstantu~$c$ tak, aby i pøes zkreslení zpùsobené aproximací
248 bylo podle odpovìdi algoritmu poznat, zda nìjaká kru¾nice délky~$n$ existuje.
249 Potøebujeme, aby platilo $(1+\varepsilon)\cdot n < n-1+c$, tedy staèí zvolit
250 $c$ vìt¹í ne¾ $\varepsilon n + 1$.
252 Pøidali jsme tedy polynomiálnì mnoho hran s~polynomiálnì velkým ohodnocením,
253 tak¾e graf~$G'$ je polynomiálnì velký vzhledem ke~$G$ a ná¹ algoritmus rozhoduje
254 existenci HK v~polynomiálním èase.
257 \s{Poznámka:} Podobnì mù¾eme dokázat, ¾e pokud $\P\ne\NP$, neexistuje ani
258 pseudopolynomiální algoritmus. Staèí pùvodním hranám pøiøadit váhu~1 a novým váhu~2.
260 \h{Aproximaèní schéma pro problém batohu}
262 Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$,
263 pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen.
264 Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
265 ceny byly dìlitelné nìjakým èíslem~$p$, mohli bychom je tímto èíslem
266 vydìlit. Tím bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
267 stejná mno¾ina pøedmìtù jako u~zadání pùvodního.
269 Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky
270 nìjak zaokrouhlit. Optimální øe¹ení nové úlohy pak sice nemusí odpovídat optimálnímu
271 øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací.
273 \ss{Základní my¹lenka:}
275 \def\cmax{c_{\rm max}}
277 Oznaèíme si $\cmax$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < \cmax$
278 a zobrazíme interval cen $[0, \cmax]$ na $\{0, \ldots, M \}$ (tedy ka¾dou cenu znásobíme pomìrem
279 $M/\cmax$ a zaokrouhlíme).
280 Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé
281 ceny zaokrouhlili na~násobky èísla $\cmax/M$ (prvky z intervalu
282 $[i\cdot \cmax/M,(i+1)\cdot \cmax/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím
283 tedy zmìnili o~nejvý¹e $\cmax/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak
284 nejvý¹e o~$n\cdot \cmax/M$. Navíc odstraníme-li ze vstupu
285 pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $c^* \ge \cmax$,
286 tak¾e chyba na¹í aproximace nepøesáhne $n\cdot c^*/M$. Má-li tato chyba být shora omezena
287 $\varepsilon\cdot c^*$, musíme zvolit $M\ge n/\varepsilon$.
289 Na~této my¹lence \uv{kvantování cen} je zalo¾en následující algoritmus.
291 \algo{AproximaceBatohu}
292 \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$.
293 \:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$.
294 \:Kvantujeme ceny: Pro $i=1,\ldots,n$ polo¾íme $\hat{c}_i \= \lfloor c_i \cdot M/\cmax \rfloor$.
295 \:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$
296 a pùvodní hmotnosti i kapacitu batohu.
297 \:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání.
301 Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
302 se souètem cen $\hat{C}\le nM = \O(n^2/\varepsilon)$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$.
303 Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$.
305 Oznaème~$P$ mno¾inu pøedmìtù pou¾itých v~optimálním øe¹ení pùvodní úlohy a $c(P)$
306 cenu tohoto øe¹ení. Podobnì~$Q$ bude mno¾ina pøedmìtù v~optimálním øe¹ení
307 nakvantované úlohy a $\hat{c}(Q)$ jeho hodnota v~nakvantovaných cenách. Potøebujeme
308 odhadnout ohodnocení mno¾iny~$Q$ v~pùvodních cenách, tedy $c(Q)$, a~srovnat
311 Nejprve uká¾eme, jakou cenu má optimální øe¹ení~$P$ pùvodní úlohy
312 v~nakvantovaných cenách:
315 \hat{c}(P) &= \sum_{i\in P} \hat{c}_i =
316 \sum_{i\in P} \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge
317 \sum_{i\in P} \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr
319 \left(\sum_{i\in P} c_i \cdot {M\over \cmax}\right) - n =
320 c(P) \cdot {M\over \cmax} - n.
323 Nyní naopak spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
324 na~pùvodní ceny (to je výsledek na¹eho algoritmu):
327 c(Q) &= \sum_{i\in Q} c_i \ge
328 \sum_{i\in Q} \hat{c}_i \cdot {\cmax\over M} =
329 \left(\sum_i \hat{c}_i\right) \cdot {\cmax\over M} =
330 \hat{c}(Q) \cdot {\cmax\over M} \ge
331 \hat{c}(P) \cdot {\cmax\over M}.
334 Poslední nerovnost platí proto, ¾e $\hat{c}(Q)$ je optimální øe¹ení kvantované úlohy,
335 zatímco $\hat{c}(P)$ je nìjaké dal¹í øe¹ení té¾e úlohy, které nemù¾e být lep¹í.%
336 \foot{Zde nás zachraòuje, ¾e aèkoliv u~obou úloh le¾í optimum obecnì jinde, obì mají
337 stejnou mno¾inu {\I pøípustných øe¹ení,} tedy tìch, která se vejdou do batohu. Kdybychom
338 místo cen kvantovali hmotnosti, nebyla by to pravda a algoritmus by nefungoval.}
339 Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
342 c(Q) &\ge \left( { c(P) \cdot M\over \cmax} - n\right) \cdot {\cmax\over M} \ge
343 c(P) - {n\cdot \cmax\over n / \varepsilon} \ge c(P) - \varepsilon \cmax \ge \cr
344 &\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P).
347 Dokázali jsme tedy tuto vìtu:
350 Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne
351 {\I $(1 - \varepsilon)$-aproximaci} problému batohu s $n$ pøedmìty v èase
352 $\O(n^3/\varepsilon)$.
354 Dodejme je¹tì, ¾e algoritmùm, které dovedou pro ka¾dé $\varepsilon > 0$ najít
355 v~polynomiálním èase $(1-\varepsilon)$-aproximaci optimálního øe¹ení, øíkáme
356 {\I polynomiální aproximaèní schémata} (PTAS -- Polynomial-Time Approximation Scheme).
357 V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e
358 schéma je {\I plnì polynomiální} (FPTAS -- Fully Polynomial-Time Approximation Scheme).
362 \ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu
363 (vrcholové pokrytí je mno¾ina vrcholù, která z~ka¾dé hrany obsahuje alespoò jeden vrchol.}
365 \exx{Naleznìte polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí
370 \ex{Uka¾te, jak v~polynomiálnì najít nejvìt¹í nezávislou mno¾inu v~intervalovém grafu.}
372 \exx{Vyøe¹te v~polynomiálním èase 2-SAT, tedy splnitelnost formulí zadaných v~CNF,
373 jejich¾ klauzule obsahují nejvý¹e 2 literály.}
375 \hint{Na ka¾dou klauzuli se mù¾eme podívat jako na implikaci.}
377 \ex{Problém E3,E3-SAT je zesílením 3,3-SATu. Chceme zjistit splnitelnost formule v~CNF, její¾ ka¾dá
378 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.
379 Uka¾te, ¾e tento problém lze øe¹it efektivnì z~toho prostého dùvodu, ¾e ka¾dá taková formule je
382 \hint{Pou¾ijte Hallovu vìtu.}
384 \ex{Problém tøí loupe¾níkù: Je dána mno¾ina pøedmìtù s~cenami, chceme ji rozdìlit na 3
385 èásti o~stejné cenì. Navrhnìte pseudopolynomiální algoritmus.}
387 \ex{Problém \alg{MaxCut}: vrcholy zadaného grafu chceme rozdìlit do dvou mno¾in tak,
388 aby mezi mno¾inami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf
389 s~co nejvíce hranami. Rozhodovací verze tohoto problému je \NP-úplná, zkuste jej
390 v~polynomiálním èase 2-aproximovat.}
392 \exx{V~problému \alg{MaxE3-SAT} dostaneme formuli v~CNF, její¾ ka¾dá klauzule obsahuje
393 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
394 klauzulí. Rozhodovací verze je \NP-úplná. Uka¾te, ¾e pøi náhodném ohodnocení promìnných
395 je splnìno v~prùmìru $7/8$ klauzulí. Z~toho odvoïte deterministickou $7/8$-aproximaci
396 v~polynomiálním èase.
399 \exx{Uva¾ujme následující algoritmus pro nejmen¹í vrcholové pokrytí grafu. Graf projdeme
400 do hloubky, do výstupu vlo¾íme v¹echny vrcholy vzniklého DFS stromu kromì listù. Doka¾te,
401 ¾e vznikne vrcholové pokrytí a ¾e 2-aproximuje to nejmen¹í.}
403 \hint{Najdìte v~$G$ párování obsahující alespoò tolik hran, kolik je polovina poètu
404 vrcholù vráceného pokrytí. Jak velikost párování souvisí s~velikostí nejmen¹ího vrcholového
407 \exx{V~daném orientovaném grafu hledáme acyklický podgraf s~co nejvíce hranami.
408 Navrhnìte polynomiální 2-aproximaèní algoritmus.}
410 \hint{Libovolné oèíslování vrcholù rozdìlí hrany na \uv{dopøedné} a \uv{zpìtné}.}
projects / ads2.git / blob