{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke <Státnice> ze <Státnice_-Informatika-Složitost%28obory_Matematická_lingvistika_a_Softwarové_systémy%29> pro obory <Státnice_-Informatika-_I3:Matematická_lingvistika> a <Státnice-Informatika-_I2:_Softwarové_systémy>, pocházející ze zápisků z předmětu Složitost I -- User:Tuetschek 22:44, 16 Aug 2010 (CEST)

}}

Aproximační algoritmy

Definice (Aproximační algoritmus)

Aproximační algoritmus běží v polynomiálním čase a vrací řešení "blízká" optimu. Je nutné mít nějakou míru kvality řešení. Označme:

  • C∗  ⁣ C^{*}\,\! hodnotu optimálního řešení

  • C  ⁣ C\,\! hodnotu nalezenou aproximačním algoritmem

A předpokládejme nezáporné hodnoty řešení.

Definice (Poměrová chyba)

Řekneme, že algoritmus řeší problém s poměrovou chybou ρ(n)  ⁣ \rho(n)\,\!, pokud pro každé zadání velikosti n  ⁣ n\,\! platí:

:max⁡{C∗C,CC∗}≤ρ(n)  ⁣\max\{\frac{C^{*}}{C},\frac{C}{C^{*}}\}\leq \rho(n)\,\!

Definice (Relativní chyba)

Řekneme, že algoritmus řeší problém s relativní chybou ε(n)  ⁣ \varepsilon(n)\,\!, pokud pro každé zadání velikosti n  ⁣ n\,\! platí:

:∣C−C∗∣C∗≤ε(n)  ⁣\frac{|C-C^{*}|}{C^{*}}\leq \varepsilon(n)\,\!

Poznámka (O převodu chyb)

Z jedné chyby se dá vyjádřit druhá:

  • V případě maximalizační úlohy: ε(n)=C−C∗C∗=CC∗−1=ρ(n)−1  ⁣ \varepsilon(n) = \frac{C-C^{*}}{C^{*}}=\frac{C}{C^{*}}-1=\rho(n)-1\,\!

  • V případě minimalizační úlohy: ε(n)=C∗−CC∗=1−1ρ(n)  ⁣ \varepsilon(n) = \frac{C^{*}-C}{C^{*}}=1-\frac{1}{\rho(n)}\,\!

Příklad (Aproximační algoritmy pro vrcholové pokrytí)

  • "Brát vrcholy od nejvyššího stupně, dokud nemám celé pokrytí" nemá konstantní relativní chybu -- ex. protipříklad, kdy ρ(k)≤a⋅ln⁡k  ⁣ \rho(k)\leq a\cdot\ln k\,\!

  • "Vzít libovolnou hranu, dát do pokrytí její dva konce, odstranit její incidentní hrany a projít tak celé E  ⁣ E\,\!" má relativní chybu 2  ⁣ 2\,\! -- žádné 2 hrany nemají společný vrchol, tj. mám pokrytí o velikosti 2×∣  ⁣ 2\times|\,\!mn. disj. hran∣  ⁣ |\,\!. Každé vrcholové pokrytí je ale ≥∣  ⁣ \geq|\,\!mn. disj. hran∣  ⁣ |\,\!.

Příklad (Aproximační algoritmy pro TSP)

Omezení na trojúhelníkovou nerovnost -- pořád je NP (převod HK→  ⁣ \to\,\!TSP zachovával trojúhelníkovou nerovnost). Algoritmus:

  1. Najdi minimální kostru T  ⁣ T\,\!

  2. Zvol lib. vrchol a pomocí DFS nad T  ⁣ T\,\! v PRE-ORDERu očísluj vrcholy.

  3. Cesta (s opakováním) po kostře T  ⁣ T\,\! přes všechny vrcholy :=X  ⁣ := X\,\!. Pak w(X)=2w(T)  ⁣ w(X)=2 w(T)\,\! (každou hranou kostry jdu tam a zpět).

  4. Výslednou HK H  ⁣ H\,\! vyrobím zkrácením cesty (vypouštěním již navštívených vrcholů), z trojúhelníkové nerovnosti w(H)≤w(X)  ⁣ w(H)\leq w(X)\,\!. Celkem tedy dává w(H)≤w(X)≤2w(H∗)  ⁣ w(H)\leq w(X)\leq 2w(H^{*})\,\!, protože w(T)≤w(H∗)  ⁣ w(T)\leq w(H^{*})\,\! (H∗  ⁣ H^{*}\,\! je kostra, bez jedné hrany).

