\input lecnotes.tex
-\prednaska{12}{Aproximaèní algoritmy}{(???)}
+\prednaska{12}{Aproximaèné algoritmy}{(F. Ha¹ko, J. Menda, M. Mare¹)}
-\h{Pseudopolynomiální algoritmus pro problém batohu}
+\>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.
-\s{POZOR:} Na~pøedná¹ce byla jen verze bez cen, nauète se, prosím, obì. --M.M.
+\h{Prvý spôsob: ©peciálny prípad}
-\s{Problém batohu:} Je dána mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$
-a cenami $c_1,\ldots,c_n$ a batoh, který unese hmotnost~$H$. Naleznìte takovou
-podmno¾inu pøedmìtù, jejich¾ celková hmotnost je nejvý¹e~$H$ a celková cena je
-maximální mo¾ná.
+\>È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.
-Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
+\s{Problém: Maximálna nezávislá mno¾ina v strome (nie rozhodovacia)}
+
+\>{\I Vstup:} zakorenený strom~$T$
+
+\>{\I Výstup:} Maximálna (èo do poètu vrcholov) nezávislá mno¾ina vrcholov~$M$
+
+\>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:
+\itemize\ibull
+\: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).
+\:Ak tam otec je, tak ho z~$M$ vyjmeme a~namiesto neho vlo¾íme~$l$ (veµkos» nezávislej mno¾iny sa nezmen¹ila).
+\endlist
+\>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.
+
+\s{Algoritmus:}
+\algo
+\:Polo¾íme $M_1$:=$\{$listy stromu $T\}$.
+\:Polo¾íme $M_2$:=$\{$otcovia vrcholov z~$M_1\}$.
+\:Vrátime $M_1 \cup$ MaxNz$(T\setminus(M_1 \cup M_2)$.
+\endalgo
+\>{\I Poznámka:} Toto doká¾eme naprogramova» v $\O(n)$ (vrcholy máme vo fronte a prechádzame).
+
+\s{Problém: Batoh}
+
+\>Je daná mno¾ina $n$~predmetov s~hmotnos»ami $h_1,\ldots,h_n$
+a cenami $c_1,\ldots,c_n$ a~batoh, ktorý unesie hmotnos»~$H$. Nájdite takú
+podmno¾inu predmetov, ktorých celková hmotnos» je najviac~$H$ a~celková cena je
+maximálna 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$
+\>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
$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$
+(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:
$$
$$
Tímto zpùsobem v~èase $\O(C)$ spoèteme jednu mno¾inu, v~èase $\O(nC)$ pak v¹echny.
-Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do batohu. To bude
+\>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^*) < \infty$. Jeho nalezení nás stojí èas $\O(C)$.
-A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,
+\>A~jak 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$~mu¾e být a¾ exponenciálnì
+\>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$~mu¾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í.}
\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á
+$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 z~$Z_{k-1}$ a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
+spoèteme ze~$Z_{k-1}$ 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)$.
+\h{Druhý spôsob: Aproximácia}
+
+\>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.
+
+\s{Problém: Obchodný cestujúci}
+
+\>{\I Vstup:} neorientovaný graf $G$, popisujúci nejaku krajinu a~ka¾dá hrana je ohodnotená funkciou $w: E(G)\rightarrow {\bb R}^+_0$
+
+\>{\I Vystup:} Hamiltonovská kru¾nica (v¹etky vrcholy grafu), a~to tá najkrat¹ia (podµa ohodnotenia).
+
+\>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.
+
+\>{\I a) trojuholníková nerovnos»:} $\forall x,y,z \in V: w(xz)\le w(xy)+w(yz)$
+
+\>Existuje pekný algoritmus, ktory nájde Hamiltonovsku kru¾nicu, èo je
+maximálne dvakrát tak veµká ako optimálna.
+
+\>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$.
+
+\>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.
+
+\>{\I b) bez~trojuholníkovej nerovnosti:}
+
+\>Tu sa budeme naopak sna¾i» ukáza», ¾e ¾iaden polynomiálny aproximaèný algoritmus neexistuje.
+
+\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$.
+
+\proof Uká¾eme, ¾e v~tom prípade doká¾eme v~polynomiálnom èase nájs» Hamiltonovskú kru¾nicu.
+
+\>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:
+\itemize\ibull
+\: $w(e) = 1$, ak $e \in E(G)$
+\: $w(e) = c \ll 1$, ak $e \not\in E(G)$
+\endlist
+\>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»
+$$
+\eqalign{
+(1+\varepsilon).n &< n-1+c \cr
+\varepsilon n+1 &< c
+}
+$$
+\>Ak by taký algoritmus existoval, tak na~neho máme polynomiálny algoritmus
+na~Hamiltonovsku kru¾nicu. Inak neexistuje ani pseudo-polynomialny algoritmus.
+\qed
+
\h{Aproximaèní schéma pro problém batohu}
\s{POZOR:} Verze algoritmu, kterou jsem øíkal na~pøedná¹ce, obsahovala jednu
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. Ø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í.
+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í.
\s{Základní my¹lenka:}
projects / ads2.git / blobdiff