Algorytm aproksymacyjny

Algorytmy aproksymacyjne – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych.

Istotą algorytmu aproksymacyjnego, tym co odróżnia go od algorytmu heurystycznego, jest związana z każdym takim algorytmem informacja o koszcie zwracanego rozwiązania w stosunku do rozwiązania optymalnego. Mianowicie koszt rozwiązania zwróconego przez algorytm aproksymacyjny jest nie większy (w przypadku problemu minimalizacyjnego) albo nie mniejszy (w przypadku problemu maksymalizacyjnego) od rozwiązania optymalnego pomnożonego przez pewną stałą.

Definicja

Załóżmy, że mamy dany konkretny problem optymalizacyjny. Niech $F(x)$ oznacza zbiór dopuszczalnych rozwiązań tego problemu dla danych wejściowych $x$. Niech $c(y) \geqslant 0$, gdzie $y\in F(x)$, będzie funkcją kosztu rozwiązania dla tego problemu. Oznaczmy przez $c_{OPT}(x)$ koszt rozwiązania optymalnego dla danych $x$, mianowicie $c_{OPT}(x) = \min_{y\in F(x)}c(y)$ dla problemu minimalizacyjnego oraz $c_{OPT}(x) = \max_{y\in F(x)}c(y)$ dla problemu maksymalizacyjnego.

ε-aproksymacja

Algorytm A nazywamy ε-aproksymacyjnym, jeżeli dla dowolnych poprawnych danych wejściowych $x$, $A(x)\in F(x)$ oraz

$\frac{|c(A(x)) - c_{OPT}(x)|}{\max\{c(A(x)), c_{OPT}(x)\}} \leqslant \varepsilon,\quad 0\leqslant\varepsilon\leqslant 1.$

Przy takiej definicji zachodzi:

• $c(A(x)) \geqslant (1-\varepsilon)\cdot c_{OPT}(x)$, dla problemu maksymalizacyjnego,
• $c(A(x)) \leqslant \frac{1}{1-\varepsilon}\cdot c_{OPT}(x)$, dla problemu minimalizacyjnego.

Jeśli $\varepsilon = 0$ to algorytm zwraca rozwiązanie optymalne. Jeżeli natomiast $\varepsilon = 1$, to algorytm jest jedynie heurystyką, a więc zwracane przez niego rozwiązanie może być dowolnie odległe od optimum.

Czasem dopuszcza się również, że ε jest pewną funkcją od wielkości danych $x$.

ρ-aproksymacja

Algorytm A nazywamy ρ-aproksymacyjnym, jeśli dla dowolnych poprawnych danych wejściowych $x$, $A(x)\in F(x)$ oraz

$\max\Big\{\frac{c(A(x))}{c_{OPT}(x)},\frac{c_{OPT}(x)}{c(A(x))}\Big\}\leqslant \rho,\quad \rho\geqslant 1$

Wartość ρ określa ile razy otrzymane rozwiązanie jest gorsze od optimum. Dokładniej

• $c(A(x)) \geqslant \frac{1}{\rho}\cdot c_{OPT}(x)$, dla problemu maksymalizacyjnego,
• $c(A(x)) \leqslant \rho\cdot c_{OPT}(x)$, dla problemu minimalizacyjnego.

W przypadku gdy algorytm zwraca rozwiązanie optymalne, $\rho = 1$. Jeżeli rozwiązanie może być dowolnie odległe od optimum, to wartość ρ jest nieskończonością.

Powyższe dwie definicje są od siebie zależne. Zachodzi równość $\varepsilon = 1 - \frac{1}{\rho}$. Warto zauważyć, że nie ma potrzeby zaznaczania, która z powyższych definicji została wykorzystana przy określaniu konkretnego algorytmu, ponieważ $\varepsilon < 1$ (przypadek, w którym $\varepsilon = 1$ nie jest interesujący, gdyż wtedy mamy do czynienia z heurystyką), natomiast $\rho \geqslant 1$.

Zobacz też

• L-redukcja
• Wielomianowy schemat aproksymacji
• W pełni wielomianowy schemat aproksymacji

Bibliografia

1. 3. Approximation Classes. W: G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation. Springer, s. 87-91. ISBN 3-540-65431-3. [dostęp 2009-07-29]. (ang.)
2. 37. Algorytmy aproksymacyjne. W: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Wprowadzenie do algorytmów. Wyd. 4. Warszawa: Wydawnictwa Naukowo-Techniczne, s. 1073-1074. ISBN 83-204-2665-0. (pol.)

Linki zewnętrzne

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems (en).