Bez omezení -- pro žádné konstantní ρ  ⁣ \rho\,\! neexistuje polynomiální algoritmus, řešící obecný TSP s poměrovou chybou ρ  ⁣ \rho\,\!. Mohu totiž mít HK v grafu G=(V,E)  ⁣ G=(V,E)\,\!, pak zadání TSP zkonstruovat jako K∣V∣(V,V×V)  ⁣ K_{|V|}(V,V\times V)\,\!, kde w(e)={1e∈E∣V∣ρe∉E  ⁣w(e)=\begin{cases}1 & e\in E \\ |V|\rho & e\notin E\end{cases}\,\!. Pak by aproximační algoritmus s chybou ρ  ⁣ \rho\,\! musel určitě vždy vrátit přesné řešení, takže by musel být NP-těžký.

Aproximační schémata

Definice (Aproximační schéma)

Aproximační schéma pro optimalizační úlohu je aproximační algoritmus, který má jako vstup instanci dané úlohy a číslo ε>0  ⁣ \varepsilon > 0\,\!, a který pro libovolné ε  ⁣ \varepsilon\,\! pracuje jako aproximační algoritmus s relativní chybou ε  ⁣ \varepsilon\,\!. Doba běhu může být exponenciální jak vzhledem k n  ⁣ n\,\! -- velikosti vstupní instance, tak vzhledem k 1ε  ⁣ \frac{1}{\varepsilon}\,\!.

Definice (Polynomiální aproximační schéma)

Polynomiální aproximační schéma je takové aproximační schéma, které pro každé pevné ε>0  ⁣ \varepsilon> 0\,\! běží v polynomiálním čase vzhledem k n  ⁣ n\,\! (ale stále může být exponenciální vzhledem k 1ε  ⁣ \frac{1}{\varepsilon}\,\!.

Definice (Úplně polynomiální aproximační schéma)

Úplně polynomiální aproximační schéma je polynomiální aprox. schéma, běžící také v polynomiálním čase vzhledem k 1ε  ⁣ \frac{1}{\varepsilon}\,\! (tj. algoritmus s konstantně-krát menší relativní chybou běží v konstantně-krát delším čase).

Úplná polynomiálna aproximačná schéma pre problém batohu

Zadanie pre "dvojrozmernú variantu" problému batohu je nn hmotností predmetov w1,w2,…wnw_1, w_2, \ldots w_n, obmedzenie WW na celkovú hmotnosť a hodnoty predmetov v1,v2,…,vnv_1, v_2, \ldots, v_n.

Úlohou je nájsť takú množinu S⊂{1,2,…,n}S \subset \{1, 2, \ldots, n\}, aby ∑i∈Swi≤W\sum_{i \in S}w_i \leq W a ∑i∈Svi\sum_{i \in S}v_i bolo čo najväčšie.

Nech V=max⁡{v1,v2,…,vn}V=\max\{v_1, v_2, \ldots, v_n\}. Zadefinujme si W(i,v)W(i,v) ako najmenšia hmotnosť takej podmnožiny predmetov {w1,…wi}\{w_1, \ldots w_i\}, ktorých celková hodnota je práve vv. Potom: :

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 118: …-1, v-v_i) \} &\̲m̲b̲o̲x̲{inak} \end{cas…

V treťom prípade nepridáme vec ii, lebo by sme prekročili cenu vv (spomeňme si na definíciu W(i,v)W(i,v)), v štvrtom ju pridáme ak nám nepokazí hmotnosť.

Pomocou tohto môžeme napísať algoritmus využívajúci dynamické programovanie a ako výsledok vrátime max⁡{v∣W(n,v)≤W}\max\{v | W(n,v) \leq W\}. Tento algoritmus bude mať zložitosť n2Vn^2 V, čo je iba pseudopolynomiálny algoritmus. Ten však môžeme upraviť.

Upravme si zadanie tak, že hodnoty všetkých predmetov orežeme o najnižšie bity. Ak chceme relatívnu chybu ϵ>0\epsilon > 0, tak orežeme b=⌈logϵVn⌉b= \lceil log \frac{\epsilon V}{n}\rceil bitov (nahradíme ich nulami) (prečo práve toľko bude vysvetlené nižšie). Tým sme získali novú inštanciu problému batohu, kde hmotnosti a limit sú rovnaké, ale pre každé ii je hodnota predmetu vi′=2b⌊vj2b⌋v'_i = 2^b \lfloor \frac{v_j}{2^b}\rfloor. Náš algoritmus bude potrebovať čas O(n2V2b)O(\frac{n^2V}{2^b}) (pretože ignorujeme nulové bity na konci každej hodnoty predmetu). Riešenie S′S', ktoré dostaneme bude možno rôzne od optima SS pôvodnej úlohy, ale bude platiť:

:∑i∈Svi≥∑i∈S′vi≥∑i∈S′vi′≥∑i∈Svi′≥∑i∈S(vi−2b)≥∑i∈Svi−n2b\sum_{i \in S} v_i \geq \sum_{i\in S'} v_i \geq \sum_{i \in S'}v'_i \geq \sum_{i \in S}v'_i \geq \sum_{i\in S}(v_i - 2^b) \geq \sum_{i\in S} v_i -n 2^b

Prvá nerovnosť platí, lebo SS je optimum v pôvodnej úlohe, druhá lebo vi′≤viv'_i \leq v_i, tretia lebo S′S' je optimum novej úlohy, štvrtá lebo vi′≥vi−2bv'_i \geq v_i - 2^b a posledná lebo ∣S∣≤n|S| \leq n. Naše riešenie je teda najviac n2bn 2^b pod optimom. Dolný odhad optima je VV (predpokladáme, že každý predmet sa samotný vmestí do batoha, ináč môžeme príliš ťažké predmety vyhodiť ako preprocessing). Relatívna chyba je teda

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 7: \frac{\̲m̲b̲o̲x̲{approx} - \mbo…

Takže pre zadané ϵ\epsilon orežeme b=⌈logϵVn⌉b = \lceil log \frac{\epsilon V}{n}\rceil bitov a dostaneme algoritmus, ktorého relatívna chyba je ϵ\epsilon a jeho časová zložitosť je O(n2V2b)=O(n3ϵ)O(\frac{n^2V}{2^b}) = O(\frac{n^3}{\epsilon}), čo je polynomiálne aj v nn aj v 1ϵ\frac{1}{\epsilon}, preto je to úplná polynomiálna aproximačná schéma.

{{Statnice I3}}