Közelítési algoritmus - Approximation algorithm

A számítástechnika és az operációkutatás , approximációs algoritmusok vannak hatékony algoritmusok , hogy megtalálják közelítő megoldást optimalizálási problémák (különösen NP-nehéz problémák) a kimutatható garanciákat a távolság a visszaküldött megoldást az optimális. A közelítő algoritmusok természetesen felmerülnek az elméleti informatika területén a széles körben elterjedt P ≠ NP sejtés következtében. E feltételezés szerint az optimalizálási feladatok széles osztálya nem oldható meg pontosan polinomidőben . A közelítő algoritmusok mezője ezért megpróbálja megérteni, hogy milyen közelről lehetséges közelíteni az ilyen problémák optimális megoldásait polinomiális időben. Az esetek túlnyomó többségében az ilyen algoritmusok garanciája egy multiplikatív, közelítési arányban vagy közelítő tényezőben kifejezve, azaz az optimális megoldás mindig garantáltan a visszaadott megoldás (előre meghatározott) szorzó tényezőjén belül van. Ugyanakkor számos közelítő algoritmus is létezik, amelyek adalék -garanciát nyújtanak a visszaadott megoldás minőségére. A közelítő algoritmus figyelemre méltó példája, amely mindkettőt biztosítja, a Lenstra , a Shmoys és a Tardos klasszikus közelítő algoritmusa a nem kapcsolódó párhuzamos gépeken történő ütemezéshez .

A közelítő algoritmusok tervezése és elemzése döntően magában foglal egy matematikai bizonyítást, amely a legrosszabb esetben igazolja a visszaadott megoldások minőségét. Ez megkülönbözteti őket az olyan heurisztikáktól , mint a lágyítás vagy a genetikai algoritmusok , amelyek ésszerűen jó megoldásokat találnak néhány bemenetre, de az elején nem adnak egyértelmű jelzést arról, hogy mikor lehet sikeres vagy sikertelen.

Nagy az érdeklődés az elméleti informatika iránt, hogy jobban megértsük azokat a határokat, amelyekhez közelíthetünk bizonyos híres optimalizálási problémákat. Például a számítástechnika egyik régóta nyitott kérdése annak meghatározása, hogy létezik-e olyan algoritmus, amely felülmúlja a Christofides 1,5 közelítő algoritmusát a metrikus utazó értékesítési problémánál . A vágyat, hogy a közelítő szemszögből megértsük a kemény optimalizálási problémákat, meglepő matematikai összefüggések felfedezése és széles körben alkalmazható technikák motiválják a kemény optimalizálási problémák algoritmusainak megtervezésére. Egy jól ismert példája az előbbi a Goemans-Williamson algoritmus a maximális vágás , ami megoldja a gráfelméleti problémát a magas dimenziós geometria.

Bevezetés

Egy közelítő algoritmus egyszerű példája a minimális csúcsfedési probléma, ahol a cél a legkisebb csúcshalmaz kiválasztása úgy, hogy a bemeneti gráf minden élete legalább egy kiválasztott csúcsot tartalmazzon. A csúcsborítás megkeresésének egyik módja a következő eljárás megismétlése: keressen egy fedetlen élt, adja hozzá mindkét végpontját a fedélhez, és távolítsa el a grafikonból az egyik csúcsra eső élt. Mivel a bemeneti gráf bármely csúcsborításának külön csúcsot kell használnia a folyamat során figyelembe vett minden él lefedésére (mivel illeszkedést képez ), ezért az előállított csúcsborítás legfeljebb kétszer akkora, mint az optimális. Más szóval, ez egy állandó tényező közelítő algoritmus , amelynek közelítési tényezője 2. A legutóbbi egyedi játékok feltételezése szerint ez a tényező a lehető legjobb is.

Az NP-kemény problémák megközelíthetősége nagyban különbözik; néhányat, például a hátizsák problémát , szorzótényezőn belül közelíthetünk , bármilyen fixhez , és ezért tetszőlegesen az optimálishoz közelítő megoldásokat állítunk elő (az ilyen közelítő algoritmuscsaládot polinomiális idő -közelítési sémának vagy PTAS -nak hívják). Másokat lehetetlen közelíteni bármely állandó, vagy akár polinom tényezőben, hacsak P = NP , mint a maximális klikk probléma esetén . Ezért a közelítő algoritmusok tanulmányozásának fontos előnye a különböző NP-nehéz feladatok nehézségeinek finom osztályozása, túl azon, amit az NP-teljesség elmélete kínál . Más szóval, bár az NP-teljes feladatok a pontos megoldások szempontjából egyenértékűek lehetnek (polinomiális időcsökkentések esetén), a megfelelő optimalizálási problémák a hozzávetőleges megoldások szempontjából nagyon eltérően viselkednek. ${\ displaystyle 1+ \ epsilon}$${\ displaystyle \ epsilon> 0}$

