Aproximační algoritmus

Aproximační algoritmus je algoritmus v operačním výzkumu , který se používá k nalezení přibližného řešení optimalizačního problému .

Koncept aproximačního algoritmu byl formalizován v roce 1972 v práci Gareyho, Grahama a Ullmana [1] a později Johnsona [2] . Aproximační algoritmy jsou často spojovány s NP-těžkými problémy, protože pro ně stěží existuje účinný polynomiální časově přesný algoritmus řešení, takže má smysl snažit se najít řešení, které se blíží optimálnímu. Na rozdíl od heuristických algoritmů , které poskytují dostatečně dobrá řešení v přijatelném čase, poskytují aproximační algoritmy prokazatelnou kvalitu řešení v předem stanovených časových limitech. V ideálním případě poskytuje aproximace řešení, které se od optimálního liší o nějaký malý faktor (například v rozmezí 5 %). Aproximační algoritmy se stále častěji používají k řešení problémů, pro které jsou známy přesné algoritmy, které běží v polynomiálním čase, ale běží po dlouhou dobu. Typickým příkladem aproximačního algoritmu je algoritmus pro řešení problému pokrytí vrcholů v teorii grafů : najděte nepokrytou hranu a přidejte oba její vrcholy k pokrytí vrcholu a tak dále, dokud nejsou pokryty všechny. Je jasné, že výsledné krytí může být dvakrát větší než to optimální. Toto řešení je aproximační algoritmus s konstantním koeficientem 2.

NP-těžké problémy se velmi liší svou aproximovatelností. Některé, jako je problém s balením přihrádek , lze aproximovat jakýmkoli faktorem větším než 1 (tato rodina algoritmů se nazývá Přibližné polynomické časové schéma nebo PTAS ). Jiné problémy nelze aproximovat žádným konstantním koeficientem, dokonce ani polynomiálním koeficientem (pokud P ≠ NP ), a mezi takové problémy patří problém maximální kliky .

NP-těžké problémy lze často vyjádřit pomocí celočíselného programování a vyřešit je přesně v exponenciálním čase . Mnoho exponenciálních algoritmů pochází z redukce celočíselného problému na problém lineárního programování . [3]

Ne všechny aproximační algoritmy jsou vhodné pro řešení praktických problémů. Často používají CPU / LP / semi-definované úlohy , složité datové struktury nebo sofistikované programovací techniky jako dílčí úlohy, což vede ke složitosti implementace. Některé aproximační algoritmy mají nepřijatelné doby běhu, i když je čas polynomiální (např. O( n 2000 )). Studium ani takových nereálných algoritmů však nesleduje čistě teoretické cíle, protože umožňuje pochopit podstatu problému. Klasickým příkladem je počáteční algoritmus PTAS pro metrický problém obchodního cestujícího , který vlastní Sanjiv Arora , který měl téměř nereálnou dobu běhu. Během jednoho roku však Arora zdokonalila myšlenku na algoritmus, který běžel v lineárním čase. Takové algoritmy jsou také vhodné pro úlohy, kde lze odůvodnit provozní dobu a náklady. Tyto úkoly zahrnují výpočetní biologii , finanční inženýrství , plánování dopravy a řízení zásob .

Dalším omezením je, že přístup je vhodný pouze pro optimalizační problémy, ale ne pro "čisté" rozpoznávací problémy , jako je problém splnitelnosti booleovských vzorců , i když se často stává, že metoda je docela použitelná pro řešení optimalizačních verzí stejných problémů, např. například pro problém maximální splnitelnosti booleovské vzorce (Max SAT).

Nemožnost aproximace je plodnou oblastí výzkumu v oblasti výpočetní složitosti od doby, kdy Feige, Goldwasser, Lovasz, Safra a Szegedy v roce 1990 stanovili, že problém nalezení maximální nezávislé množiny nelze aproximovat . Rok poté, co Arora dokázal PCP teorém , Johnsonovy aproximační algoritmy z roku 1974 pro Booleovský problém uspokojitelnosti , Problém množinového pokrytí , Problém nezávislých množin a Problém chromatických čísel grafů mají optimální aproximační faktor (za předpokladu P ≠ NP)

Zaručená účinnost

U některých aproximačních algoritmů je možné prokázat některé vlastnosti výsledku aproximace. Například ρ -aproximační algoritmus A je podle definice algoritmem, pro který poměr f ( x ) = hodnota/náklady na řešení aproximačního problému A ( x ) pro problém x nepřesahuje (nebo není menší, v závislosti na situace) součin koeficientu ρ na optimální hodnotu [4] [5] :

{\begin{cases}\mathrm {OPT} \leqslant f(x)\leqslant \rho \mathrm {OPT} ,\rho >1;\\\rho \mathrm {OPT} \leqslant f(x) \leqslant \mathrm {OPT} ,\rho <1.\end{cases}}

Koeficient ρ se nazývá relativní zaručená účinnost .

Aproximační algoritmus má absolutní zaručenou účinnost nebo omezenou chybu c , pokud pro jakýkoli problém x ,

(\mathrm {OPT} -c)\leqslant f(x)\leqslant (\mathrm {OPT} +c).

Zaručená účinnost , R ( x, y ) řešení y pro úlohu x je definována podobným způsobem

