''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] ze [[Státnice_-_Informatika_-_Složitost_(obory_Matematická_lingvistika_a_Softwarové_systémy)|složitosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze zápisků z předmětu [[Složitost I]] -- [[User:Tuetschek|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> (slajdy: chyba) 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 \\ n\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\geq 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 <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\geq 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).
{{TODO|APPROX-SP}}
