{{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^{\ast }$ hodnotu optimálního řešení

• $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 $\rho (n)$, pokud pro každé zadání velikosti $n$ platí:

:$\max \{\frac{C^{\ast }}{C},\frac{C}{C^{\ast }}\}\le \rho (n)$

Definice (Relativní chyba)

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

:$\frac{|C-C^{\ast }|}{C^{\ast }}\le \epsilon (n)$

Poznámka (O převodu chyb)

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

• V případě maximalizační úlohy: $\epsilon (n)=\frac{C-C^{\ast }}{C^{\ast }}=\frac{C}{C^{\ast }}-1=\rho (n)-1$

• V případě minimalizační úlohy: $\epsilon (n)=\frac{C^{\ast }-C}{C^{\ast }}=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 $\rho (k)\le 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$" má relativní chybu $2$ -- žádné 2 hrany nemají společný vrchol, tj. mám pokrytí o velikosti $2\times |$mn. disj. hran$|$. Každé vrcholové pokrytí je ale $\ge |$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$

2. Zvol lib. vrchol a pomocí DFS nad $T$ v PRE-ORDERu očísluj vrcholy.

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

4. Výslednou HK $H$ vyrobím zkrácením cesty (vypouštěním již navštívených vrcholů), z trojúhelníkové nerovnosti $w(H)\le w(X)$. Celkem tedy dává $w(H)\le w(X)\le 2w(H^{\ast })$, protože $w(T)\le w(H^{\ast })$ ($H^{\ast }$ 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)$, pak zadání TSP zkonstruovat jako $K_{|V|}(V,V\times V)$, kde $w(e)=\{\begin{array}{ll}1& e\in E\\ |V|\rho & e\notin E\end{array}$. 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 $\epsilon >0$, a který pro libovolné $\epsilon$ pracuje jako aproximační algoritmus s relativní chybou $\epsilon$. Doba běhu může být exponenciální jak vzhledem k $n$ -- velikosti vstupní instance, tak vzhledem k $\frac{1}{\epsilon }$.

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

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

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 $\frac{1}{\epsilon }$ (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 $n$ hmotností predmetov $w_1,w_2,\dots w_n$, obmedzenie $W$ na celkovú hmotnosť a hodnoty predmetov $v_1,v_2,\dots ,v_n$.

Úlohou je nájsť takú množinu $S\subset \{1,2,\dots ,n\}$, aby ${\sum }_{i\in S}{w}_i\le W$ a ${\sum }_{i\in S}{v}_i$ bolo čo najväčšie.

Nech $V=\max \{v_1,v_2,\dots ,v_n\}$. Zadefinujme si $W(i,v)$ ako najmenšia hmotnosť takej podmnožiny predmetov $\{w_1,\dots w_i\}$, ktorých celková hodnota je práve $v$. 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 $i$, lebo by sme prekročili cenu $v$ (spomeňme si na definíciu $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)\le W\}$. Tento algoritmus bude mať zložitosť $n^{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$, tak orežeme $b=\lceil log\frac{ϵ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é $i$ je hodnota predmetu $v_i^{\prime }=2^b\lfloor \frac{v_j}{2^b}\rfloor$. Náš algoritmus bude potrebovať čas $O(\frac{n^{2}V}{2^b})$ (pretože ignorujeme nulové bity na konci každej hodnoty predmetu). Riešenie $S^{\prime }$, ktoré dostaneme bude možno rôzne od optima $S$ pôvodnej úlohy, ale bude platiť:

:${\sum }_{i\in S}{v}_i\ge {\sum }_{i\in S^{\prime }}{v}_i\ge {\sum }_{i\in S^{\prime }}{v}_i^{\prime }\ge {\sum }_{i\in S}{v}_i^{\prime }\ge {\sum }_{i\in S}(v_i-2^b)\ge {\sum }_{i\in S}{v}_i-n{2}^b$

Prvá nerovnosť platí, lebo $S$ je optimum v pôvodnej úlohe, druhá lebo $v_i^{\prime }\le v_i$, tretia lebo $S^{\prime }$ je optimum novej úlohy, štvrtá lebo $v_i^{\prime }\ge v_i-2^b$ a posledná lebo $|S|\le n$. Naše riešenie je teda najviac $n{2}^b$ pod optimom. Dolný odhad optima je $V$ (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é $ϵ$ orežeme $b=\lceil log\frac{ϵV}{n}\rceil$ bitov a dostaneme algoritmus, ktorého relatívna chyba je $ϵ$ a jeho časová zložitosť je $O(\frac{n^{2}V}{2^b})=O(\frac{n^3}{ϵ})$, čo je polynomiálne aj v $n$ aj v $\frac{1}{ϵ}$, preto je to úplná polynomiálna aproximačná schéma.

{{Statnice I3}}