R(x,y)=\max \left({\frac {\mathrm {OPT} }{f(y)))),{\frac {f(y)}{\mathrm {OPT} } } \vpravo),

kde f ( y ) je poměr hodnota/náklady pro řešení y problému x . Je jasné, že garantovaná účinnost není menší než jedna a rovná se jedné pouze v případě, kdy y je optimální řešení. Pokud algoritmus A zaručuje řešení s maximální účinností r ( n ), pak A je považován za r ( n )-aproximační algoritmus a má aproximační faktor r ( n ) [6] [7] .

Je snadné vidět, že v případě problému minimalizace dávají obě definice garantované účinnosti stejnou hodnotu, zatímco pro problém maximalizace . ${\displaystyle r=\rho ^{-1))$

Důležitý pojem relativní chyby spojený s optimalizačními problémy je v literatuře definován různými způsoby: například W. Kann [7] jej definuje jako , Ausiello et al., [6] jako . $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ ${\displaystyle |\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\))$

Absolutní zaručená účinnost některého aproximačního algoritmu A je definována jako $\mathrm {P} _{A}$

\mathrm {P} _{A}=\inf\{r\geqslant 1\mid R_{A}(x)\leqslant r,\forall x\}.

Zde x označuje úlohu a a je zaručená účinnost A pro x . $R_{A}(x)$

Je tedy horní mez garantované účinnosti r pro všechny možné problémy. $\mathrm {P} _{A}$

Asymptotická účinnost je definována podobným způsobem : ${\displaystyle R_{A}^{\infty ))$

R_{A}^{\infty }=\inf\{r\geqslant 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leqslant r,\ forall x,|x|\geqslant n\}.

Zaručená účinnost: Dolní (horní) hranice pro problémy s minimalizací (maximalizací) při různých hodnotách

	r -cca. [6] [7]	ρ -cca.	se týká. chyba c [7]	se týká. chyba c [6]	normy. vztah chyba c [6] [7]	břišní svaly. chyba c [6] [7]
max: $f(x)\geqslant$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {HORST}$	$\mathrm {OPT} -c$
min: $f(x)\leqslant$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {HORST}$	$\mathrm {OPT} +c$

Techniky vývoje algoritmů

V současné době existuje několik standardních přístupů k vývoji aproximačního algoritmu. Mezi nimi:

Chamtivý algoritmus .
Místní vyhledávání .
Enumerace a dynamické programování .
Řešení oslabeného konvexního programovacího problému s možností získání zlomkového řešení. Roztok se pak zaokrouhlováním převede na vhodný roztok. Populární metody zmírnění problémů jsou:
1. Redukce na problém lineárního programování .
2. Redukce na problém semidefinitního programování .
Definování nějaké jednoduché metriky pro problém a řešení problému s touto metrikou.

Člen Epsilon

V literatuře se aproximační koeficient pro maximální (nebo minimální) problém zapisuje jako (nebo ) pro nějaké číslo v případě, že existují varianty algoritmu s aproximačním koeficientem pro libovolné ale ne pro . Příkladem takové aproximace je nedosažitelnost koeficientu 7/8 pro problém MAX-3SAT [8] . $c-\epsilon$ $c+\epsilon$ $C$ $c\mp \epsilon$ $\epsilon >0$ $\epsilon =0$

Poznámky

↑ MRGarey, RL Graham a JD Ullman. Analýza nejhoršího případu algoritmů alokace paměti. V Proc. 4. ACM Symp. O teorii výpočetní techniky. 143-152, 1972.
↑ D.S. Johnson. Aproximační algoritmy pro kombinatorické úlohy. J Výpočet. System Sci., 9, 256-278, 1974.
↑ Gomory, Ralph E. (1958), "Náčrt algoritmu pro celočíselná řešení lineárních programů", Bulletin of the American Mathematical Society 64 (5): 275-279, doi: 10.1090/S0002-9904-1958-1022 čtyři.
↑ Dorit S. Hochbaum, editor, Aproximační algoritmy pro NP-Hard Problems, strana XV. Vydavatelská společnost PWS
↑ Tjark Vredeveld, Experimentální kombinatorické aproximační algoritmy: Zaručená versus výkon, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
↑ 1 2 3 4 5 6 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela a M. Protasi. Složitost a aproximace: Problémy kombinatorické optimalizace a jejich vlastnosti aproximovatelnosti . — 1999.
↑ 1 2 3 4 5 6 Viggo Kann. O aproximovatelnosti NP-úplných optimalizačních problémů . — 1992.
↑ Johan Hastad. Některé výsledky optimální nepřiblížení // Journal of the ACM : journal. — 1999.

Literatura

Vazirani, Vijay V.Aproximačníalgoritmy . - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein. Úvod do algoritmů , druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN 0-262-03293-7 . Kapitola 35: Aproximační algoritmy, str. 1022-1056.
Dorit H. Hochbaum, ed. Aproximační algoritmy pro NP-Hard problémy, PWS Publishing Company, 1997. ISBN 0-534-94968-1 . Kapitola 9: Různé představy o aproximacích: dobré, lepší, nejlepší a další
Williamson, David & Shmoys, David (26. dubna 2011), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

Odkazy

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski a Gerhard Woeginger, Přehled problémů optimalizace NP

V bibliografických katalozích	BNF : 16603384f GND : 4500954-5 J9U : 987007475469205171 LCCN : sh2009010988