Algoritmul de aproximare

În studiul operațiilor, algoritmul de aproximare este un algoritm. folosit pentru a găsi o soluție aproximativă la problema de optimizare.

Conceptul de algoritm de aproximare a fost formalizat în 1972 într-un articol de Garey, Graham și Ulman [1]. și mai târziu de Johnson [2]. Algoritmi de aproximare sunt adesea asociate cu sarcina NP-grea, pentru că pentru ei nu este greu de un algoritm eficient pentru soluția exactă în timp polinomial, deci are sens pentru a încerca să găsească aproape de soluția optimă. Spre deosebire de algoritmii euristici. oferind soluții suficient de bune într-un timp acceptabil, algoritmii de aproximare asigură o calitate probabilă a soluției la limite de timp predeterminate. În mod ideal, aproximarea oferă o soluție care diferă de cea optimă de un factor mic (de exemplu, în termen de 5%). Algoritmii de aproximare sunt folosiți din ce în ce mai mult pentru a rezolva problemele pentru care algoritmi exacți care lucrează pentru timpul polinomial sunt cunoscuți, dar care funcționează mult timp. Un exemplu tipic al unui algoritm de aproximare este algoritmul pentru rezolvarea problemei acoperire a vârfurilor în teoria graficelor. găsiți o margine neacoperită și adăugați ambele vârfuri la capacul superior și continuați până când toate sunt acoperite. Este clar că acoperirea obținută poate fi de două ori mai bună decât acoperirea optimă. O astfel de soluție este un algoritm de aproximare cu un coeficient constant de 2.

NP-probleme dificile diferă foarte mult în posibilitatea de aproximare. Unele, dintre care, de exemplu, problema ambalării în recipiente. poate fi aproximat cu orice coeficient mai mare decât 1 (această familie de algoritmi se numește schema aproximată a timpului polinomial) sau PTAS. Alte probleme nu pot fi aproximate cu nici un coeficient constant, sau chiar cu un coeficient polinomial (dacă P ≠ NP), și printre astfel de probleme este problema maximă a clichetului.

NP-problemele dificile pot fi adesea exprimate în termeni de programare întreg și rezolvate exact pentru timpul exponențial. Mulți algoritmi exponențiali provin de la reducerea la problema programării liniare a unei probleme cu valoare totală. [3]

O altă limitare este legată de faptul că abordarea este potrivită numai pentru problemele de optimizare, dar nu și pentru problemele de "recunoaștere" pură precum satisfacerea formulelor booleene. deși adesea cazul în care metoda este destul de potrivit pentru rezolvarea versiuni de optimizare a acelorași probleme, de exemplu, pentru problema satisfiabilitate maximal de formule Booleene (Max SAT).

Pentru unii algoritmi de aproximare, este posibil să se demonstreze unele proprietăți ale rezultatului aproximării. De exemplu, ρ -approksimatsionny algoritmA - prin algoritmul definitie pentru care raportul f (x) = soluții / valoarea de cost a problemei de aproximare A (x) pentru sarcina x nu este mai mare (sau mai puțin, în funcție de situație) funcționează pe care p coeficient valoarea optimă a valorii [4] [5]:

Coeficientul ρ se numește eficiența relativă garantată.

Algoritmul de aproximare are o eficiență absolută garantată sau o eroare limitată c. dacă pentru orice problemă x

Eficiența garantată este definită într-un mod similar. R (x, y), soluțiile y pentru problema x

unde f (y) este relația valoare / cost pentru soluția y a problemei x. Este clar că eficiența garantat nu este mai mică decât unul și egal cu unitatea numai în cazul în care y este soluția optimă. Dacă algoritmul O soluție asigură o eficiență maximă r (n), spunem că A este r (n) algoritm -approksimatsionnym este un coeficient de aproximare și r (n) [6] [7].

Este ușor de observat că în cazul problemei de minimizare, ambele definiții ale eficienței garantate dau o valoare, în timp ce pentru problema de maximizare r = ρ - 1>.

Un concept important al erorii relative. legată de probleme de optimizare, este definită în literatură în moduri diferite: de exemplu, V. Cann [7] o definește ca | O P T - f (y) / O P T -f (y) | / \ mathrm>. și Auziello și colab., [6] ca O P T - f (y) / max -f (y) \ / \ max \, f (y) \ >>.

Aici x denotă problema și R A (x) este randamentul garantat al A pentru x.

Randamentul asimptotic R A ∞> este definit într-un mod similar:

Eficacitate garantată: limitele de mai jos (de sus) pentru sarcini de minimizare (maximizare) cu valori diferite date

Tehnici pentru dezvoltarea algoritmilor

În prezent, există mai multe abordări standard pentru dezvoltarea unui algoritm de aproximare. Printre acestea:

1. Algoritm greedy.
2. Căutare locală.
3. Enumerarea și programarea dinamică.
4. Soluția problemei slabe a programării convexe cu posibilitatea obținerii unei soluții fracționate. Apoi soluția este transformată într-o soluție potrivită prin rotunjire. Metodele populare de relaxare a problemei sunt:
   1. Reducerea problemei programării liniare.
   2. Reducerea problemei programării semidefinite.
5. Definiți pentru problema unor metrici simple și soluționarea problemei cu această valoare.

În literatura de specialitate, coeficientul de aproximare pentru problema la maxim (sau minim) este scris ca c - ε (sau c + ε) pentru un număr c, în cazul în care există variații ale algoritmului cu coeficientul de aproximare c ∓ gruparea e pentru fiecare ε> 0. dar nu pentru ε = 0. Un exemplu de astfel de aproximare - coeficientul inaccesibilitate 7/8 pentru problema MAX-3SAT [8].

• Pierluigi Crescenzi, Viggo Kann, Halldórsson MAGNUS, Marek Karpinski și Gerhard Woeginger, un compendiu de NP probleme de optimizare.

Articole similare

• Algoritmul de curățare generală în sala de operație - cerințele și procedura generală

Trimiteți-le prietenilor: