\input lecnotes.tex
\prednaska{9}{Co si poèít s tì¾kým problémem}{}
-V~pøedchozí kapitole jsme zjistili, ¾e mnohé problémy, které v~¾ivotì
-potkáme, jsou \NP-úplné, tak¾e není pravdìpodobné, ¾e bychom pro nì
-umìli nalézt polynomiální algoritmus. Ale co naplat, èasto je potøebujeme
-vyøe¹it. Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto
-mo¾nosti, co si poèít:
+V~pøedchozí kapitole jsme zjistili, ¾e leckteré rozhodovací problémy
+jsou \NP-úplné. Z~toho plyne, ¾e jsou ekvivalentní, ale bohu¾el také,
+¾e ani jeden z~nich zatím neumíme vyøe¹it v~polynomiálním èase.
+
+Èasto se stane, ¾e problém, který v~¾ivotì potkáme, patøí mezi \NP-úplné.
+Pøesnìji øeèeno spí¹ ne¾ s~rozhodovacím problémem se potkáme s~problémem
+{\I optimalizaèním,} ve~kterém jde o~nalezení {\I nejlep¹ího} objektu
+s~danou vlastností. To mù¾e být tøeba nejvìt¹í nezávislá mno¾ina v~grafu
+nebo obarvení grafu nejmen¹ím mo¾ným poètem barev. Kdybychom umìli efektivnì
+øe¹it optimalizaèní problém, umíme samozøejmì øe¹it i pøíslu¹ný rozhodovací,
+tak¾e pokud $\P\ne\NP$, jsou i optimalizaèní problémy tì¾ké.
+
+Ale co naplat, svìt nám takové úlohy pøedkládá a my je potøebujeme vyøe¹it.
+Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto mo¾nosti, co si
+poèít:
\algo
\:{\I Spokojit se s~málem.} Nejsou vstupy, pro které problém potøebujeme
tvar, kterého bychom mohli vyu¾ít? Grafové problémy jsou èasto v~\P{}
tøeba pro stromy nebo i obecnìji pro bipartitní grafy. U~èíselných
problémù zase nìkdy pomù¾e, jsou-li èísla na vstupu dostateènì malá.
-\:{\I Øe¹ení aproximovat.} Pokud chceme nalézt nejlep¹í objekt s~danou
- vlastností (tøeba nejvìt¹í nezávislou mno¾inu), nestaèil by nám o~nìco
- hor¹í? Èasto existuje polynomiální algoritmus, který nalezne nejhùøe
- $c$-krát hor¹í øe¹ení ne¾ je optimum pro nìjakou konstantu~$c$.
+\:{\I Øe¹ení aproximovat.} Opravdu potøebujeme optimální øe¹ení? Nestaèilo
+ by nám o~kousíèek hor¹í? Èasto existuje polynomiální algoritmus, který
+ nalezne nejhùøe $c$-krát hor¹í øe¹ení ne¾ je optimum, kde $c$~je konstanta.
\:{\I Pou¾ít heuristiku.} Neumíme-li nic lep¹ího, mù¾eme sáhnout po~nìkteré
z~mnoha heuristických technik, které sice nic nezaruèují, ale obvykle
- nìjaké uspokojivé øe¹ení najdou. Hodit se mohou tøeba genetické algoritmy.
-\:{\I Kombinace pøístupù.} Èasto lze vý¹e zmínìné pøístupy kombinovat:
- napøíklad mù¾eme pou¾ít aproximaèní algoritmus a poté jeho výsledek
+ nìjaké uspokojivé øe¹ení najdou. Mù¾e pomoci tøeba hladový algoritmus
+ nebo genetické algoritmy. Èasto platí, ¾e èím déle heuristiku necháme
+ 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.
\endalgo
\h{Nejvìt¹í nezávislá mno¾ina ve stromu}
-Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je pro stromy velmi snadné.
+Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je snadné, pokud graf je strom.
\s{Lemma:} Buï~$T$ zakoøenìný strom a $\ell$ jeho libovolný list. Pak alespoò jedna
z~nejvìt¹ích nezávislých mno¾in obsahuje~$\ell$.
\h{Barvení intervalového grafu}
-FIXME
+Mìjme~$n$ pøedná¹ek s~urèenými èasy zaèátku a konce. Chceme je rozvrhnout
+do co~nejmen¹ího poètu poslucháren tak, aby nikdy neprobíhaly dvì pøedná¹ky
+naráz v~jedné místnosti.
+
+Chceme tedy obarvit co nejmen¹ím poètem barev graf, jeho¾ vrcholy jsou èasové
+intervaly a dvojice intervalù je spojena hranou, pokud má neprázdný prùnik.
+Takovým grafùm se øíká {\I intervalové} a pro jejich barvení existuje pìkný
+polynomiální algoritmus.
+
+Podobnì jako jsme geometrické problémy øe¹ili zametáním roviny, zde budeme
+\uv{zametat pøímku bodem}, tedy procházet ji zleva doprava, a~v¹ímat si
+událostí, co¾ budou zaèátky a konce intervalù. Pro jednoduchost pøedpokládejme,
+¾e v¹echny souøadnice zaèátkù a koncù jsou navzájem rùzné.
+
+Kdykoliv interval zaène, pøidìlíme mu barvu. A¾ skonèí, o~barvì si poznamenáme,
+¾e je momentálnì volná, a~dal¹ím intervalùm budeme pøednostnì pøidìlovat
+volné barvy. Øeèeno v~pseudokódu:
+
+\algo
+\algin Intervaly $\left[ x_1, y_1 \right], \ldots, \left[ x_n, y_n \right]$.
+\:$b \= 0$ \cmt{poèet zatím pou¾itých barev}
+\:$B \= \emptyset$ \cmt{které barvy jsou momentálnì volné}
+\:Setøídíme mno¾inu v¹ech $x_i$ a $y_i$.
+\:Procházíme v¹echna $x_i$ a $y_i$ ve~vzestupném poøadí:
+\::Narazíme-li na $x_i$:
+\:::Je-li $B\ne\emptyset$, odebereme jednu barvu z~$B$ a ulo¾íme ji do~$c_i$.
+\:::Jinak $b\=b+1$ a $c_i\=b$.
+\::Narazíme-li na $y_i$:
+\:::Vrátíme barvu $c_i$ do~$B$.
+\algout Obarvení $c_1,\ldots,c_n$.
+\endalgo
+
+\s{Analýza:}
+Tento algoritmus má èasovou slo¾itost $\O(n\log n)$ kvùli tøídìní souøadnic.
+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
+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í
+potøebuje alespoò~$b$ barev.
\h{Problém batohu s~malými èísly}
-\>Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$
-a cenami $c_1,\ldots,c_n$ a~batoh, který unese hmostnost~$H$. Najdìte takovou
-podmno¾inu pøedmìtù, jejich¾ celková hmotnost je maximálnì $H$ a celková cena
-je maximální mo¾ná.
-
-\>Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
-Jednak místo rozhodovacího problému øe¹íme optimalizaèní, jednak pøedmìty
-mají ceny (pøedchozí verze odpovídala tomu, ¾e ceny jsou rovny hmotnostem).
-Uká¾eme si algoritmus pro øe¹ení tohoto obecného problému, jeho¾ èasová
-slo¾itost bude polynomiální v~poètu pøedmìtù~$n$ a souètu v¹ech cen~$C=\sum_i
-c_i$.
-
-\>Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
-pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost
-podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$:
-Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=infty$ pro $c>0$. Pokud ji¾ známe
+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$
+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á.
+
+Uká¾eme algoritmus, jeho¾ èasová slo¾itost bude polynomiální v~poètu
+pøedmìtù~$n$ a souètu v¹ech cen $C=\sum_i c_i$.
+
+Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
+pøedmìtù. Oznaème $A_k(c)$ (kde $0\le c\le C$) minimum z~hmotností tìch podmno¾in
+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
$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) =
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í. Tedy:
+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).
$$
-Tímto zpùsobem v~èase $\O(C)$ spoèteme $A_k(c)$ pro fixní $k$ a v¹echna $c$,
-v~èase $\O(nC)$ pak v¹echny $A_k(c)$.
+Pøechod od $A_{k-1}$ k~$A_k$ tedy trvá $\O(C)$, pro v¹echna~$k$ pak $\O(Cn)$.
-\>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do~batohu.
-To bude nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) \le H$. Jeho nalezení nás stojí
-èas $\O(C)$.
+Jakmile spoèteme~$A_n$, známe pro ka¾dou cenu nejlehèí podmno¾inu s~touto cenou.
+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)$.
-\>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,
+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,
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
prvku k~prvnímu.
-\>Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í
-problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ($C$~mù¾e
-být a¾ exponenciálnì velké vzhledem k~velikosti vstupu), ale pouze ve~velikosti
-èísel na~vstupu. Takovým algoritmùm se øíká {\I pseudopolynomiální.} Ani takové
-algoritmy ale nejsou k dispozici pro v¹echny problémy (napø. u problému obchodního
-cestujícího nám vùbec nepomù¾e, ¾e váhy hran budou malá èísla).
-
-\s{Verze bez cen:} Na verzi s~cenami rovnými hmotnostem se dá pou¾ít
-i jiný algoritmus zalo¾ený na~dynamickém programování: poèítá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ù. Pøitom $Z_0=\{0\}$, $Z_k$
-spoèteme ze~$Z_{k-1}$ --- udr¾ujme si $Z_{k-1}$ jako setøídìný spojový seznam,
-výpoèet dal¹ího seznamu udìláme slitím dvou seznamù $Z_{k-1}$ a $Z_{k-1}$ se
-v¹emi prvky zvý¹enými o hmotnost $k$ zahazujíce duplicitní a pøíli¹ velké hodnoty ---
-a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
-mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$.
+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ý
+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.
+
+\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
+programování.
+
+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.
+
+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
+dobìhne v~èase $\O(Hn)$.
\h{Aproximace problému obchodního cestujícího}
\>{\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
+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
\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
+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
+
+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
\varepsilon n+1 &< c
}
$$
-\>Kdyby takový algoritmus existoval, máme polynomiální algoritmus
+Kdyby takový algoritmus existoval, máme polynomiální algoritmus
na~hamiltonovskou kru¾nici.
\qed
projects / ads2.git / blobdiff