{{Sources|
''Ze zápisků k zkoušce z [[Řešené_otázky_NTIN090|ZSV]]
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í:
# '''Množina instancí ''D<sub>A</sub>'''''<sub> </sub> ⊆ {0, 1}*
# '''Množina přípustných řešení''' '''''S<sub>A</sub>''(''I'')''' ⊆ {0, 1}* , ∀''I ''∈'' D<sub>A</sub>''
# '''Hodnota řešení '''σ je fce '''''μ<sub>A</sub>''(''I'', σ)'''<sub>'' ''</sub>, která ∀''I ''∈'' D<sub>A</sub>'' a ∀přípustnému řešení σ ∈ ''S<sub>A</sub>''(''I'') přiřadí kladné racionální číslo ''μ<sub>A</sub>''(''I'', σ)
* '''Optimální řešení''' '''σ''' ∈ ''S<sub>A</sub>''(''I''), pro něž je ''μ<sub>A</sub>''(''I'', σ) maximální (pro maximalizační úlohu ''A'') nebo minimální (pro minimalizační ''A'')
** 💡 tj. pro maximalizační: ''μ<sub>A</sub>''(''I'', σ) = max{ ''μ<sub>A</sub>''(''I'', σ) | σ ∈ ''S<sub>A</sub>''(''I'') }
** 💡 tj. pro minimalizační: ''μ<sub>A</sub>''(''I'', σ) = min{ ''μ<sub>A</sub>''(''I'', σ) | σ ∈ ''S<sub>A</sub>''(''I'') }
** '''''OPT<sub>A</sub>''(''I'')''' je '''hodnota optimálního řešení''' instance ''I'' ∈ ''D<sub>A</sub>''
*** 💡 tj. ''OPT<sub>A</sub>''(''I'')''' '''= ''μ<sub>A</sub>''(''I'', σ), kde σ je optimální řešení intance ''I''
* '''''ALG''''' je '''aproximačním algoritmem''' pro optimalizační úlohu ''A'', pokud ∀vstup ''I ''∈'' D<sub>A</sub>'' vrátí řešení σ ∈ ''S<sub>A</sub>''(''I'')
** 💡 pro ''S<sub>A</sub>''(''I'') = ∅ ohlásí že přípustné řešení neexistuje
* '''''ALG''(''I'')''' je '''hodnota řešení''' ''ALG'' na instanci ''I ''∈'' D<sub>A</sub>''
** 💡 v tj. ''ALG''(''I'') = ''μ<sub>A</sub>''(''I'', σ), kde σ ∈ ''S<sub>A</sub>''(''I'') je přípustné řešení vrácené algoritmem ''ALG''
* '''Aproximační poměr ε ≥ 1''' algoritmu ALG pokud ∀''I ''∈'' D<sub>A</sub>'' platí: <math>ε ≥ max\left\{ \frac{OPT(I)}{ALG(I)}, \frac{ALG(I)}{OPT(I)} \right\}</math>
** 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'')
* <math>\text{"relativní chyba"} ≥ \frac{|ALG(I)-OPT(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ů ''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''<sub>BP</sub>(''I'')
| Aproximační poměr ''FF-BP'' je 2 - tj. max 2x horší než optimum
}}
{{collapse|Dk:|2=
: 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 (🎓)===
'''''ALG''(''I'', ε)''' je '''aproximačním schématem''' pro úlohu ''A,'' pokud pro ''I ''∈'' D<sub>A</sub>'' a racionální číslo '''ε > 0''' vydá řešení σ ∈ ''S<sub>A</sub>''(''I''), jehož hodnota se od optimální liší s '''aproximačním poměrem''' <math> (1 + ε) ≥ max\left\{ \frac{OPT(I)}{ALG(I, ε)}, \frac{ALG(I, ε)}{OPT(I)} \right\}</math>
* 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'''''<sub>'''ε'''</sub> je instance algoritmu ''ALG'' se zafixovanou ε
* ''ALG'' je '''polynomiální aproximační schéma''' ('''PAS'''), pokud ''ALG''<sub>ε</sub> má časovou složitost polynomiální v <u>len(''I'')</u> (💡 tj. délce vstupu ''n'', ∀ε)
* ''ALG'' je '''úplně polynomiální aproximační schéma''' ('''ÚPAS'''), pokud ''ALG'' má časovou složitost polynomiální v <u>len(''I'') a 1/ϵ</u>
** 💡 tj. PAS může mít 1/ϵ v exponentu čas.složitosti (např. O(n<sup>1/ϵ</sup>)) ale ÚPAS <u>nesmí</u>
[[Image:Schemes-input.jpg|thumb|502px|'''💡 př. použití aprox.schématu''': ''I'' je moc složitá pro přímé nalezení ''OPT '', zjednodušíme jí tedy a získáme řešení ''ALG''<sub>ε</sub>(''I'') to ještě můžeme přeložit zpět na řešení odpovídající původní instanci ''I'' (u BAPX to ani není nutné)]]
;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'', ε)'''
# urči ''v''[''m''] největší cenu
# if (1 + ε ≥ ''n'') return {''m''} <font color="grey"> //''nemá cenu pokračovat, zaokrouhlili bysme moc''</font>
# ''t'' = ⌊log₂( ε·''v''[''m''] / ''n'' )⌋ - 1
# ''c'' je nové pole délky ''n''
# for (''i'' = 1; ''i'' ≤ ''n''; ''i''++) ''c''[''i''] = ⌊''v''[''i''] / 2ᵗ⌋
# return Batoh(''s'', ''c'', ''B'') <font color="grey"> //''volání původního [[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|pseudopolynomiálního algoritmu]]'' iterující přes ''V'' = Σ''v''</font>
💡 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}}
