Złożoność obliczeniowa/Wykład 7: Algorytmy aproksymacyjne: Różnice pomiędzy wersjami
Nie podano opisu zmian |
|||
| Linia 14: | Linia 14: | ||
{{definicja|1.1|| | {{definicja|1.1|| | ||
Problem <math>\Pi</math> jest problemem | Problem <math>\Pi</math> jest problemem <math>\cc{NP}</math>-optymalizacyjnym, jeżeli składa się z: | ||
* zbioru instancji <math>D_\Pi</math>. Rozmiarem instancji <math>\size{I}</math> dla <math>I \in D_\Pi</math> jest ilość bitów potrzebnych do zapisania <math>I</math>, | * zbioru instancji <math>D_\Pi</math>. Rozmiarem instancji <math>\size{I}</math> dla <math>I \in D_\Pi</math> jest ilość bitów potrzebnych do zapisania <math>I</math>, | ||
* zbioru rozwiązań dopuszczalnych dla każdej instancji <math>\func{S_\Pi}{I}</math>. Zbiór ten musi posiadać dodatkowe własności: | * zbioru rozwiązań dopuszczalnych dla każdej instancji <math>\func{S_\Pi}{I}</math>. Zbiór ten musi posiadać dodatkowe własności: | ||
** <math>\func{S_\Pi}{I} \neq \emptyset</math> - dla każdej instancji jest jakieś rozwiązanie dopuszczalne, | ** <math>\func{S_\Pi}{I} \neq \emptyset</math> - dla każdej instancji jest jakieś rozwiązanie dopuszczalne, | ||
** każde <math>s \in \func{S_\Pi}{I}</math> ma rozmiar wielomianowy od <math>\size{I}</math> i istnieje algorytm wielomianowy, który sprawdza czy dla pary <math>\braq{I,s}</math> zachodzi <math>s \in \func{S_\Pi}{I}</math>, | ** każde <math>s \in \func{S_\Pi}{I}</math> ma rozmiar wielomianowy od <math>\size{I}</math> i istnieje algorytm wielomianowy, który sprawdza czy dla pary <math>\braq{I,s}</math> zachodzi <math>s \in \func{S_\Pi}{I}</math>, | ||
* funkcji celu <math>\obj_\Pi</math>, która przyporządkowuje rozwiązaniom dopuszczalnym nieujemne wartości wymierne. Funkcja ta musi być wielomianowo obliczalna dla każdej pary <math>\braq{I,s}</math>, gdzie <math>I</math> jest instancją <math>\Pi</math>, a <math>s</math> dopuszczalnym rozwiązaniem <math>I</math>. | * funkcji celu <math>\obj_\Pi</math>, która przyporządkowuje rozwiązaniom dopuszczalnym nieujemne wartości wymierne. Funkcja ta musi być wielomianowo obliczalna dla każdej pary <math>\braq{I,s}</math>, gdzie <math>I</math> jest instancją <math>\Pi</math>, a <math>s</math> dopuszczalnym rozwiązaniem <math>I</math>. | ||
}} | }} | ||
Wersja z 19:58, 16 sie 2006
W poprzednich modułach pokazaliśmy o wielu problemach, że są Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełne. Jeżeli Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} , to żaden z tych problemów nie może mieć rozwiązania, które działałoby w satysfakcjonujący sposób. Jednak wiele z nich to istotne zagadnienia praktyczne i metody choćby częściowego radzenia sobie z nimi są bardzo potrzebne. Konstruowane rozwiązania heurystyczne idą zazwyczaj w dwóch kierunkach:
- wyszukiwanie takich podproblemów, dla których można znaleźć rozwiązanie w czasie wielomianowym,
- szukanie algorytmów aproksymacyjnych, które nie rozwiązują problemu dokładnie, ale podają rozwiązania przybliżone do poprawnych.
W tym i w dwóch następnych modułach zajmiemy się właśnie tym drugim podejściem. Przedstawimy formalizmy, które służą do opisu algorytmów aproksymacyjnych i przeanalizujemy najistotniejsze przykłady.
Problem optymalizacyjny
Zwykłe problemy decyzyjne nie nadają się do aproksymowania, bo nie da się przybliżyć rozwiązania konkretnej instancji problemu, którym jest albo "tak", albo "nie". Problemy, które są podatne na aproksymację, to takie, w których odpowiedzią na konkretną instancję problemu jest jakiś kombinatoryczny obiekt z klasy rozwiązań dopuszczalnych. Wprowadzając dodatkowo funkcję celu na obiektach klasy rozwiązań dopuszczalnych możemy żądać, aby znaleziona odpowiedź minimalizowała (lub maksymalizowała) wartość tej funkcji po wszystkich rozwiązaniach dopuszczalnych.
Problem, który ma powyżej przedstawioną charakterystykę nazywamy problemem optymalizacyjnym i przedstawimy teraz jego formalną definicję w interesującej nas wersji dotyczącej aproksymowania problemów z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} w czasie wielomianowym:
Definicja 1.1
Problem jest problemem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjnym, jeżeli składa się z:
- zbioru instancji . Rozmiarem instancji Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{I}} dla jest ilość bitów potrzebnych do zapisania ,
- zbioru rozwiązań dopuszczalnych dla każdej instancji Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{S_\Pi}{I}}
. Zbiór ten musi posiadać dodatkowe własności:
- Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{S_\Pi}{I} \neq \emptyset} - dla każdej instancji jest jakieś rozwiązanie dopuszczalne,
- każde Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle s \in \func{S_\Pi}{I}} ma rozmiar wielomianowy od Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{I}} i istnieje algorytm wielomianowy, który sprawdza czy dla pary Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \braq{I,s}} zachodzi Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle s \in \func{S_\Pi}{I}} ,
- funkcji celu Parser nie mógł rozpoznać (nieznana funkcja „\obj”): {\displaystyle \obj_\Pi} , która przyporządkowuje rozwiązaniom dopuszczalnym nieujemne wartości wymierne. Funkcja ta musi być wielomianowo obliczalna dla każdej pary Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \braq{I,s}} , gdzie jest instancją , a dopuszczalnym rozwiązaniem .
