==Aproximační algoritmy - definice a příklad (5×🎓)==
{{Zkazky|
* '''Aproximacní algoritmy (2015)''' - Definice, chtel pomerovou i relativni chybu. Ukazal jsem algoritmus pro BIN PACKING, ktery je nejhure 2x horsi nez optimalni algoritmus. Pak definice aproximacniho schematu, polynomialniho apr. sch. i uplnepolynomialniho apr. schematu. Byl jsem dotazan, zda znam nejake schema (Batoh podle poznmek pana Kucery) a jake schema to je (uplne polynomialni nebo jen polynomialni).
* '''Aproximacni schemata (2014)''' - definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, - schema pre BATOH
* '''Aproximacne alg a schemy (2009, Fiala)''' - Pripraveny papier posluzil na prvu minutu, kedy si to skusajuci precital. Mal som tam plus minus vsetko. Este sa opytal preco nemozem TSP aproximovat s lubovolne malou chybou (v nejakom rozumnom case). Nevedel som , tak mi pomohol otazkou: Co sa stane, ak mi niekto da graf na 100 vrcholoch a povoli chybu pod 1%? Musel by som najst optimalne riesenie. Velmi rychla odpoved.
* '''Aproximacne algoritmy (2009, Loebl?)''' - Pripravil som si 2 a4 s definiciami AA, pom. rel. chyba, AS, PAS, UPAS. Nakoniec som dal priklad vrch.pokrytie s dokazom ze pom.chyba je 2. Skusajuci to asi za 5s preletel ocami a spytal sa ci viem zlozitejsi algortimus, na co som odpovedal ze nie a on ze ok a koniec. Odhad:2
* '''Aproximační algoritmy a schémata (2009, Majerech)''' - Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP
* '''Pseudopolynomiální algoritmy a aproximační schémata (2008, Trpělivý teoretik)''' - Napsal jsem špatnou definici pseudopolynomiálních algoritmů, aproximací, AS, a ÚPAS. Na dotaz jestli znám nějaké AS jsem zmínil UPAS pro SP, a to že patrně obsahuje nějakou proceduru co cosi prořezává. Posléze se mi podařilo přijít na správnou definici pseudopolynomiálních algoritmů, a to jak by zhruba měl vypadat pseudopolynomiální algoritmus pro problém batohu. Tou dobou ale už všichni ze zkoušky odešli tak mě nechal jít :-)
}}
{{TODO|poměrová a relativní chyba}}
'''Optimalizační úloha''' A je buď '''maximalizační''' nebo '''minimalizační''' a skládá se z těchto tří částí:
:# Množina instancí <math>D_A ⊆ \{0, 1\}^*</math>.
:# Pro každou instanci <math>I ∈ D_A</math> je dána množina přípustných řešení <math>S_A(I) ⊆ \{0, 1\}^*</math>.
:# Funkce <math>μ_A</math>, která každé instanci <math>I ∈ D_A</math> a každému přípustnému řešení <math>σ ∈ S_A(I)</math> přiřadí kladné racionální číslo <math>μ_A(I, σ)</math>, které nazveme '''hodnotou řešení''' σ.
* Pokud je A maximalizační úlohou, pak '''optimálním řešením''' instance <math>I ∈ D_A</math> je <math>σ ∈ S_A(I)</math>, pro něž je <math>μ_A(I, σ)</math> maximální (tj. <math>μ_A(I, σ) = max\{μ_A(I, σ) | σ ∈ S_A(I)\}</math>).
** Pokud je <math>A</math> minimalizační úlohou, pak optimálním řešením instance <math>I ∈ D_A</math> je <math>σ ∈ S_A(I)</math>, pro něž je <math>μ_A(I, σ)</math> minimální (tj. <math>μ_A(I, σ) = min\{μ_A(I, σ) | σ ∈ S_A(I)\}</math>).
** '''Hodnotu optimálního řešení''' instance <math>I ∈ D_A</math> označujeme <math>OPT_A(I)= μ_A(I, σ)</math> (kde <math>σ</math> je optimální řešení intance <math>I</math>).
* Řekneme, že algoritmus <math>ALG</math> je '''aproximačním algoritmem''' pro optimalizační úlohu <math>A</math>, pokud pro každou instanci <math>I ∈ D_A</math> vrátí <math>ALG</math> se vstupem <math>I</math> řešení <math>σ ∈ S_A(I)</math>, případně ohlásí, že žádné přípustné řešení neexistuje, pokud <math>S_A(I) = ∅</math>.
* Hodnotu řešení vráceného algoritmem <math>ALG</math> na instanci <math>I</math> označíme jako <math>ALG(I)</math>, tj. <math>ALG(I) = μ_A(I, σ)</math>, kde <math>σ ∈ S_A(I)</math> je přípustné řešení vrácené algoritmem <math>ALG</math>.
* Pokud je <math>A</math> maximalizační úloha, pak racionální číslo <math>ε ≥ 1</math> nazveme '''aproximačním poměrem''' algoritmu <math>ALG</math>, pokud pro každou instanci <math>I ∈ D_A</math> platí, že <math>OPT (I) ≤ ε.ALG(I)</math> .
** Je-li <math>A</math> minimalizační úlohou, pak racionální číslo <math>ε ≥ 1</math> nazveme '''aproximačním poměrem''' algoritmu <math>ALG</math>, pokud pro každou instanci <math>I ∈ D_A</math> platí, že <math>ALG(I) ≤ ε.OPT(I)</math> .
=== Příklad aproximačního algoritmu pro Bin Packing ===
; Bin Packing – BP, úloha:
* '''Instance :''' Konečná množina předmětů <math>U = {u_1, .., u_n}</math>, s každým předmětem asociovaná velikost <math>s(u)</math>, což je racionální číslo, pro které platí <math>0 ≤ s(u) ≤ 1</math>.
* '''Cíl :''' Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin <math>U_1, . . ., U_m</math> takové, že každá množina může mít velikost max 1.
: 💡 Naším cílem je tedy minimalizovat <math>m</math>.
: 💡 Formálně je tedy <math>D_{BP}</math> množinou řetězců kódujících instance <math>BP</math>, pro danou instanci <math>I= ⟨U, s(u)⟩</math> je množina <math>S_BP(I)</math> množinou všech možných rozdělení do dostatečného množství košů. Mírou řešení <math>μ_{BP}(σ)</math> pro <math>σ ∈ S_{BP}(I)</math> je počet košů, které řešení využívá, tedy hodnota <math>m</math>. Rozhodovací verze tohoto problému je shodná s problémem Rozvrhování, o jehož těžkosti víme, z toho plyne, že i úloha <math>BP</math> je <math>NP</math>-těžká. Šance na to, že bychom našli polynomiální algoritmus, řešící <math>BP</math> přesně, jsou tedy malé.
; Algoritmus (First Fit pro Bin Packing – <math>FF-BP</math>):
* Ber jeden předmět po druhém,
** ∀ předmět <math>u</math> najdi první koš, do nějž se tento předmět ještě vejde,
** pokud takový koš neexistuje, přidej nový koš obsahující jen předmět <math>u</math>.
💡 Algoritmus <math>FF-BP</math> je zřejmě polynomiální.
{{theorem
| ∀ instanci <math>I ∈ DBP</math> platí, že <math>FF-BP(I) < 2.OPT_{BP}(I)</math>.
| Aproximační poměr <math>FF-BP</math> je 2
}}
;Dk:
: V řešení, které vrátí <math>FF-BP</math> je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše <math>U_i</math> a <math>U_j</math> pro <math>i < j</math>, které jsou zaplněny nejvýš z poloviny, tak by <math>FF-BP</math> nepotřeboval zakládat nový koš pro předměty z <math>U_j</math>, všechny by se vešly do <math>U_i</math>.
: Pokud <math>FF-BP(I) > 1</math>, pak z toho plyne, že: <math>FF-BP(I) < ⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉</math>, kde první nerovnost plyne z toho, že po zdvojnásobení obsahu jsou všechny koše plné až na jeden, který může být zaplněn jen částečně.
: Rovnosti bychom přitom dosáhli jedině ve chvíli, kdy by byly všechny koše zaplněné právě z poloviny, což není podle našeho předpokladu možné.
: Druhá nerovnost plyne z vlastností zaokrouhlování.
: Na druhou stranu musí platit, že <math>OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉</math>.
: Dohromady tedy dostaneme, že <math>FF-BP(I) < 2.OPT(I)</math>. Pokud <math>FF-BP(I) = 1</math>, pak i <math>OPT(I) = 1</math> a i v tomto případě platí ostrá nerovnost.
==Aproximační schémata, př. (🎓)==
[[Image:Schemes.jpg|right|thumb|485px|💡 inkluze tříd NP, APX, PAS, ÚPAS, P a Pseudo-PTIME]]
{{Zkazky|
* definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, schema pre BATOH
}}
Nechť <math>A</math> je libovolná optimalizační úloha. Algoritmus <math>ALG</math> nazveme '''aproximačním schématem''' pro úlohu <math>A</math>, pokud na vstupu očekává instanci <math>I\in D_A</math> a racionální číslo <math>\varepsilon>0</math> a na výstupu vydá řešení <math>\sigma\in S_A(I)</math>, jehož hodnota se od optimální liší s aproximačním poměrem <math>(1+\varepsilon)</math>.
* Tj. pro maximalizační úlohu platí, že: <math>OPT(I)\leq(1+\varepsilon)ALG(I, \varepsilon)</math>
* a pro minimalizační úlohu platí, že: <math>ALG(I, \varepsilon)\leq(1+\varepsilon)OPT(I)\;.</math>
Předpokládejme, že algoritmus <math>ALG</math> je aproximační schéma a očekává na vstupu instanci <math>I\in D_A</math> a racionální číslo <math>\varepsilon</math>. Pomocí <math>ALG_\varepsilon</math> označíme instanci algoritmu <math>ALG</math>, kde hodnota <math>\varepsilon</math> je zafixována, vstupem <math>ALG_\varepsilon</math> je tedy jen instance <math>I\in D_A</math> a běh i výstup <math>ALG_\varepsilon</math> na vstupu <math>I</math> jsou totožné s algoritmem <math>ALG</math> se vstupem <math>I</math> a <math>\varepsilon</math>.
* Řekneme, že <math>ALG</math> je '''polynomiální aproximační schéma''' ('''PAS'''), pokud je pro každé <math>\varepsilon</math> časová složitost algoritmu <math>ALG_\varepsilon</math> polynomiální v <math>len(I)</math>, kde <math>ALG_\varepsilon</math> označuje algoritmus vzniklý dosazením konstanty <math>\varepsilon</math> do <math>ALG</math>
* Řekneme, že <math>ALG</math> je '''úplně polynomiální aproximační schéma''' ('''ÚPAS'''), pokud <math>ALG</math> pracuje v čase polynomiálním v <math>len(I)</math> a <math>\frac{1}{\varepsilon}</math>.
{{theorem
| Nechť <math>A</math> je optimalizační úloha, jejíž přípustná řešení mají nezápornou celočíselnou hodnotu. Předpokládejme, že ∃ polynom dvou proměnných <math>q</math>, který pro každou instanci <math>I ∈ DA</math> splňuje: <math>OPT(I) < q(len(I), max(I))</math>. Pokud ∃ úplně polynomiální aproximační schéma pro úlohu <math>A</math>, pak ∃ i pseudopolynomiální algoritmus pro <math>A</math>.
|
}}
💡 '''Důsledek :''' Nechť <math>A</math> je silně NP-úplná optimalizační úloha, která splňuje předpoklady věty. Pokud <math>P = NP</math>, pak neexistuje úplně polynomiální aproximační schéma pro úlohu <math>A</math>.
{{theorem
| Pokud existuje polynomiální aproximační algoritmus <math>ALG</math> pro úlohu obchodního cestujícího s aproximačním poměrem <math>ε</math>, kde <math>ε > 1</math> je konstanta, potom <math>P = NP</math>.
|
}}
[[Image:Schemes-input.jpg|right|thumb|502px|'''💡 př. použití aprox.schématu''': <math>I</math> je moc složitá pro přímé nalezení <math>OPT</math>, zjednodušíme jí tedy a získáme řešení <math>ALG_\varepsilon(I)</math> to ještě můžeme přeložit zpět na řešení odpovídající původní instanci <math>I</math> (u BAPX to ani není nutné)]]
{{collapse|Příklad aproximačního schématu pro Batoh - BAPX|2=
* '''Vstup:''' Pole <math>s</math> velikostí předmětů a pole <math>v</math> cen předmětů, obě délky <math>n</math>, velikost batohu <math>B</math>, racionální číslo <math>\varepsilon>0</math>. Předpokládáme, že <math>(\forall i\in\{1, \dots, n\})\;\big[0<s[i]\leq B\big]</math>
* '''Otázka:''' Množina M předmětů, jejichž souhrnná velikost nepřesahuje B.
<math>BAPX(s, v, B, \varepsilon)</math>
:# Spočti index m, pro nějž je <math>v[m] = max_{1\leq i\leq n} v[i]</math>.
:# if (<math>\varepsilon \geq n - 1</math>) return {m}
:# <math>t = ⌊log_2( \varepsilon v[m]/n )⌋ - 1</math>
:# c je nové pole délky n.
:# for (<math>i= 1; i\leq n;i++</math>) <math>c[i] = ⌊v[i]/2^t⌋</math>
:# return Batoh(s, c, B) // Volání původního algoritmu
💡 algoritmus provede zaokrouhlení cen předmětů a jejich přeškálování podle <math>ε</math>
{{theorem
| Schéma BAPX pracuje v čase <math>O(\frac{1}{\varepsilon}n^3)</math>. Pro libovolnou instanci <math>I = ⟨s, v, B⟩</math> úlohy Batoh a libovolné <math>ε > 0</math> platí, že <math>OPT(I) ≤ (1 + ε) BAPX(I, ε)</math>.
| Algoritmus BAPX je <math>O(\frac{1}{\varepsilon}n^3)</math>
}}
}}
{{Statnice I2}}
