Złożoność obliczeniowa/Wykład 7: Algorytmy aproksymacyjne

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 $\mathrm{\Pi }$ jest problemem {Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjnym}, jeżeli składa się z:

• zbioru instancji $D_{\mathrm{\Pi }}$. Rozmiarem instancji Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{I}} dla $I\in D_{\mathrm{\Pi }}$ jest ilość bitów potrzebnych do zapisania $I$,

• 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 $I$ jest instancją $\mathrm{\Pi }$, a $s$ dopuszczalnym rozwiązaniem $I$.