Státnice - Aproximační algoritmy a schémata

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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:

  • $ C^{*}\,\! $ 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^{*}}{C},\frac{C}{C^{*}}\}\leq \rho(n)\,\! $

Definice (Relativní chyba)

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

$ \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: $ \varepsilon(n) = \frac{C-C^{*}}{C^{*}}=\frac{C}{C^{*}}-1=\rho(n)-1\,\! $
  • V případě minimalizační úlohy: $ \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 $ \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\,\! $" 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 $ \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\,\! $
  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)=2 w(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)\leq w(X)\,\! $. Celkem tedy dává $ w(H)\leq w(X)\leq 2w(H^{*})\,\! $, protože $ w(T)\leq w(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)\,\! $, pak zadání TSP zkonstruovat jako $ K_{|V|}(V,V\times V)\,\! $, kde $ 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 $ \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\,\! $ -- velikosti vstupní instance, tak vzhledem k $ \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é $ \varepsilon> 0\,\! $ běží v polynomiálním čase vzhledem k $ n\,\! $ (ale stále může být exponenciální vzhledem k $ \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 $ \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 $ n $ hmotností predmetov $ w_1, w_2, \ldots w_n $, obmedzenie $ W $ na celkovú hmotnosť a hodnoty predmetov $ v_1, v_2, \ldots, v_n $. Úlohou je nájsť takú množinu $ S \subset \{1, 2, \ldots, n\} $, aby $ \sum_{i \in S}w_i \leq W $ a $ \sum_{i \in S}v_i $ bolo čo najväčšie.

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

$ 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} $

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) \leq 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 $ \epsilon > 0 $, tak orežeme $ 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é $ i $ je hodnota predmetu $ v'_i = 2^b \lfloor \frac{v_j}{2^b}\rfloor $. Náš algoritmus bude potrebovať čas $ O(\frac{n^2V}{2^b}) $ (pretože ignorujeme nulové bity na konci každej hodnoty predmetu). Riešenie $ S' $, ktoré dostaneme bude možno rôzne od optima $ S $ pôvodnej úlohy, ale bude platiť:

$ \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 $ S $ je optimum v pôvodnej úlohe, druhá lebo $ v'_i \leq v_i $, tretia lebo $ S' $ je optimum novej úlohy, štvrtá lebo $ v'_i \geq v_i - 2^b $ a posledná lebo $ |S| \leq 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 $ \frac{\mbox{approx} - \mbox{opt}}{\mbox{opt}} \leq \frac{\mbox{approx} - \mbox{opt}}{V} \leq \frac{n 2^b}{V} = \epsilon $

Takže pre zadané $ \epsilon $ orežeme $ 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(\frac{n^2V}{2^b}) = O(\frac{n^3}{\epsilon}) $, čo je polynomiálne aj v $ n $ aj v $ \frac{1}{\epsilon} $, preto je to úplná polynomiálna aproximačná schéma.


Citováno z „http://wiki.matfyz.cz/index.php?title=Státnice_-_Aproximační_algoritmy_a_schémata&oldid=19912“