Közelítő algoritmus

A közelítő algoritmus egy olyan műveleti kutatási algoritmus , amelyet egy optimalizálási probléma közelítő megoldásának megtalálására használnak .

A közelítő algoritmus fogalmát 1972-ben formalizálták Garey, Graham és Ullman [1] , majd később Johnson [2] cikkében . A közelítő algoritmusokat gyakran NP-nehéz problémákkal társítják , mivel ezekre aligha létezik hatékony polinomiális idő pontos megoldási algoritmus, ezért célszerű az optimálishoz közeli megoldást keresni. Ellentétben a heurisztikus algoritmusokkal , amelyek elfogadható időn belül kellően jó megoldásokat adnak, a közelítő algoritmusok előre meghatározott időhatárokon belül biztosítják a megoldás bizonyítható minőségét. Ideális esetben a közelítés olyan megoldást ad, amely valamilyen kis tényezővel (például 5%-on belül) eltér az optimálistól. Egyre gyakrabban alkalmaznak közelítő algoritmusokat olyan problémák megoldására, amelyekre pontos algoritmusok ismertek, amelyek polinomiális időben futnak, de hosszú ideig futnak. A közelítő algoritmus tipikus példája a gráfelméletben a csúcsfedési probléma megoldására szolgáló algoritmus : keressünk egy fedetlen élt, és adjuk hozzá mindkét csúcsát a csúcsfedéshez, és így tovább, amíg az összeset le nem fedi. Nyilvánvaló, hogy a kapott lefedettség kétszer akkora lehet, mint az optimális. Ez a megoldás egy közelítő algoritmus , amelynek állandó együtthatója 2.

Az NP-nehéz problémák közelíthetősége nagyon eltérő. Némelyik, például a szemetes-csomagolási probléma , bármely 1-nél nagyobb tényezővel közelíthető (ezt az algoritmuscsaládot Approximate Polynomial Time Scheme -nek vagy PTAS -nak nevezik ). Más problémák nem közelíthetők semmilyen konstans együtthatóval, de még polinomiális együtthatóval sem (ha P ≠ NP ), ilyenek közé tartozik a maximális klikk probléma .

Az NP-nehéz problémák gyakran egészszámú programozással fejezhetők ki, és pontosan exponenciális idő alatt oldhatók meg . Sok exponenciális algoritmus egy egész szám probléma lineáris programozási problémává való redukálásából származik . [3]

Nem minden közelítő algoritmus alkalmas gyakorlati problémák megoldására. Gyakran CPU / LP / félig definiált feladatokat , összetett adatstruktúrákat vagy kifinomult programozási technikákat használnak részfeladatként , ami a megvalósítás bonyolultságához vezet. Egyes közelítő algoritmusoknak elfogadhatatlan futási ideje van annak ellenére, hogy az idő polinomiális (pl. O( n 2000 )). Ennek ellenére még az ilyen irreális algoritmusok tanulmányozása sem pusztán elméleti célokat követ, hiszen lehetővé teszi a probléma lényegének megértését. Klasszikus példa erre a Sanjiv Arora tulajdonában lévő metrikus utazó értékesítő problémára kidolgozott kezdeti PTAS algoritmus , amely szinte irreális futási idővel bírt. Azonban egy éven belül Arora finomította az ötletet egy lineáris időben futó algoritmussá. Az ilyen algoritmusok olyan feladatokra is alkalmasak, ahol a futási idő és költség igazolható. Ezek a feladatok közé tartozik a számítási biológia , a pénzügyi tervezés , a közlekedéstervezés és a készletkezelés .

Egy másik korlát, hogy a megközelítés csak optimalizálási problémákra alkalmas, de nem "tiszta" felismerési problémákra , mint például a Boole-képletek kielégíthetőségének problémája , bár gyakran előfordul, hogy a módszer teljesen alkalmazható ugyanazon problémák optimalizálási változatainak megoldására, pl. például a maximális kielégítési probléma logikai képleteihez (Max SAT).

A közelítés lehetetlensége azóta is gyümölcsöző kutatási terület a számítási komplexitás területén, amióta Feige, Goldwasser, Lovasz, Safra és Szegedy 1990-ben megállapították, hogy a maximális független halmaz megtalálásának problémája nem közelíthető . Egy évvel azután, hogy Arora bebizonyította a PCP-tételt , Johnson 1974-es közelítési algoritmusai a Boole -féle kielégíthetőségi problémára , a halmazfedő-problémára , a független halmazproblémára és a gráf kromatikus számproblémára rendelkeznek egy optimális közelítési tényezővel (P ≠ NP-t feltételezve)

Garantált hatékonyság

Egyes közelítési algoritmusoknál lehetőség van a közelítési eredmény bizonyos tulajdonságainak bizonyítására. Például egy ρ -közelítő algoritmus A definíció szerint egy olyan algoritmus, amelynél az x feladat A ( x ) közelítési feladatának megoldásához szükséges f ( x ) = érték/költség arány nem haladja meg ( vagy nem kevesebb , attól függően, hogy a helyzet) a ρ együttható szorzata az optimális értékhez [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}}

A ρ együtthatót relatív garantált hatásfoknak nevezzük .

Egy közelítő algoritmus abszolút garantált hatékonysággal vagy korlátos c hibával rendelkezik, ha bármely x problémára ,

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

Az x feladat y megoldásának garantált hatékonysága , R ( x, y ) hasonló módon definiálva

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

