{{Sources|
*Ze zápisků k zkoušce z [ZSV](Řešené_otázky_NTIN090)*
09/10, 14/15: Aproximacní algoritmy a schémata.
}}
## Aproximační algoritmy - definice a příklad (6×🎓) ##
{{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, konzultace)** - definice Aproximační algoritmy a schémata a jejich souvislost s pseudopolynom. algoritmy, příklad schémata pro batoh nebo soucet podmnozin
* **Aproximacni schemata (2014, Kučera)** - 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 :-)
}}
**Optimalizační úloha** *A* je buď **maximalizační** nebo **minimalizační** a skládá se z těchto tří částí:
1. **Množina instancí *DA*** ⊆ {0, 1}*
1. **Množina přípustných řešení** ***SA*(*I*)** ⊆ {0, 1}* , ∀*I *∈* DA*
1. **Hodnota řešení **σ je fce ***μA*(*I*, σ)**'' '', která ∀*I *∈* DA* a ∀přípustnému řešení σ ∈ *SA*(*I*) přiřadí kladné racionální číslo *μA*(*I*, σ)
* **Optimální řešení** **σ** ∈ *SA*(*I*), pro něž je *μA*(*I*, σ) maximální (pro maximalizační úlohu *A*) nebo minimální (pro minimalizační *A*)
* 💡 tj. pro maximalizační: *μA*(*I*, σ) = max{ *μA*(*I*, σ) | σ ∈ *SA*(*I*) }
* 💡 tj. pro minimalizační: *μA*(*I*, σ) = min{ *μA*(*I*, σ) | σ ∈ *SA*(*I*) }
* ***OPTA*(*I*)** je **hodnota optimálního řešení** instance *I* ∈ *DA*
* 💡 tj. *OPTA*(*I*)** **= *μA*(*I*, σ), kde σ je optimální řešení intance *I*
* ***ALG*** je **aproximačním algoritmem** pro optimalizační úlohu *A*, pokud ∀vstup *I *∈* DA* vrátí řešení σ ∈ *SA*(*I*)
* 💡 pro *SA*(*I*) = ∅ ohlásí že přípustné řešení neexistuje
* ***ALG*(*I*)** je **hodnota řešení** *ALG* na instanci *I *∈* DA*
* 💡 v tj. *ALG*(*I*) = *μA*(*I*, σ), kde σ ∈ *SA*(*I*) je přípustné řešení vrácené algoritmem *ALG*
* **Aproximační poměr ε ≥ 1** algoritmu ALG pokud ∀*I *∈* DA* platí: $ε ≥ max\left\{ \frac{OPT(I)}{ALG(I)}, \frac{ALG(I)}{OPT(I)} \right\}$
* tj. *OPT*(*I*) ≤ ε·*ALG*(*I*) (maximalizační úlohy)
* *ALG*(*I*) ≤ ε·*OPT*(*I*) (minimalizační úlohy)
* 💡 nekdy se nazývá také **poměrová chyba** a značí se ρ(*n*)
* $\text{"relativní chyba"} ≥ \frac{|ALG(I)-OPT(I)|}{OPT(I)}$
### Příklad aproximačního algoritmu pro Bin Packing ###
Bin Packing – BP, úloha
::
* **Instance :** Konečná množina předmětů *U* = {*u*₁, .., *u*ₙ}, s každým předmětem asociovaná velikost 0 ≤ *s*(*u*) ≤ 1, což je racionální číslo.
* **Cíl :** Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin *U*₁, .., *U*ₘ takové, že každá množina může mít velikost max 1.
:: 💡 Naším cílem je tedy minimalizovat *m*.
Algoritmus (First Fit pro Bin Packing – *FF-BP* - 💡 zřejmě polynomiální)
::
* Ber jeden předmět po druhém,
* ∀ předmět *u* 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 *u*
{{theorem
| ∀ instanci *I* ∈ *DBP* platí, že *FF*-*BP*(*I*) <2·*OPT*BP
| Aproximační poměr *FF-BP* je 2 - tj. max 2x horší než optimum
}}
{{collapse|Dk:|2=
:: V řešení, které vrátí $FF-BP$ je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše $U_i$ a $U_j$ pro $i 1$, pak z toho plyne, že: $FF-BP(I) <⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉$, 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 $OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉$.
:: Dohromady tedy dostaneme, že $FF-BP(I) <2.OPT(I)$. Pokud $FF-BP(I) = 1$, pak i $OPT(I) = 1$ a i v tomto případě platí ostrá nerovnost.
}}
### Aproximační schémata (🎓) ###
***ALG*(*I*, ε)** je **aproximačním schématem** pro úlohu *A,* pokud pro *I *∈* DA* a racionální číslo **ε > 0** vydá řešení σ ∈ *SA*(*I*), jehož hodnota se od optimální liší s **aproximačním poměrem** $ (1 + ε) ≥ max\left\{ \frac{OPT(I)}{ALG(I, ε)}, \frac{ALG(I, ε)}{OPT(I)} \right\}$
* Tj. pro maximalizační úlohu platí, že: *OPT*(*I*) ≤ (1 + ε) *ALG*(*I*, ε)
* a pro minimalizační úlohu platí, že: *ALG*(*I, ε*) ≤ (1 + ε) *OPT*(*I*)
***ALG***'''ε''' je instance algoritmu *ALG* se zafixovanou ε
* *ALG* je **polynomiální aproximační schéma** (**PAS**), pokud *ALG*ε má časovou složitost polynomiální v len(*I*) (💡 tj. délce vstupu *n*, ∀ε)
* *ALG* je **úplně polynomiální aproximační schéma** (**ÚPAS**), pokud *ALG* má časovou složitost polynomiální v len(*I*) a 1/ϵ
* 💡 tj. PAS může mít 1/ϵ v exponentu čas.složitosti (např. O(n1/ϵ)) ale ÚPAS nesmí
Příklad ÚPAS pro Batoh - BAPX
::
* **Vstup:** Velikost batohu *B*, pole 0 <*s*\[1..n] ≤ *B* velikostí předmětů a pole *v*\[1..n] cen předmětů, racionální číslo ε > 0.
* **Otázka:** Množina *M* předmětů, jejichž souhrnná velikost nepřesahuje *B*, maximalizujeme celkovou cenu.
**BAPX(*s*, *v*, *B*, ε)**
1. urči *v*\[*m*] největší cenu
1. if (1 + ε ≥ *n*) return {*m*} //*nemá cenu pokračovat, zaokrouhlili bysme moc*
1. *t* = ⌊log₂( ε·*v*\[*m*] / *n* )⌋ - 1
1. *c* je nové pole délky *n*
1. for (*i* = 1; *i* ≤ *n*; *i*++) *c*\[*i*] = ⌊*v*\[*i*] / 2ᵗ⌋
1. return Batoh(*s*, *c*, *B*) //*volání původního [pseudopolynomiálního algoritmu](Státnice_-_NP-úplnost_I2#Pseudopolynomi.C3.A1ln.C3.AD_algoritmy.2C_siln.C3.A1_NP-.C3.BAplnost._.286.C3.97.F0.9F.8E.93.29)* iterující přes *V* = Σ*v*
💡 není nutné znát všechny logaritmy v algoritmu, jenom nějak stručně vysvětlit myšlenku
💡 snažíme se omezit celkovou cenu *V = Σv*, algoritmus přeškáluje (normalizuje) ceny předmětů pomocí ε a *v*\[*m*] a zaokrouhlí na ⌊⌋
💡 Předpokládáme, že (∀*i* ∈ {1, ..., *n*}) \[0 < *s*\[*i*] ≤ *B*]
* Schéma BAPX pracuje v čase **O(*n*³ / ε)**
{{Statnice I2}}