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 $|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 $|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$.

Definicja 1.2

Rozwiązaniem optymalnym minimalizacji (maksymalizacji) dla instancji $I$ problemu Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjnego $\mathrm{\Pi }$ jest każde z rozwiązań dopuszczalnych, dla którego funkcja celu jest minimalna (maksymalna).

Wartość minimalną (maksymalną) funkcji celu oznaczamy przez Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\opt_\Pi}{I}} i nazywamy optimum. Często będziemy używać skróconej notacji Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \opt} , kiedy nie będzie wątpliwości jaki problem i jego instancję mamy na myśli.

Problemy optymalizacyjne, a problemy decyzyjne

Załóżmy, że mamy problem minimalizacji $\mathrm{\Pi }$. Dla problemów maksymalizacyjnych całe rozumowanie jest analogiczne.

Z problemem $\mathrm{\Pi }$ w naturalny sposób jest związany problem decyzyjny $\mathrm{\Sigma }$ równoważny pytaniu: " Czy dla zadanej instancji $I$ problemu $\mathrm{\Pi }$ i liczby $B$ istnieje rozwiązanie dopuszczalne osiągające wartość funkcji celu mniejszą niż $B$?".

Znając wartość optimum dla $I$ można natychmiast odpowiadać na pytania $\mathrm{\Sigma }$. Z drugiej strony, zazwyczaj można łatwo znaleźć wartość Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\opt_\Pi}{I}} używając algorytmu rozwiązującego $\mathrm{\Sigma }$. Wystarczy użyć odpowiednio dobranego wyszukiwania binarnego.

Dość oczywistą i ważną własnością jest, że jeżeli problem $\mathrm{\Sigma }$ jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełny, to skojarzony z nim problem minimalizacji jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -trudny. W dalszej części wykładu będziemy analizować tylko problemy, których wersje decyzyjne są Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełne.

Uwaga 1.3

Dla wielu problemów sama tylko umiejętność znajdowania wartości optimum wystarcza, aby w czasie wielomianowym znaleźć również rozwiązanie optymalne. Nie jest to jednak reguła - są problemy, o których zostało pokazane, że nie mają tej własności. Dlatego trzeba rozróżniać problem znalezienia wartości optimum i znalezienia rozwiązania optymalnego. Oczywiście ten drugi jest dla nas znacznie ciekawszy.

Rozwiązania aproksymacyjne

Wprowadzimy teraz pojęcie algorytmu aproksymacyjnego. Nie będzie ona zbyt restrykcyjna i będzie obejmować każdy algorytm znajdujący jakiekolwiek rozwiązania. Dopiero później zdefiniujemy pojęcia, które pozwolą mówić o skuteczności takich algorytmów.

Definicja 1.4

Algorytmem aproksymacyjnym ${𝒜}$ dla minimalizacji (maksymalizacji) problemu Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjnego $\mathrm{\Pi }$ nazywamy algorytm, który działa w czasie wielomianowym i dla każdej instancji problemu $\mathrm{\Pi }$ znajduje rozwiązanie dopuszczalne.

W domyśle interesują nas algorytmy, które znajdują rozwiązania przybliżające rozwiązanie optymalne. W związku z tym chcemy ograniczyć błąd jaki może popełnić algorytm. Stąd definicja:

Definicja 2.5

Jeżeli dla problemu minimalizacji $\mathrm{\Pi }$ i algorytmu ${𝒜}$ istnieje stała Parser nie mógł rozpoznać (nieznana funkcja „\realsplus”): {\displaystyle a \in \realsplus} , taka że:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle a \geq 1 \wedge \forall_{I \in D_\Pi} \func{\obj_\Pi}{I,\func{\mathcal{A}}{I}} \leq a \cdot \func{\opt_\Pi}{I}, }

to ${𝒜}$ jest algorytmem $a$-aproksymacyjnym. Można też powiedzieć, że $a$ jest stałą aproksymacji algorytmu ${𝒜}$.

Jeżeli $\mathrm{\Pi }$ jest problemem maksymalizacji, to Algorytm ${𝒜}$ musi spełniać odwrotną nierówność:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle a \leq 1 \wedge \forall_{I \in D_\Pi} \func{\obj_\Pi}{I,\func{\mathcal{A}}{I}} \geq a \cdot \func{\opt_\Pi}{I} }

