From bb87b43368286edcd814819ae81aa5c6a477d2ff Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 15 Jan 2012 13:30:47 +0100 Subject: [PATCH] APX: Uvod upraven a zmineny optimalizacni problemy --- 9-apx/9-apx.tex | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-) diff --git a/9-apx/9-apx.tex b/9-apx/9-apx.tex index 450cf67..960766d 100644 --- a/9-apx/9-apx.tex +++ b/9-apx/9-apx.tex @@ -1,11 +1,21 @@ \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 @@ -16,15 +26,16 @@ mo 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 -- 2.39.5