Wikipedysta:Doil/brudnopis: Różnice pomiędzy wersjami
Usunięta treść Dodana treść
Nie podano opisu zmian |
aproks. |
||
Linia 30:
[[:Kategoria:Albumy muzyczne wydane w roku 1994]]
[[:Kategoria:Albumy metalowe]]
Istotą algorytmu aproksymacyjnego, w odróżnieniu od [[Heurystyka (informatyka)|algorytmów heurystycznych]], jest zapewnienie co do jakości zwracanego rozwiązania. 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 <math>F(x)</math> oznacza zbiór dopuszczalnych rozwiązań tego problemu dla danych wejściowych <math>x</math>. Niech <math>c(y) \geqslant 0</math>, gdzie <math>y\in F(x)</math>, będzie funkcją
Algorytm A nazywamy ε-aproksymacyjnym, jeżeli dla dowolnych poprawnych danych wejściowych <math>x</math>, <math>A(x)\in F(x)</math> oraz
:<math>\frac{|c(A(x)) - c_{OPT}(x)|}{\max\{c_{OPT}(x), c(A(x))\}} \leqslant \varepsilon,\quad 0\leqslant\varepsilon\leqslant 1.</math>
Przy takiej definicji zachodzi:
* <math>c(A(x)) \geqslant (1-\varepsilon)\cdot c_{OPT}(x)</math>, dla problemu maksymalizacyjnego,
* <math>c(A(x)) \leqslant \frac{1}{1-\varepsilon}\cdot c_{OPT}(x)</math>, dla problemu minimalizacyjnego.
Warto zauważyć, że jeśli <math>\varepsilon = 0</math> to algorytm zwraca rozwiązanie optymalne. Jeżeli natomiast <math>\varepsilon = 1</math>, to algorytm jest jedynie [[Heurystyka (informatyka)|heurystyką]], a więc zwracane przez niego rozwiązanie może być dowolnie odległe od optimum.
Czasem dopuszcza się również, że ε jest funkcją od wielkości danych <math>x</math>.
===Ograniczenie względne<ref>{{cytuj książkę | autor = Thomas H. Cormen | autor2 = Charles E. Leiserson | autor3 = Ronald L. Rivest| tytuł = Wprowadzenie do algorytmów | wydanie = 4 | wydawca = [[Wydawnictwa Naukowo-Techniczne]] | miejsce = Warszawa | strony = 1073-1074 | rozdział = 37. Algorytmy aproksymacyjne | isbn = 83-204-2665-0 }}</ref>===
Algorytm aproksymacyjny A ma ograniczenie względne ρ, jeśli zachodzi następująca nierówność
:<math>\max\Big\{\frac{c(A(x))}{c_{OPT}(x)},\frac{c_{OPT}(x)}{c(A(x))}\Big\}\leqslant \rho</math>
Wartość ρ określa zależność między zwracanym przez algorytm rozwiązaniem, a rozwiązaniem optymalnym. Mianowicie
* <math>c(A(x)) \geqslant \rho\cdot c_{OPT}(x)</math> i <math>\rho < 1</math> dla problemu maksymalizacyjnego,
* <math>c(A(x)) \leqslant \rho\cdot c_{OPT}(x)</math> i <math>\rho > 1</math> dla problemu minimalizacyjnego.
Zgodnie z powyższą definicją prawdziwe są równości
* <math>\rho = (1-\varepsilon)</math>, dla problemu maksymalizacyjnego,
* <math>\rho = \frac{1}{1-\varepsilon}</math>, dla problemu minimalizacyjnego.
===Błąd względny===
Zamiast stosunku rozwiązania przybliżonego do optymalnego, czasami wygodniej jest stosować pojęcie błędu względnego, które definiuje się w następujący sposób
:<math>\frac{|c(A(x)) - c_{OPT}(x)|}{c_{OPT}(x)}</math>
== Zobacz też ==
* [[L-redukcja]]
* [[Wielomianowy schemat aproksymacji]]
* [[W pełni wielomianowy schemat aproksymacji]]
{{Przypisy}}
== Linki zewnętrzne ==
* Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''] <small>(en)</small>.
| |||