Istotne jest wymaganie, aby Parser nie mógł rozpoznać (nieznana funkcja „\realsplus”): {\displaystyle a \in \realsplus} , gdyż każdy algorytm aproksymacyjny spełniałby powyższą równość dla $a\le 0$.

Czasem algorytm nie ma stałej aproksymacji, ale różnicę pomiędzy rozwiązaniami znajdowanymi, a optymalnymi można ograniczyć przez funkcję zależną od rozmiaru instancji. Chcemy mieć możliwość uchwycenia również takich zależności.

Definicja 2.6

Jeżeli dla algorytmu ${𝒜}$ rozwiązującego problem minimalizacji $\mathrm{\Pi }$ istnieje funkcja Parser nie mógł rozpoznać (nieznana funkcja „\naturals”): {\displaystyle \alpha : \naturals \rightarrow \realsplus} , taka że

Parser nie mógł rozpoznać (nieznana funkcja „\naturals”): {\displaystyle \forall_{n \in \naturals} \func{\alpha}{n} \geq 1 \wedge \forall_{I\in D_\Pi} \func{\obj_\Pi}{I,\func{\mathcal{A}}{I}} \leq \func{\alpha}{\size{I}} \cdot \func{\opt_\Pi}{I}, }

to ${𝒜}$ jest algorytmem $\alpha$-aproksymacyjnym.

Definicja dla problemu maksymalizacji jest analogiczna.

Zaprezentowane definicje pozwalają badać pesymistyczne zachowanie algorytmów. Często można również przeprowadzić analizę przypadku średniego, w którym znalezione rozwiązania są zazwyczaj znacząco lepsze od tych, które występują w przypadku pesymistycznym. My jednak skupimy się poszukiwaniu algorytmów, które dają gwarancję ograniczonego błędu dla dowolnej instancji.

Ćwiczenie 2.7 [Problemy decyzyjne jako problemy optymalizacyjne]

Przyjrzyjmy się bliżej związkom Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełnych problemów decyzyjnych i Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjnych. Skorzystamy z definicji języka $L$ należącego klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} :

Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle L = \defset{x}{\exists_y \braq{x,y} \in R} }

gdzie $y$ jest świadkiem wielomianowo zrównoważonej relacji $R$. Możemy teraz zdefiniować problem optymalizacyjny związany z językiem $L$. Instancją problemu ${\mathrm{\Pi }}_L$ będzie dowolny ciąg bitów $x$. Rozwiązaniami dopuszczalnymi będą dowolne ciągi $y$ o długości wielomianowo ograniczonej od Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{x}} (z tym samym wielomianem który decyduje o zrównoważeniu relacji $R$). Funkcja celu natomiast będzie zdefiniowana następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\obj_{\Pi_L}}{x,y} = \begincases 0\quad\braq{x,y} \notin R \\ 1\quad\braq{x,y} \in R \endcases }

Pokaż, że jest to dobrze zdefiniowany problem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -optymalizacyjny i że o ile problem $L$ jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełny i Parser nie mógł rozpoznać (nieznana funkcja „\pneqnp”): {\displaystyle \pneqnp} , to dla problemu maksymalizacji ${\mathrm{\Pi }}_L$ nie ma algorytmu $a$-aproksymacyjnego.

Wskazówka

Użyj algorytmu $a$-aproksymacyjnego do znalezienia świadka relacji $R$ lub stwierdzenia, że taki świadek nie istnieje.

Rozwiązanie

Żeby uzasadnić dobre postawienie problemu wystarczy powiedzieć, że dziedzina instancji jest dobrze określona, dla każdej instancji istnieją rozwiązania i są one wielomianowego rozmiaru, oraz że zarówno funkcja sprawdzająca dopuszczalność rozwiązania, jak i funkcja celu są obliczalne w czasie wielomianowym. Wszystkie te własności są zapewnione przez wielomianowe zrównoważenie relacji $R$.

Załóżmy teraz, że ${𝒜}$ jest algorytmem $a$-aproksymacyjnym dla problemu ${\mathrm{\Pi }}_L$. Jeżeli $x\in L$, to Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\opt_{\Pi_L}}{x} = 1} , a w przeciwnym wypadku Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\opt_{\Pi_L}}{x} = 0} . W związku z tym rozwiązanie znajdowane przez algorytm Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\mathcal{A}}{x}} musi mieć wartość funkcji celu nie mniejszą niż $a>0$ dla $x\in L$. Oznacza to, że dla $x\in L$ musi zachodzić Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \braq{x,\func{\mathcal{A}}{x}} \in R} , bo w przeciwnym wypadku Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\obj_{\Pi_L}}{x,\func{\mathcal{A}}{x}}=0} . Dla dowolnego ciągu $x$ możemy zatem uruchomić algorytm ${𝒜}$, który działa w czasie wielomianowym i sprawdzić, czy znalezione rozwiązanie jest świadkiem relacji $R$ dla $x$.

Pokazaliśmy właśnie algorytm wielomianowy rozwiązujący Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełny problem $L$, co jest sprzeczne z założeniem Parser nie mógł rozpoznać (nieznana funkcja „\pneqnp”): {\displaystyle \pneqnp} .

}}

Pokrycie wierzchołkowe - NODE COVER

Pierwszym problemem, którego możliwość aproksymacji zbadamy jest problem minimalizacji rozmiaru pokrycia wierzchołkowego grafu. Jest to optymalizacyjna wersja problemu NODE COVER. Instancją problemu jest pojedynczy graf. Rozwiązaniami dopuszczalnymi są pokrycia wierzchołkowe tego grafu, a funkcją celu jest rozmiar znalezionego pokrycia. Interesuje nas oczywiście minimalizacja rozmiaru pokrycia.

Zarówno sprawdzenia dopuszczalności rozwiązania, jak i obliczenia funkcji celu można łatwo dokonać w czasie liniowym od rozmiaru grafu.

Algorytm zachłanny

Na początek przeanalizujemy najbardziej naturalne podejście do rozwiązania. Wykorzystamy metodę zachłanną konstruowania algorytmów. Wydaje się, że wybieranie do pokrycia wierzchołków, które mają największy stopień (a więc pokrywają najwięcej krawędzi), pozwala najszybciej pokryć cały graf. Prowadzi to do następującego algorytmu:

Algorytm zachłanny

Dopóki w grafie są krawędzie:

1. wybierz wierzchołek $v$ o największym stopniu.

1. dodaj $v$ do pokrycia i usuń z grafu wszystkie krawędzie incydentne z $v$.

Okazuje się jednak, że ten algorytm, nie osiąga stałej aproksymacji. Aby dowieść tego faktu, wystarczy spojrzeć na poniższy przykład:

Przykład 2.2

pokrycie wierzchołkowe - ZO-7.1

Algorytm zachłanny najpierw wybierze do pokrycia wierzchołek z grupy $B_n$ (ma on stopień $n$, gdy tymczasem wierzchołki z grupy $A$ mają stopień co najwyżej $n-1$). Po usunięciu tego wierzchołka stopień wierzchołków z $A$ spadnie do co najwyżej $n-2$, więc algorytm wybierze wszystkie wierzchołki z grupy $B_{n-1}$, itd.

W wyniku działania algorytmu zostanie skonstruowane pokrycie $B_n\cup B_{n-1}\cup \dots \cup B_2$ o rozmiarze Parser nie mógł rozpoznać (nieznana funkcja „\floor”): {\displaystyle \floor{\frac{n}{n}}+\floor{\frac{n}{n-1}}+\ldots+\floor{\frac{n}{2}}} , gdy tymczasem rozwiązaniem optymalnym jest pokrycie $A$ o rozmiarze $n$.

Używając prostej analizy z wykorzystaniem sumy ciągu harmonicznego można pokazać, że dla instancji z tej konkretnej rodziny rozwiązanie znajdowane przez algorytm jest Parser nie mógł rozpoznać (nieznana funkcja „\notT”): {\displaystyle \notT{\log n}} razy gorsze od rozwiązania optymalnego.

