bì¾et, tím lep¹í øe¹ení najde.
\:{\I Kombinace pøístupù.} Mnohdy lze pøedchozí pøístupy kombinovat:
napøíklad pou¾ít aproximaèní algoritmus a poté jeho výsledek
- je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které zaruèenì není
- moc daleko od optima, a~pokud budeme mít ¹tìstí, bude k~nìmu velmi blízko.
+ je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které od~optima
+ zaruèenì není moc daleko, a~pokud budeme mít ¹tìstí, bude se od~nìj li¹it
+ jen velmi málo.
\endlist
\>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.
Samotné obarvování je lineární.
Je¹tì ov¹em potøebujeme dokázat, ¾e jsme pou¾ili minimální mo¾ný poèet barev.
-Uva¾ujme okam¾ik, kdy promìnná~$b$ naposledy vzroste. Tehdy zaèal interval
+Uva¾ujme okam¾ik, kdy promìnná~$b$ naposledy vzrostla. Tehdy zaèal interval
a mno¾ina~$B$ byla prázdná, co¾ znamená, ¾e jsme $b-1$ pøedchozích barev museli
pøidìlit intervalùm, je¾ zaèaly a dosud neskonèily. Existuje tedy $b$ rùzných
intervalù, které mají spoleèný bod (v~grafu tvoøí kliku), tak¾e ka¾dé obarvení
\h{Problém batohu s~malými èísly}
-Pøipomeòme si problém batohu. Jeho optimalizaèní verze vypadá takto:
-Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ a cenami $c_1,\ldots,c_n$
+Pøipomeòme si {\I problém batohu.} Jeho optimalizaèní verze vypadá takto:
+Je dána mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ a cenami $c_1,\ldots,c_n$
a nosnost batohu~$H$. Hledáme podmno¾inu pøedmìtù~$P \subseteq \{1,\ldots,n\}$,
která se vejde do batohu (tedy $h(P)=\sum_{i\in P} h_i \le H$) a její cena
$c(P) = \sum_{i\in P} c_i$ je nejvìt¹í mo¾ná.
jejich¾ cena je právì~$c$; pokud ¾ádná taková podmno¾ina neexistuje, polo¾íme $A_k(c)=\infty$.
Tato $A_k$ spoèteme indukcí podle~$k$: Pro $k=0$ je
-urèitì $A_0(0)=0$ a $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe
+urèitì $A_0(0)=0$ a $A_0(1)=\ldots=A_0(C)=\infty$. 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) =
+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í:
$$
A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
$$
-Pøechod od $A_{k-1}$ k~$A_k$ tedy trvá $\O(C)$, pro v¹echna~$k$ pak $\O(Cn)$.
+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)$.
-Jakmile spoèteme~$A_n$, známe pro ka¾dou cenu nejlehèí podmno¾inu s~touto cenou.
+Jakmile získáme~$A_n$, známe pro ka¾dou cenu pøíslu¹nou nejlehèí podmno¾inu.
Maximální cena mno¾iny, která se vejde do batohu, je tedy nejvìt¹í~$c^*$, pro nì¾
je $A_n(c^*) \le H$. Jeho nalezení nás stojí èas $\O(C)$.
Zbývá 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,
+aby si pro ka¾dé $A_k(c)$ pamatoval je¹tì $B_k(c)$, co¾ bude index posledního pøedmìtu,
který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
Máme tedy algoritmus, který vyøe¹í problém batohu v~èase $\O(nC)$. Tato funkce
ov¹em není polynomem ve~velikosti vstupu, jeliko¾ reprezentujeme-li vstup binárnì,
-$C$~mù¾e být a¾ exponenciálnì velké vzhledem k~velikosti jeho zápisu. To je pìkný
+$C$~mù¾e být a¾ exponenciálnì velké vzhledem k~délce jeho zápisu. To je pìkný
pøíklad tzv. {\I pseudopolynomiálního} algoritmu, tedy algoritmu, jeho¾ slo¾itost
je polynomem v~poètu èísel na vstupu a jejich velikosti. Pro nìkteré \NP-úplné
-problémy takové algoritmy existují, pro jiné (napø. pro nezávislou mno¾inu) nikoliv.
+problémy takové algoritmy existují, pro jiné (napø. pro nezávislou mno¾inu) by
+z~jejich existence plynulo $\P=\NP$.
\s{Verze bez cen:} Jednodu¹¹í verzi problému batohu, která nerozli¹uje mezi
hmotnostmi a cenami, zvládneme i jiným algoritmem, opìt zalo¾eným na dynamickém
Indukcí podle~$k$ vytváøí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ù. Jistì je $Z_0=\{0\}$.
Podobnou úvahou jako v~pøedchozím algoritmu dostaneme, ¾e ka¾dou dal¹í~$Z_k$ mù¾eme
-zapsat jako sjednocení $Z_{k-1}$ s~kopií $Z_{k-1}$ posunutou o~$h_k$, pøièem¾ hodnoty
-vìt¹í ne¾~$H$ zahodíme. Nakonec ze~$Z_n$ vyèteme výsledek.
+zapsat jako sjednocení $Z_{k-1}$ s~kopií $Z_{k-1}$ posunutou o~$h_k$, ignorujíce hodnoty
+vìt¹í ne¾~$H$. Nakonec ze~$Z_n$ vyèteme výsledek.
V¹echny mno¾iny pøitom mají nejvý¹e~$H+1$ prvkù, tak¾e pokud si je budeme udr¾ovat
jako setøídìné seznamy, spoèítáme sjednocení sléváním v~èase $\O(H)$ a celý algoritmus
\h{Aproximace problému obchodního cestujícího}
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
+hrany jsou ohodnoceny délkami $\ell(e)\ge 0$. V~tomto
grafu chceme nalézt nejkrat¹í z~hamiltonovských kru¾nic, tedy tìch, které nav¹tíví
v¹echny vrcholy.
è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.
+toti¾ 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
+a» ji obejde. 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 pøitom
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
è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:
+Trojúhelníková nerovnost nicménì byla pro tento algoritmus naprosto nezbytná.
+To není náhoda -- hned doká¾eme, ¾e bez tohoto pøedpokladu je libovolná
+aproximace stejnì tì¾ká jako pøesné øe¹ení.
-\s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální
-$(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího
+\s{Vìta:} Pokud pro~nìjaké reálné~$t\ge 1$ existuje polynomiální
+$t$-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$.
+Doplníme $G$ na~úplný graf~$G'$. V¹em pùvodním hranám nastavíme délku na~1,
+tìm novým na nìjaké dost velké èíslo~$c$. Kolik to bude, urèíme za chvíli.
-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$.
+Graf~$G'$ je úplný, tak¾e v~nìm urèitì nìjaké HK existují. Ty, které se
+vyskytují i v~pùvodním grafu~$G$, mají délku pøesnì~$n$. Jakmile ale
+pou¾ijeme jedinou hranu, která z~$G$ nepochází, vzroste délka kru¾nice
+alespoò na $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$.
+Podle délky nejkrat¹í HK tedy doká¾eme rozpoznat, zda existuje HK v~$G$.
+Potøebujeme ov¹em zjistit i pøes zkreslení zpùsobené aproximací. Musí tedy
+platit $tn < n-1+c$. To snadno zajistíme volbou hodnoty~$c$ vìt¹í ne¾ $(t-1) 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.
+Na¹e konstrukce pøidala polynomiálnì mnoho hran s~polynomiálnì velkým ohodnocením,
+tak¾e graf~$G'$ je polynomiálnì velký vzhledem ke~$G$. Rozhodujeme tedy
+existenci HK v~polynomiálním èase a $\P=\NP$.
\qed
-\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.
+\s{Poznámka:} Podobnì mù¾eme dokázat, ¾e pokud $\P\ne\NP$, neexistuje pro problém
+obchodního cestujícího ani pseudopolynomiální algoritmus. Staèí pùvodním hranám
+pøiøadit délku~1 a novým délku~2.
\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.
Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
-ceny byly dìlitelné nìjakým èíslem~$p$, mohli bychom je tímto èíslem
-vydìlit. Tím bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
+ceny byly násobky nìjakého èísla~$p$, mohli bychom je tímto èíslem
+vydìlit. Tak bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
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. 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í.
-\ss{Základní my¹lenka:}
-
\def\cmax{c_{\rm max}}
-Oznaèíme si $\cmax$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < \cmax$
+\s{Základní my¹lenka:}
+Oznaèíme $\cmax$ maximum z~cen~$c_i$. Zvolíme nìjaké pøirozené èíslo~$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é
&\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P).
}
$$
-Dokázali jsme tedy tuto vìtu:
+Na~pøechodu mezi øádky jsme vyu¾ili toho, ¾e ka¾dý pøedmìt se vejde do batohu,
+tak¾e optimum musí být alespoò tak cenné jako nejcennìj¹í z~pøedmìtù.
+
+Shròme, co jsme dokázali:
\s{Vìta:}
Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne
\exercises
-\ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu
-(vrcholové pokrytí je mno¾ina vrcholù, která z~ka¾dé hrany obsahuje alespoò jeden vrchol.}
+\ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu.
+(To je mno¾ina vrcholù, která obsahuje alespoò jeden vrchol z~ka¾dé hrany.)}
\exx{Naleznìte polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí
bipartitního grafu.}
-\hint{Toky a øezy.}
+\hint{Vzpomeòte si na sí» z~algoritmu na nejvìt¹í párování. Jak v~ní vypadají øezy?}
\ex{Uka¾te, jak v~polynomiálnì najít nejvìt¹í nezávislou mno¾inu v~intervalovém grafu.}
\hint{Pou¾ijte Hallovu vìtu.}
+\ex{Pokusíme se øe¹it problém dvou loupe¾níkù hladovým algoritmem. Probíráme
+pøedmìty od~nejdra¾¹ího k~nejlevnìj¹ímu a ka¾dý dáme tomu loupe¾níkovi, který
+má zrovna ménì. Je nalezené øe¹ení optimální?}
+
\ex{Problém tøí loupe¾níkù: Je dána mno¾ina pøedmìtù s~cenami, chceme ji rozdìlit na 3
èásti o~stejné cenì. Navrhnìte pseudopolynomiální algoritmus.}
v~polynomiálním èase.
}
+\hint{Linearita støední hodnoty.}
+
+\ex{Hledejme vrcholové pokrytí následujícím hladovým algoritmem. V~ka¾dém kroku
+vybereme vrchol nejvy¹¹ího stupnì, pøidáme ho do pokrytí a odstraníme ho z~grafu
+i se v¹emi ji¾ pokrytými hranami. Je nalezené pokrytí nejmen¹í? Nebo alespoò $\O(1)$-aproximace
+nejmen¹ího?}
+
\exx{Uva¾ujme následující algoritmus pro nejmen¹í vrcholové pokrytí grafu. Graf projdeme
do hloubky, do výstupu vlo¾íme v¹echny vrcholy vzniklého DFS stromu kromì listù. Doka¾te,
¾e vznikne vrcholové pokrytí a ¾e 2-aproximuje to nejmen¹í.}
projects / ads2.git / blobdiff