Közelítési algoritmus
A műveletek vizsgálatakor egy közelítési algoritmus egy algoritmus. az optimalizációs probléma megközelítő megoldásának megtalálására szolgál.
A közelítési algoritmus fogalmát 1972-ben formalizálták Garey, Graham és Ulman cikkében [1]. és később Johnson [2]. Közelítő algoritmusok gyakran társul NP-nehéz feladat, mert számukra alig van olyan hatékony algoritmust a pontos megoldást polinomiális időben, így van értelme, hogy megpróbálja megtalálni közel optimális megoldást. A heurisztikus algoritmusokkal ellentétben. ha elfogadható időn belül kielégítően jó megoldásokat adunk, a közelítő algoritmusok a megoldás bizonyítható minőségét biztosítják előre meghatározott időhatárokon belül. Ideális esetben a közelítés egy olyan megoldást eredményez, amely kis mértékű (például 5% -on belül) eltér az optimálistól. Közelítő algoritmusok egyre inkább használják a problémák megoldása érdekében az ismert egzakt algoritmus fut polinomiális időben, de dolgozott sokáig. Az approximációs algoritmus tipikus példája az algoritmus a csúcsfelületi probléma megoldására a grafikonelméletben. fedetlen élre talál, és mindkét csúcsait felemelje a felső fedélre, és addig folytatódik, amíg mindent el nem takar. Nyilvánvaló, hogy a kapott bevonat kétszer olyan jó, mint az optimális lefedettség. Egy ilyen megoldás egy közelítő algoritmus, amelynek állandó koefficiense 2.
Az NP-nehéz problémák nagyban különböznek a közelítés lehetőségétől. Néhány, köztük például a konténerek csomagolásának problémája. bármely 1-nél nagyobb együtthatóval közelíthető (ez a család az algoritmusok egy polinom idejének közelítő sémáját jelentik.) vagy a PTAS. Egyéb feladatok nem közelíthetők bármely konstans faktor, vagy akár egy polinom együttható (ha P ≠ NP), és ezek közül a problémákat a probléma a maximális klikk.
Az NP-bonyolult problémákat gyakran egész programozással fejezzük ki, és pontosan az exponenciális időben megoldódnak. Számos exponenciális algoritmus származik az egész értékű probléma lineáris programozásának csökkentéséből. [3]
Egy másik korlátozás azzal a ténnyel kapcsolatos, hogy a megközelítés csak az optimalizálási problémákra alkalmas, de nem a "tiszta" felismerési problémákra, mint a logikai képletek kielégíthetősége. bár gyakran előfordul, hogy a módszer igen alkalmas ugyanazon problémák optimalizálási verzióinak megoldására, például a Boole-képletek (Max SAT) maximális kielégíthetőségének problémájára.
Néhány közelítési algoritmus esetében a közelítés eredménye néhány tulajdonságának bizonyítása lehetséges. Például, ρ -approksimatsionny algoritmA - definíció szerint algoritmust, amely az aránya az f (x) = érték / költség megoldásokat a közelítés problémát A (x) A feladatra x nem nagyobb, mint (vagy kevesebb, a helyzettől függően) működik az együttható ρ az érték optimális értéke [4] [5]:
A ρ koefficiens a relatív garantált hatékonyságnak nevezhető.
A közelítési algoritmus abszolút garantált hatékonysággal vagy korlátozott hibával rendelkezik c. ha bármilyen x probléma esetén
A garantált hatékonyságot hasonló módon határozták meg. R (x, y), y megoldás az x-es probléma miatt
ahol f (y) az x-es probléma megoldásának y / y érték / költség összefüggése. Nyilvánvaló, hogy a garantált hatékonyság nem kevesebb, mint az egység, és csak abban az esetben van egyenlő, ha y az optimális megoldás. Ha az algoritmus A megoldás biztosítja a maximális hatékonyságot r (n), azt mondjuk, hogy A jelentése R (n) -approksimatsionnym algoritmus egy közelítés együtthatót és r (n) [6] [7].
Egyszerűen látható, hogy a minimalizálási probléma esetén a garantált hatékonyság mindkét definíciója egy értéket ad, míg a maximalizálási probléma r = ρ - 1>.
A relatív hiba fontos fogalma. az optimalizációs problémákhoz kapcsolódóan a szakirodalom különböző módon definiálja: például V. Cann [7] meghatározza azt | O P T - f (y) | / O P T -f (y) | / \ mathrm>. és Auziello és munkatársai [6] O P T - f (y) | / max
Itt x jelöli a problémát, és R A (x) az A x-re garantált hatékonysága.
Így P A _> a garantált hatékonyság felső határa minden lehetséges probléma esetén.Az R A ∞> aszimptotikus hatékonyságot hasonló módon definiáljuk:
Garantált hatékonyság: a határértékek alulról (felülről) a minimális (maximalizálási) feladatokhoz adott különböző értékekkel
Az algoritmusok fejlesztésére szolgáló technikák
Jelenleg számos megközelítés létezik egy közelítési algoritmus kidolgozásához. Közülük:
- Greedy algoritmus.
- Helyi keresés.
- Számlálás és dinamikus programozás.
- A domború programozás gyengített problémájának megoldása, azzal a lehetőséggel, hogy frakcionált megoldást kapjunk. Ezután az oldatot kerekítéssel megfelelő megoldássá alakítjuk át. A probléma enyhítésének népszerű módjai:
- Csökkentés a lineáris programozás problémájára.
- A semidefinit programozás problémájának csökkentése.
- Néhány egyszerű metrika problémájának meghatározása és a probléma megoldása ezzel a mutatóval.
A szakirodalomban, a közelítés együttható a probléma, hogy a maximális (vagy minimális) van írva, mint a C - ε (vagy c + ε) valamilyen számot C abban az esetben, ha eltérések vannak az algoritmus közelítési együttható C ∓ ε minden ε> 0. de nem ε = 0. Ilyen közelítés például a MAX-3SAT probléma 7/8 együtthatójának elérhetetlensége [8].
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldorsson, Marek Karpinsky és Gerhard Woeginger, A kompendium NP optimalizálási problémák.