Algoritmus tervezési technikák

Mostanra már számos bevált technika létezik a közelítő algoritmusok tervezésére. Ezek közé tartoznak a következők.

1. Mohó algoritmus
2. Helyi keresés
3. Felsorolás és dinamikus programozás
4. Megoldása a konvex programozás relaxációs, hogy egy tört megoldást. Ezután ezt a töredékes oldatot megfelelő kerekítéssel megvalósítható oldattá alakítjuk. A népszerű kikapcsolódások a következők.
   • Lineáris programozási relaxációk
   • Félig végleges programozási relaxációk
5. Primal-dual módszerek
6. Kettős illesztés
7. A probléma beágyazása valamilyen mutatóba, majd a probléma megoldása a metrikában. Ezt metrikus beágyazásnak is nevezik.
8. Véletlen mintavétel és általában a véletlenszerűség alkalmazása a fenti módszerekkel együtt.

Utólagos garancia

Míg a közelítő algoritmusok mindig eleve a legrosszabb esetek garanciáját nyújtják (legyen az additív vagy multiplikatív), bizonyos esetekben utólagos garanciát is adnak, amely gyakran sokkal jobb. Ez gyakran előfordul olyan algoritmusok esetében, amelyek úgy működnek, hogy az adott bemeneten az optimalizálási probléma konvex relaxációját oldják meg . Például létezik egy másik közelítési algoritmus a minimális csúcsborításhoz, amely egy lineáris programozási relaxációt megold , hogy olyan csúcsborítást találjon, amely legfeljebb kétszerese a relaxáció értékének. Mivel a relaxáció értéke soha nem nagyobb, mint az optimális csúcsborítás mérete, ez újabb 2-közelítő algoritmust eredményez. Bár ez hasonló az előző közelítő algoritmus a priori garanciájához, az utóbbi garanciája sokkal jobb lehet (sőt, ha az LP relaxáció értéke messze nem az optimális csúcsborítás mérete).

Közelítés keménysége

A közelítési algoritmusok, mint kutatási terület szorosan kapcsolódnak a közeledési elmélethez , és tájékoztatnak arról, hogy bizonyos közelítési arányokkal rendelkező hatékony algoritmusok nem létezése bizonyított (a széles körben elterjedt hipotézisek, például a P ≠ NP sejtés függvényében) redukciókkal . A metrikus utazó értékesítő probléma esetén a legismertebb megközelíthetetlenségi eredmény kizárja az algoritmusokat, amelyek közelítési aránya kisebb, mint 123/122 ≈ 1,008196, kivéve, ha P = NP, Karpinski, Lampis, Schmied. A Christofides 1,5 -ös közelítési algoritmusának ismeretével párosítva ez azt mutatja, hogy a metrikus utazó értékesítők közelítési küszöbértéke (ha létezik) 123/122 és 1,5 között van.

Míg az 1970 -es évek óta bebizonyították a megközelíthetetlenségi eredményeket, ezeket az eredményeket ad hoc eszközökkel szerezték be, és akkoriban nem állt rendelkezésre szisztematikus megértés. Feige, Goldwasser, Lovász, Safra és Szegedy 1990 -es eredménye óta, amely az Independent Set megközelíthetetlenségéről és a híres PCP -tételről szól, csak akkor fedezték fel a korszerű eszközöket a megközelíthetetlenség bizonyítására. A PCP -tétel például azt mutatja, hogy Johnson 1974 -es közelítési algoritmusai a Max SAT , a fedőlap , a független halmaz és a színezés mind elérik az optimális közelítési arányt, feltéve, hogy P ≠ NP.

Praktikusság

