{{TOC float}}
{{Sources| Tohle je poněkud obšírnější výcuc ke státnicovým okruhům ze složitosti pro obory Matematická lingvistika a Softwarové systémy, pocházející ze zápisků z předmětu Složitost I -- 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:
<math> C^{*}\,\!</math> hodnotu optimálního řešení
<math> C\,\!</math> 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 <math> \rho(n)\,\!</math>, pokud pro každé zadání velikosti <math> n\,\!</math> platí:
:<math>\max\{\frac{C^{*}}{C},\frac{C}{C^{*}}\}\leq \rho(n)\,\!</math>
Definice (Relativní chyba)
Řekneme, že algoritmus řeší problém s relativní chybou <math> \varepsilon(n)\,\!</math>, pokud pro každé zadání velikosti <math> n\,\!</math> platí:
:<math>\frac{|C-C^{*}|}{C^{*}}\leq \varepsilon(n)\,\!</math>
Poznámka (O převodu chyb)
Z jedné chyby se dá vyjádřit druhá:
V případě maximalizační úlohy: <math> \varepsilon(n) = \frac{C-C^{*}}{C^{*}}=\frac{C}{C^{*}}-1=\rho(n)-1\,\!</math>
V případě minimalizační úlohy: <math> \varepsilon(n) = \frac{C^{*}-C}{C^{*}}=1-\frac{1}{\rho(n)}\,\!</math>
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 <math> \rho(k)\leq a\cdot\ln k\,\!</math>
"Vzít libovolnou hranu, dát do pokrytí její dva konce, odstranit její incidentní hrany a projít tak celé <math> E\,\!</math>" má relativní chybu <math> 2\,\!</math> -- žádné 2 hrany nemají společný vrchol, tj. mám pokrytí o velikosti <math> 2\times|\,\!</math>mn. disj. hran<math> |\,\!</math>. Každé vrcholové pokrytí je ale <math> \geq|\,\!</math>mn. disj. hran<math> |\,\!</math>.
Příklad (Aproximační algoritmy pro TSP)
Omezení na trojúhelníkovou nerovnost -- pořád je NP (převod HK<math> \to\,\!</math>TSP zachovával trojúhelníkovou nerovnost). Algoritmus:
Najdi minimální kostru <math> T\,\!</math>
Zvol lib. vrchol a pomocí DFS nad <math> T\,\!</math> v PRE-ORDERu očísluj vrcholy.
Cesta (s opakováním) po kostře <math> T\,\!</math> přes všechny vrcholy <math> := X\,\!</math>. Pak <math> w(X)=2 w(T)\,\!</math> (každou hranou kostry jdu tam a zpět).
Výslednou HK <math> H\,\!</math> vyrobím zkrácením cesty (vypouštěním již navštívených vrcholů), z trojúhelníkové nerovnosti <math> w(H)\leq w(X)\,\!</math>. Celkem tedy dává <math> w(H)\leq w(X)\leq 2w(H^{*})\,\!</math>, protože <math> w(T)\leq w(H^{*})\,\!</math> (<math> H^{*}\,\!</math> je kostra, bez jedné hrany).
Bez omezení -- pro žádné konstantní <math> \rho\,\!</math> neexistuje polynomiální algoritmus, řešící obecný TSP s poměrovou chybou <math> \rho\,\!</math>. Mohu totiž mít HK v grafu <math> G=(V,E)\,\!</math>, pak zadání TSP zkonstruovat jako <math> K_{|V|}(V,V\times V)\,\!</math>, kde <math>w(e)=\begin{cases}1 & e\in E \\ |V|\rho & e\notin E\end{cases}\,\!</math>. Pak by aproximační algoritmus s chybou <math> \rho\,\!</math> 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 <math> \varepsilon > 0\,\!</math>, a který pro libovolné <math> \varepsilon\,\!</math> pracuje jako aproximační algoritmus s relativní chybou <math> \varepsilon\,\!</math>. Doba běhu může být exponenciální jak vzhledem k <math> n\,\!</math> -- velikosti vstupní instance, tak vzhledem k <math> \frac{1}{\varepsilon}\,\!</math>.
Definice (Polynomiální aproximační schéma)
Polynomiální aproximační schéma je takové aproximační schéma, které pro každé pevné <math> \varepsilon> 0\,\!</math> běží v polynomiálním čase vzhledem k <math> n\,\!</math> (ale stále může být exponenciální vzhledem k <math> \frac{1}{\varepsilon}\,\!</math>.
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 <math> \frac{1}{\varepsilon}\,\!</math> (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 <math>n</math> hmotností predmetov <math>w_1, w_2, \ldots w_n</math>, obmedzenie <math>W</math> na celkovú hmotnosť a hodnoty predmetov <math>v_1, v_2, \ldots, v_n</math>.
Úlohou je nájsť takú množinu <math>S \subset \{1, 2, \ldots, n\}</math>, aby <math>\sum_{i \in S}w_i \leq W</math> a <math>\sum_{i \in S}v_i</math> bolo čo najväčšie.
Nech <math>V=\max\{v_1, v_2, \ldots, v_n\}</math>. Zadefinujme si <math>W(i,v)</math> ako najmenšia hmotnosť takej podmnožiny predmetov <math>\{w_1, \ldots w_i\}</math>, ktorých celková hodnota je práve <math>v</math>. Potom: :<math>W(i, v) = \begin{cases} 0&v=0\\ \infty & i=0, v>0 \\ W(i-1, v) & v_i > v \\ \min\{W(i-1, v), w_i + W(i-1, v-v_i) \} &\mbox{inak} \end{cases} </math>
V treťom prípade nepridáme vec <math>i</math>, lebo by sme prekročili cenu <math>v</math> (spomeňme si na definíciu <math>W(i,v)</math>), 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 <math>\max\{v | W(n,v) \leq W\}</math>. Tento algoritmus bude mať zložitosť <math>n^2 V</math>, č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 <math>\epsilon > 0</math>, tak orežeme <math>b= \lceil log \frac{\epsilon V}{n}\rceil</math> 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é <math>i</math> je hodnota predmetu <math>v'_i = 2^b \lfloor \frac{v_j}{2^b}\rfloor</math>. Náš algoritmus bude potrebovať čas <math>O(\frac{n^2V}{2^b})</math> (pretože ignorujeme nulové bity na konci každej hodnoty predmetu). Riešenie <math>S'</math>, ktoré dostaneme bude možno rôzne od optima <math>S</math> pôvodnej úlohy, ale bude platiť:
:<math>\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</math>
Prvá nerovnosť platí, lebo <math>S</math> je optimum v pôvodnej úlohe, druhá lebo <math>v'_i \leq v_i</math>, tretia lebo <math>S'</math> je optimum novej úlohy, štvrtá lebo <math>v'_i \geq v_i - 2^b</math> a posledná lebo <math>|S| \leq n</math>. Naše riešenie je teda najviac <math>n 2^b</math> pod optimom. Dolný odhad optima je <math>V</math> (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 <math>\frac{\mbox{approx} - \mbox{opt}}{\mbox{opt}} \leq \frac{\mbox{approx} - \mbox{opt}}{V} \leq \frac{n 2^b}{V} = \epsilon</math>
Takže pre zadané <math>\epsilon</math> orežeme <math>b = \lceil log \frac{\epsilon V}{n}\rceil</math> bitov a dostaneme algoritmus, ktorého relatívna chyba je <math>\epsilon</math> a jeho časová zložitosť je <math>O(\frac{n^2V}{2^b}) = O(\frac{n^3}{\epsilon})</math>, čo je polynomiálne aj v <math>n</math> aj v <math>\frac{1}{\epsilon}</math>, preto je to úplná polynomiálna aproximačná schéma.
{{Statnice I3}}