Pierwsze, bardzo naturalne, podejście do problemu nie doprowadziło nas do algorytmu ze stałą aproksymacji. Niestety, regułą jest, że nie da się osiągnąć aproksymacji problemów Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełnych tak prostymi sposobami i trzeba szukać bardziej wyrafinowanych metod. Oczywiście są od tej reguły wyjątki, które pokażemy. Teraz skonstruujemy algorytm $2$-aproksymacyjny dla problemu pokrycia wierzchołkowego.

Algorytm skojarzeniowy

Algorytm ten jest bardzo prosty w konstrukcji:

Algorytm skojarzeniowy

1. Znajdź dowolne skojarzenie maksymalne (w sensie inkluzji) $M$ w grafie $G$.

1. Wypisz wszystkie wierzchołki występujące w $M$.

Twierdzenie 2.4

Algorytm skojarzeniowy jest algorytmem $2$-aproksymacyjnym dla problemu minimalizacji rozmiaru pokrycia wierzchołkowego.

Dowód

Najpierw musimy pokazać, że wierzchołki $M$ tworzą pokrycie $G$. Gdyby jakaś krawędź nie była pokryta, oznaczałoby to, że żaden z jej końców nie należy do $M$ i można by poszerzyć skojarzenie o tą krawędź, co przeczy maksymalności $M$.

Niech $O$ będzie optymalnym pokryciem. Zauważmy, że ponieważ $M$ jest skojarzeniem, to zawiera Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{M}} krawędzi, z których żadne dwie nie mają wspólnego wierzchołka. Zatem w pokryciu $O$ musi się znajdować przynajmniej jeden z końców każdej z tych krawędzi (w przeciwnym wypadku, krawędź ta byłaby niepokryta przez $O$). Z tego wynika, że

Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \size{M} \leq \size{O}\textnormal{,} }

a liczba wierzchołków w pokryciu znalezionym przez algorytm wynosi $2M$, co dowodzi że jest to algorytm $2$-aproksymacyjny.

Ćwiczenie 2.5 [Pesymistyczny przypadek dla algorytmu skojarzeniowego]

Pokaż rodzinę grafów, dla których wynik algorytmu skojarzeniowego jest dokładnie $2$ razy gorszy od optymalnego.

Wskazówka

Dla grafów z tej rodziny pokrycie wierzchołkowe musi zawierać dokładnie po jednym wierzchołku z każdej krawędzi skojarzenia maksymalnego.

Rozwiązanie

Przykładem takiej rodziny grafów są pełne grafy dwudzielne $K_{n,n}$ z $2n$ wierzchołkami. Każde skojarzenie maksymalne w takim grafie ma $n$ krawędzi, a więc $2n$ wierzchołków. Tymczasem minimalne pokrycie wierzchołkowe składa się z dokładnie $n$ wierzchołków.

[[Rysunek:graf $K_{n,n}$ - ZO-7.3]]

}}

Ćwiczenie 2.6 [Konstrukcja rozwiązania optymalnego z wyrocznią podającą optimum]

Pokaż, że używając wyroczni podającej rozmiar najmniejszego pokrycia wierzchołkowego dla zadanego grafu, można znaleźć rozwiązanie optymalne problemu NODE COVER w czasie wielomianowym.

Wskazówka

Użyj wyroczni do stwierdzenia czy konkretny wierzchołek należy do jakiegoś rozwiązania optymalnego.

Rozwiązanie

Oznaczmy odpowiedź wyroczni dla grafu $G$ przez Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\mathcal{A}}{G}} .

Dla danego wierzchołka $x$ możemy przy pomocy wyroczni ${𝒜}$ stwierdzić, czy istnieje pokrycie wierzchołkowe minimalnego rozmiaru zawierające $x$. Wystarczy porównać wartości Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\mathcal{A}}{G}} i Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\mathcal{A}}{G-x}} . Druga z nich jest mniejsza od pierwszej wtedy i tylko wtedy, gdy istnieje pokrycie wierzchołkowe minimalnego rozmiaru zawierające $x$.

Po znalezieniu takiego wierzchołka $x$ wystarczy go dodać do konstruowanego pokrycia, usunąć z grafu i kontynuować proces dopóki w grafie są jeszcze jakieś krawędzie.

}}

Problem maksymalnego przekroju - MAX CUT

Ciekawym problemem optymalizacyjnym, który daje się łatwo aproksymować jest problem maksymalnego przekroju.