Nem minden közelítő algoritmus alkalmas közvetlen gyakorlati alkalmazásokra. Néhány esetben nem triviális lineáris programozás / félig végleges relaxációk (amelyek maguk is az ellipszoid algoritmust idézhetik elő ) megoldása, bonyolult adatstruktúrák vagy kifinomult algoritmikus technikák jelentik , amelyek csak kivitelezhetetlenül nagy bemenetek esetén okoznak nehéz megvalósítási problémákat vagy javítják a futási időt (pontos algoritmusokon felül). . A megvalósítással és a futási idővel kapcsolatos kérdéseket félretéve, a közelítő algoritmusok által nyújtott garanciák önmagukban nem lehetnek elég erősek ahhoz, hogy igazolják a gyakorlatban való figyelembevételüket. Annak ellenére, hogy képtelenek "a dobozon kívül" használni a gyakorlati alkalmazásokban, az ilyen algoritmusok tervezése mögött rejlő ötletek és felismerések gyakran más módon is beépíthetők a gyakorlati algoritmusokba. Ily módon még a nagyon drága algoritmusok tanulmányozása sem teljesen elméleti tevékenység, mivel értékes felismerésekre tehetnek szert.

Más esetekben, még akkor is, ha a kezdeti eredmények pusztán elméleti érdeklődésre tartanak számot, idővel, jobb megértéssel az algoritmusokat finomítani lehet, hogy praktikusabbak legyenek. Az egyik ilyen példa a kezdeti preferenciális kereskedelmi számára euklideszi TSP által Sanjeev Arora (és egymástól függetlenül a Joseph Mitchell ), amelyek egy tiltó futási ideje egy közelítés. Mégis, egy éven belül ezeket az ötleteket beépítették egy szinte lineáris időalgoritmusba minden konstansra . ${\ displaystyle n^{O (1/\ epsilon)}}$${\ displaystyle 1+ \ epsilon}$${\ displaystyle O (n \ log n)}$${\ displaystyle \ epsilon> 0}$

Teljesítménygaranciák

Néhány közelítő algoritmus esetében lehetséges bizonyos tulajdonságok bizonyítása az optimális eredmény közelítésével kapcsolatban. Például egy ρ -approximation algoritmus Egy úgy definiáljuk, hogy egy algoritmust, amely bebizonyosodott, hogy az érték / költség, f ( x ), a közelítő megoldást A ( X ) egy példány x nem lesz több, (vagy kevesebb, a helyzettől függően), mint egy ρ tényező az optimális megoldás értéke, OPT.

${\ displaystyle {\ begin {case} \ mathrm {OPT} \ leq f (x) \ leq \ rho \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho> 1; \\\ rho \ mathrm {OPT} \ leq f (x) \ leq \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho <1. \ end {tokok}}}$

A ρ tényezőt relatív teljesítménygaranciának nevezik . Közelítő algoritmus egy abszolút teljesítési biztosíték vagy korlátos hiba c , ha bebizonyosodott, hogy minden esetben x , hogy

${\ displaystyle (\ mathrm {OPT} -c) \ leq f (x) \ leq (\ mathrm {OPT} +c).}$

Hasonlóképpen, a teljesítési garancia , R ( x, y ), egy oldat y egy példány X jelentése a

${\ displaystyle R (x, y) = \ max \ left ({\ frac {OPT} {f (y)}}, {\ frac {f (y)} {OPT}} \ right),}$

ahol f ( y ) az y megoldás értéke/költsége az x példányra . Nyilvánvaló, hogy a teljesítménygarancia nagyobb és egyenlő 1 -gyel, és csak akkor egyenlő 1 -vel, ha és csak akkor, ha az y optimális megoldás. Ha egy algoritmus A garanciákat, hogy visszatérjen megoldások teljesítési garanciát legfeljebb r ( n ), akkor A azt mondják, hogy egy R ( n ) -approximation algoritmus és egy közelítése aránya a r ( n ). Hasonlóképpen, egy r ( n ) -közelítési algoritmus problémája r ( n ) - közelíthető, vagy közelítő aránya r ( n ).

Minimalizálási problémák esetén a két különböző garancia ugyanazt az eredményt adja, és maximalizálási problémák esetén a ρ relatív teljesítménygarancia egyenértékű a teljesítési garanciával . A szakirodalomban mindkét definíció gyakori, de egyértelmű, hogy melyik definíciót használják, mivel a maximalizálási problémák esetén ρ ≤ 1, míg r ≥ 1. ${\ displaystyle r = \ rho ^{-1}}$