ahol f ( y ) az x feladat y megoldásának érték/költség aránya . Nyilvánvaló, hogy a garantált hatásfok nem kisebb egynél, és csak abban az esetben egyenlő eggyel, ha y az optimális megoldás. Ha az A algoritmus maximális r ( n ) hatásfokú megoldást garantál, akkor A -t r ( n )-közelítési algoritmusnak mondjuk, és r ( n ) közelítési tényezője van [6] [7] .

Könnyen belátható, hogy a minimalizálási probléma esetén a garantált hatékonyság mindkét definíciója azonos értéket ad, míg a maximalizálási probléma esetében . ${\displaystyle r=\rho ^{-1))$

Az optimalizálási problémákhoz kapcsolódó relatív hiba fontos fogalmát a szakirodalom többféleképpen definiálja: például W. Kann [7] -ként , Ausiello és munkatársai [6] -ként definiálja . $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ ${\displaystyle |\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\))$

Valamelyik A közelítési algoritmus abszolút garantált hatékonyságát a következőképpen határozzuk meg $\mathrm {P} _{A}$

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

Itt x egy feladatot jelöl, a pedig A garantált hatékonyságát x esetén . $R_{A}(x)$

Így minden lehetséges probléma esetén a garantált hatékonyság r felső korlátja. $\mathrm {P} _{A}$

Az aszimptotikus hatékonyságot hasonló módon határozzuk meg : ${\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\}.

Garantált hatékonyság: A minimalizálási (maximalizálási) problémák alsó (felső) határai eltérő értékek mellett

	r -kb. [6] [7]	ρ -kb.	kapcsolódik. hiba c [7]	kapcsolódik. c hiba [6]	normák. kapcsolat hiba c [6] [7]	abs. hiba 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 {LOSSZABB}$	$\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 {LOSSZABB}$	$\mathrm {OPT} +c$

Algoritmusfejlesztési technikák

Jelenleg számos szabványos megközelítés létezik egy közelítő algoritmus fejlesztésére. Közöttük:

Mohó algoritmus .
Helyi keresés .
Felsorolás és dinamikus programozás .
Gyengített konvex programozási feladat megoldása törtmegoldás megszerzésének lehetőségével. Ezután az oldatot kerekítéssel megfelelő oldattá alakítjuk. A népszerű problémacsökkentő módszerek a következők:
1. Redukció lineáris programozási problémává .
2. A félig meghatározott programozás problémájának redukálása .
Egy probléma egyszerű mérőszámának meghatározása és a probléma megoldása ezzel a mérőszámmal.

Epsilon tag

A szakirodalomban a maximális (vagy minimális) feladat közelítési együtthatója (vagy )-ként van írva valamilyen számra abban az esetben, ha az algoritmusnak vannak olyan változatai, amelyeknek közelítési együtthatója van bármelyikre, de nem -re . Egy ilyen közelítésre példa a 7/8-as együttható elérhetetlensége a MAX-3SAT probléma esetében [8] . $c-\epsilon$ $c+\epsilon$ $c$ $c\mp \epsilon$ $\epsilon >0$ $\epsilon =0$

Jegyzetek

↑ MRGarey, RL Graham és JD Ullman. A memóriafoglalási algoritmusok legrosszabb eset elemzése. In Proc. A 4. ACM Symp. A számítástechnika elméletéről. 143-152, 1972.
↑ D.S. Johnson. Approximációs algoritmusok kombinatorikus feladatokhoz. J Számítógép. System Sci. 9, 256-278, 1974.
↑ Gomory, Ralph E. (1958), "A lineáris programok egészszámú megoldásainak algoritmusa", Bulletin of the American Mathematical Society 64 (5): 275-279, doi: 10.1090/S0002-9904-1958-10224 négy.
↑ Dorit S. Hochbaum, szerkesztő, Approximation Algorithms for NP-Hard Problems, XV. oldal. PWS Publishing Company
↑ Tjark Vredeveld, Kísérleti kombinatorikus közelítő algoritmusok: Garantált versus teljesítmény, 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 és M. Protasi. Komplexitás és közelítés: Kombinatorikus optimalizálási problémák és közelíthetőségi tulajdonságaik . – 1999.
↑ 1 2 3 4 5 6 Viggo Kann. Az NP-teljes optimalizálási problémák közelíthetőségéről . – 1992.
↑ Johan Hastad. Néhány optimális megközelíthetetlenségi eredmény // Journal of the ACM : Journal. – 1999.

Irodalom

Vazirani, Vijay V.Közelítőalgoritmusok . - Berlin: Springer, 2003. - ISBN 3-540-65367-8 .
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest és Clifford Stein. Bevezetés az algoritmusokba , második kiadás. MIT Press és McGraw-Hill, 2001. ISBN 0-262-03293-7 . 35. fejezet: Közelítő algoritmusok, pp. 1022-1056.
Dorit H. Hochbaum, szerk. Approximation Algorithms for NP-Hard problémák, PWS Publishing Company, 1997. ISBN 0-534-94968-1 . 9. fejezet: Különféle közelítési fogalmak: jó, jobb, legjobb és több
Williamson, David és Shmoys, David (2011. április 26.), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

Linkek

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski és Gerhard Woeginger, A kompendium az NP optimalizálási problémákról

Bibliográfiai katalógusokban	BNF : 16603384f GND : 4500954-5 J9U : 987007475469205171 LCCN : sh2009010988