A abszolút teljesítési biztosíték néhány közelítés algoritmus A , ahol X jelentése egy példány az a probléma, és hol van a teljesítési biztosíték A a x (azaz ρ a probléma például x ) jelentése: ${\ displaystyle \ mathrm {P} _ {A}}$${\ displaystyle R_ {A} (x)}$

${\ displaystyle \ mathrm {P} _ {A} = \ inf \ {r \ geq 1 \ mid R_ {A} (x) \ leq r, \ forall x \}.}$

Ez azt jelenti, hogy ez a legnagyobb korlát a közelítési arányban, r , amelyet a probléma minden lehetséges példája átlát. Hasonlóképpen, az aszimptotikus teljesítményarány : ${\ displaystyle \ mathrm {P} _ {A}}$ ${\ displaystyle R_ {A}^{\ infty}}$

${\ displaystyle R_ {A} ^{\ infty} = \ inf \ {r \ geq 1 \ mid \ létezik n \ in \ mathbb {Z} ^{+}, R_ {A} (x) \ leq r, \ minden x, | x | \ geq n \}.}$

Ez azt jelenti, hogy ez ugyanaz, mint a abszolút teljesítmény aránya , egy alsó határ n a mérete probléma példányok. Ezt a kétféle arányt azért használják, mert léteznek olyan algoritmusok, ahol a kettő közötti különbség jelentős.

Teljesítménygaranciák

	r -kb	ρ -kb	rel. hiba	rel. hiba	norma. rel. hiba	hasizom hiba
max: ${\ displaystyle f (x) \ geq}$	${\ displaystyle r^{-1} \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} -c}$
min: ${\ displaystyle f (x) \ leq}$	${\ displaystyle r \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1+c) \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT}}$	${\ displaystyle (1-c)^{-1} \ mathrm {OPT} +c \ mathrm {WORST}}$	${\ displaystyle \ mathrm {OPT} +c}$

Epsilon kifejezések

A szakirodalomban a c - ϵ (min: c + ϵ) maximalizálási (minimalizálási) probléma közelítési aránya azt jelenti, hogy az algoritmus közelítő aránya c ∓ ϵ tetszőleges ϵ> 0 esetén, de az arány nem (vagy nem lehetséges) ϵ = 0. esetén. Példa erre az optimális megközelíthetetlenség-közelítés hiánya-7 /8 + ϵ arány a kielégíthető MAX- 3SAT példákhoz Johan Håstad miatt . Amint azt korábban említettük, amikor c = 1, akkor a probléma polinomiális közelítési sémával rendelkezik .

Egy ϵ-kifejezés akkor jelenhet meg, ha egy közelítő algoritmus multiplikatív hibát és állandó hibát vezet be, míg az n-es példányok minimális optimuma a végtelenbe megy, mint n . Ebben az esetben a közelítési arány c ∓ k / OPT = c ∓ o (1) egyes c és k állandókra . Ha tetszőleges ϵ> 0, akkor elég nagy N -t választhatunk úgy, hogy a k / OPT <ϵ kifejezés minden n ≥ N -re . Minden rögzített ϵ esetében az n <N méretű példányok nyers erővel oldhatók meg, ezáltal minden ϵ> 0 -ra közelítő arányt mutatnak - közelítő algoritmusok létezése garanciával - c ∓ ϵ.

Lásd még

• Az uralom elemzése a garanciákat a számított megoldás rangja alapján veszi figyelembe.
• PTAS - egy közelítő algoritmus, amely paraméterként a közelítési arányt veszi figyelembe
• Az APX a konstans faktoros közelítő algoritmus problémáinak osztálya
• Közelítés-megőrző csökkentés
• Pontos algoritmus

Idézetek

Hivatkozások

• Vazirani, Vijay V. (2003). Közelítési algoritmusok . Berlin: Springer. ISBN 978-3-540-65367-7.
• 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ési algoritmusok, 1022–1056.
• Dorit S. Hochbaum , szerk. Közelítő algoritmusok NP-Hard problémákhoz , PWS Publishing Company, 1997. ISBN  0-534-94968-1 . 9. fejezet: Különféle megközelítések: jó, jobb, legjobb és még sok más
• Williamson, David P .; Shmoys, David B. (2011. április 26.), The Design of Approximation Algorithms , Cambridge University Press , ISBN 978-0521195270

Külső linkek

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski és Gerhard Woeginger , Az NP optimalizálási problémák összefoglalója .