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

Wprowadzenie

W poprzednich modułach pokazaliśmy o wielu problemach, że są $\mathrm{N}\mathrm{P}$-zupełne. Jeżeli $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, 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 $\mathrm{N}\mathrm{P}$ w czasie wielomianowym:

Definicja 2.1

Problem $\mathrm{\Pi }$ jest problemem $\mathrm{N}\mathrm{P}$-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 $S_{\mathrm{\Pi }}I$. Zbiór ten musi posiadać dodatkowe własności:
  • $S_{\mathrm{\Pi }}I\ne \mathrm{\varnothing }$. Dla każdej instancji jest jakieś rozwiązanie dopuszczalne,
  • każde $s\in S_{\mathrm{\Pi }}I$ ma rozmiar wielomianowy od $|I|$ i istnieje algorytm wielomianowy, który sprawdza, czy dla pary ${I},{s}$ zachodzi $s\in S_{\mathrm{\Pi }}I$,
• funkcji celu ${\text{obj}}_{\mathrm{\Pi }}$, która przyporządkowuje rozwiązaniom dopuszczalnym nieujemne wartości wymierne. Funkcja ta musi być wielomianowo obliczalna dla każdej pary ${I},{s}$, gdzie $I$ jest instancją $\mathrm{\Pi }$, a $s$ dopuszczalnym rozwiązaniem $I$.

Definicja 2.2

Rozwiązaniem optymalnym minimalizacji (maksymalizacji) dla instancji $I$ problemu $\mathrm{N}\mathrm{P}$-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 ${\text{opt}}_{\mathrm{\Pi }}I$ i nazywamy optimum. Często będziemy używać skróconej notacji $\text{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ść ${\text{opt}}_{\mathrm{\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 $\mathrm{N}\mathrm{P}$-zupełny, to skojarzony z nim problem minimalizacji jest $\mathrm{N}\mathrm{P}$-trudny. W dalszej części wykładu będziemy analizować tylko problemy, których wersje decyzyjne są $\mathrm{N}\mathrm{P}$-zupełne.

Uwaga 2.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 i 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 ono zbyt restrykcyjne 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 2.4

Algorytmem aproksymacyjnym ${𝒜}$ dla minimalizacji (maksymalizacji) problemu $\mathrm{N}\mathrm{P}$-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 $a\in {\mathbb{ℝ}}^{+}$, taka że:

$a\ge 1\wedge {\mathrm{\forall }}_{I\in D_{\mathrm{\Pi }}}{\text{obj}}_{\mathrm{\Pi }}(I,{𝒜}(I))\le a\cdot {\text{opt}}_{\mathrm{\Pi }}(I)\text{,}$

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ść:

$a\le 1\wedge {\mathrm{\forall }}_{I\in D_{\mathrm{\Pi }}}{\text{obj}}_{\mathrm{\Pi }}(I,{𝒜}(I))\ge a\cdot {\text{opt}}_{\mathrm{\Pi }}(I)\text{.}$

Istotne jest wymaganie, aby $a\in {\mathbb{ℝ}}^{+}$, 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 $\alpha :\mathbb{\mathbb{N}}\to {\mathbb{ℝ}}^{+}$, taka że:

${\mathrm{\forall }}_{n\in \mathbb{\mathbb{N}}}\alpha (n)\ge 1\wedge {\mathrm{\forall }}_{I\in D_{\mathrm{\Pi }}}{\text{obj}}_{\mathrm{\Pi }}(I,{𝒜}(I))\le \alpha |I|\cdot {\text{opt}}_{\mathrm{\Pi }}(I)\text{,}$

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 $\mathrm{N}\mathrm{P}$-zupełnych problemów decyzyjnych i $\mathrm{N}\mathrm{P}$-optymalizacyjnych. Skorzystamy z definicji języka $L$ należącego klasy $\mathrm{N}\mathrm{P}$:

$L=\{x:{\mathrm{\exists }}_y(x,y)\in R\}\text{,}$

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 $|x|$ (z tym samym wielomianem który decyduje o zrównoważeniu relacji $R$). Funkcja celu natomiast będzie zdefiniowana następująco:

${\text{obj}}_{{\mathrm{\Pi }}_L}(x,y)=\{\begin{array}{l}0(x,y)\notin R\\ 1(x,y)\in R\end{array}\text{.}$

Pokaż, że jest to dobrze zdefiniowany problem $\mathrm{N}\mathrm{P}$-optymalizacyjny i że o ile problem $L$ jest $\mathrm{N}\mathrm{P}$-zupełny i $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, 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 ${\text{opt}}_{{\mathrm{\Pi }}_L}(x)=1$, a w przeciwnym wypadku ${\text{opt}}_{{\mathrm{\Pi }}_L}(x)=0$. W związku z tym rozwiązanie znajdowane przez algorytm ${𝒜}(x)$ musi mieć wartość funkcji celu nie mniejszą niż $a>0$ dla $x\in L$. Oznacza to, że dla $x\in L$ musi zachodzić $(x,{𝒜}(x))\in R$, bo w przeciwnym wypadku ${\text{obj}}_{{\mathrm{\Pi }}_L}(x,{𝒜}(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 $\mathrm{N}\mathrm{P}$-zupełny problem $L$, co jest sprzeczne z założeniem $\mathrm{P}\ne \mathrm{N}\mathrm{P}$.

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 3.1 [Algorytm zachłanny]

---

Dopóki w grafie są krawędzie:

1. Wybierz wierzchołek $v$ o największym stopniu.
2. 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:

Pokrycie wierzchołkowe.

Przykład 3.2

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 $\lfloor \frac{n}{n}\rfloor +\lfloor \frac{n}{n-1}\rfloor +\dots +\lfloor \frac{n}{2}\rfloor$, gdy tymczasem rozwiązaniem optymalnym jest pokrycie $A$ o rozmiarze $n$ (rysunek Pokrycie wierzchołkowe).

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 $\mathrm{\Theta }(\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 $\mathrm{N}\mathrm{P}$-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 3.3 [Algorytm skojarzeniowy]

---

(animacja Algorytm skojarzeniowy)

1. Znajdź dowolne skojarzenie maksymalne (w sensie inkluzji) $M$ w grafie $G$.
2. Wypisz wszystkie wierzchołki występujące w $M$.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Algorytm skojarzeniowy.

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

$|M|\le |O|\text{,}$

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

Ćwiczenie 3.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

Graf K(n,n).

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.

Ćwiczenie 3.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 ${𝒜}(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 ${𝒜}(G)$ i ${𝒜}(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.

Problem [Maksymalny przekrój MAX CUT]

Mając dany graf $G={V},{E}$ należy podzielić wierzchołki $V$ na dwa podzbiory $V_1$ i $V_2$, tak żeby zmaksymalizować liczbę krawędzi pomiędzy $V_1$, a $V_2$.

Podamy od razu dwa różne algorytmy aproksymacyjne dla tego problemu:

Algorytm 4.1 [Algorytm zachłanny]

---

1. Ustaw $V_1=\mathrm{\varnothing }$ i $V_2=\mathrm{\varnothing }$.
2. Przeglądając wierzchołki $V$ w dowolnej kolejności, dodawaj każdy z nich do tego ze zbiorów $V_1$ lub $V_2$, z którym łączy go mniej krawędzi.

Algorytm 4.2 [Algorytm poszukujący lokalnego optimum]

---

1. Ustaw $V_1=V$ i $V_2=\mathrm{\varnothing }$.
2. Dopóki istnieje w grafie wierzchołek $x$ taki, że przesunięcie go z jednego zbioru do drugiego zwiększa rozmiar przekroju, dokonuj takiego przesunięcia.

Twierdzenie 4.3

Algorytm zachłanny i poszukujący lokalnego optimum są algorytmami $\frac{1}{2}$-aproksymacyjnymi.

Dowód

Dowód dla algorytmu zachłannego jest wyjątkowo prosty. Niech $v_1,v_2,\dots ,v_n$ będzie kolejnością w jakiej są przeglądane wierzchołki. Oznaczmy przez $e_i$ liczbę krawędzi dodanych do przekroju, kiedy był dodawany wierzchołek $v_i$, a przez $\overline{e_i}$ liczbę pozostałych krawędzi łączących $v_i$ z $v_1,v_2,\dots ,v_{i-1}$. Algorytm wybiera przyporządkowanie wierzchołka $v_i$ w ten sposób, że $e_i\ge \overline{e_i}$. Mamy zatem:

$\sum _{i=1}^n{e}_i\ge \sum _{i=1}^n\overline{e_i}\text{.}$

Ponieważ każda z krawędzi albo znajduje się w przekroju, albo nie, to zachodzi:

$\sum _{i=1}^n(e_i+\overline{e_i})=|E|$

W związku z tym mamy, że przynajmniej połowa wszystkich krawędzi jest w przekroju znalezionym przez algorytm zachłanny. To oczywiście dowodzi $\frac{1}{2}$-aproksymowalności, gdyż w rozwiązaniu optymalnym nie może być więcej krawędzi niż w całym grafie.

Żeby pokazać, że algorytm poszukujący lokalnego optimum jest $\frac{1}{2}$-aproksymacyjny, nadajmy wierzchołkom numerację $v_1,v_2,\dots ,v_n$ i oznaczmy przez $\overline{e_i}$ liczbę krawędzi łączących $v_i$ z wierzchołkami z tego samego zbioru, a przez $e_i$ liczbę pozostałych krawędzi z nim incydentnych. Tu również zachodzi $e_i\ge \overline{e_i}$. Gdyby dla któregoś z wierzchołków było przeciwnie, to przeniesienie go do drugiego zbioru zwiększyłoby rozmiar przekroju. Dalsza analiza jest taka sama jak poprzednio z tą różnicą, że:

$\sum _{i=1}^n(e_i+\overline{e_i})=2|E|\text{.}$

W przeciwieństwie do problemu NODE COVER udało nam się skonstruować algorytmy ze stałą aproksymacji dla MAX CUT, używając bardzo prostych technik: techniki zachłannej i lokalnych ulepszeń. Pokazuje to, że czasem zanim zaczniemy głębiej analizować jakiś problem, warto sprawdzić takie najprostsze podejścia.

Ćwiczenie 4.4

Pokaż, że decyzyjna wersja problemu MAX CUT jest $\mathrm{N}\mathrm{P}$-zupełna.

Wskazówka

Skonstruuj redukcję problemu NAE$3$SAT do MAXCUT. Stwórz po jednym wierzchołku dla każdego literału.

Rozwiązanie

Pokażemy redukcję logarytmiczną problemu NAE$3$SAT do MAXCUT. Niech $\varphi$ będzie formułą problemu NAE$3$SAT. Musimy dokonać pewnej modyfikacji $\varphi$. Po pierwsze, usuwamy wszystkie klauzule zawierające literał $x$ i jednocześnie jego zaprzeczenie $\mathrm{\neg }x$. Takie klauzule i tak są spełnione przez każde wartościowanie.

Druga modyfikacja formuły $\varphi$ polega na takiej zamianie klauzul, żeby żadne dwie nie miały dwóch wspólnych literałów. Można to osiągnąć w następujący sposób, że zamiast dwóch klauzul postaci $(a\vee b\vee c)$ i $(a\vee b\vee d)$ tworzymy cztery klauzule z dwiema nowymi zmiennymi $x$ i $y$:

$\begin{array}{r}a\vee b\vee c\text{,}\\ a\vee x\vee d\text{,}\\ b\vee \mathrm{\neg }x\vee y\text{,}\\ \mathrm{\neg }b\vee x\vee y\text{.}\end{array}$

Dwie ostatnie klauzule są NAE-spełnione wtedy i tylko wtedy, gdy zmienna $x$ ma tę samą wartość co $b$.

Po tych modyfikacjach $\varphi$ możemy skonstruować instancję problemu MAX CUT. Niech $\varphi$ ma $n$ zmiennych i $m$ klauzul. Stworzymy graf o $2n$ wierzchołkach i $n+3m$ krawędziach. Dla każdej zmiennej $x$ mamy dwa wierzchołki odpowiadające literałom $x$ i $\mathrm{\neg }x$. Dodajemy następujące krawędzie:

• krawędź łączącą $x$ z $\mathrm{\neg }x$ dla każdej zmiennej $x$,
• dla każdej klauzuli $a\vee b\vee c$ trzy krawędzie tworzące trójkąt oparty na literałach $a$, $b$, $c$.

Zastosowane modyfikacje formuły $\varphi$ gwarantują, że żadna z krawędzi nie została dodana wielokrotnie.

Udowodnimy teraz, że formuła $\varphi$ jest NAE-spełnialna wtedy i tylko wtedy, gdy w skonstruowanym grafie jest przekrój rozmiaru $n+2m$.

Jeżeli $\varphi$ jest spełnialna, to niech $S$ będzie zbiorem literałów, które są prawdziwe w wartościowaniu spełniającym $\varphi$. Przekrój pomiędzy zbiorem wierzchołków $S$ a resztą grafu ma dokładnie $n+2m$ krawędzi - $n$ krawędzi łączących $x$ z $\mathrm{\neg }x$ i po dwie krawędzi z każdego trójkąta.

Jeżeli jakiś przekrój $C$ w skonstruowanym grafie ma rozmiar $n+2m$, to zauważmy, że wyznacza on pewne wartościowanie zmiennych. Ponieważ w każdym przekroju mogą występować co najwyżej dwie krawędzie z jednego trójkąta, oznacza to, że przekrój $C$ ma dokładnie dwie krawędzie z każdego trójkąta i wszystkie krawędzie łączące przeciwne literały. Zatem przeciwne literały są w przeciwnych zbiorach podziału i możemy podać takie wartościowanie zmiennych, aby literały z jednego podzbioru wierzchołków były wartościowane pozytywnie, a te z drugiego negatywnie.

Ponieważ każdy z trójkątów ma dwie krawędzie w przekroju, zatem odpowiada to dokładnie temu, że każda z klauzul jest NAE-spełniona.

Problem komiwojażera TSP

Teraz przyjrzymy się innemu klasycznemu problemowi. Problem komiwojażera jest jednym z najlepiej zbadanych problemów $\mathrm{N}\mathrm{P}$-zupełnych ze względu na swoje praktyczne znaczenie. Warto sobie teraz przypomnieć dowód $\mathrm{N}\mathrm{P}$-zupełności jego decyzyjnej wersji. Użyjemy ponownie tych samych redukcji w analizie możliwości aproksymacji.

Optymalizacyjna wersja problemu TSP powstaje w naturalny sposób. Wejściem jest opis odległości pomiędzy $n$ miastami, rozwiązaniami dopuszczalnymi są cykle przechodzące przez wszystkie miasta, a funkcją celu, której wartość chcemy zminimalizować, jest sumaryczna długość cyklu.

Pierwsze smutne spostrzeżenie jest takie, że o ile $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, to nie ma możliwości skonstruowania dobrego algorytmu aproksymacyjnego. Fakt ten wyraża następujące twierdzenie:

Twierdzenie 5.1

O ile $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, to dla żadnego algorytmu aproksymacyjnego ${𝒜}$ nie istnieje funkcja obliczalna w czasie wielomianowym $\alpha$ taka, że ${𝒜}$ jest algorytmem $\alpha$-aproksymacyjnym dla problemu TSP.

Dowód

Dowód wynika bezpośrednio z dowodu $\mathrm{N}\mathrm{P}$-zupełności decyzyjnego problemu TSP. Przypomnijmy, że polegał on na redukcji problemu HAMILTON CYCLE. Wykorzystamy teraz tę redukcję do pokazania, że dowolny $\alpha$-aproksymacyjny algorytm pozwoliłby rozstrzygać problem cyklu Hamiltona, co przeczyłoby $\mathrm{P}\ne \mathrm{N}\mathrm{P}$.

Załóżmy, że ${𝒜}$ jest algorytmem $\alpha$-aproksymacyjnym dla problemu TSP. Chcąc zredukować problem cyklu Hamiltona dla grafu $G={V},{E}$ o $n$ wierzchołkach, tworzymy graf pełny $H$ na wierzchołkach $V$. Przypisujemy wagi krawędziom w następujący sposób:

• jeżeli krawędź $xy\in E$, to ustalamy jej wagę na $1$,
• w przeciwnym wypadku ustalamy jej wagę na $\alpha n\cdot n$.

Zauważmy, że koszt rozwiązania problemu TSP w grafie $H$ zależy od tego, czy w grafie $G$ był cykl Hamiltona:

• jeżeli graf $G$ jest grafem Hamiltonowskim, to koszt optymalnej trasy komiwojażera w $H$ wynosi $n$,
• w przeciwnym wypadku koszt optymalnej trasy jest większy od $\alpha n\cdot n$ (bo została użyta choć jedna krawędź $xy\notin E$).

Jeżeli teraz podamy graf $H$ na wejście algorytmu ${𝒜}$, to w pierwszym przypadku znajdzie on rozwiązanie o koszcie nie większym niż $\alpha n\cdot n$, a w drugim przypadku większym od tej wartości. Można zatem rozstrzygnąć, czy w grafie $G$ jest cykl Hamiltona, porównując koszt rozwiązania znalezionego przez ${𝒜}$ z $\alpha n\cdot n$.

Pokazany algorytm rozstrzyga $\mathrm{N}\mathrm{P}$-zupełny problem HAMILTON CYCLE i działa w czasie wielomianowym. Jest to sprzecznie z założeniem $\mathrm{P}\ne \mathrm{N}\mathrm{P}$.

Wersja metryczna

Warunek trójkąta.

Pokazaliśmy, że nie ma nadziei na efektywny algorytm dla ogólnego przypadku problemu komiwojażera. Poddamy teraz analizie naturalne zawężenie problemu i odkryjemy, że jest wtedy możliwa dobra aproksymacja. Zawężeniem problemu, o którym mowa, jest nałożenie dodatkowego wymagania na odległości podawane na wejściu. Żądamy, aby spełniały one warunek trójkąta. Dla każdych trzech miast $x,y,z$ musi zachodzić (rysunek Warunek trójkąta):

$d(x,y)\le d(x,z)+d(z,y)\text{.}$

Takie zawężenie problemu nazywa się metrycznym problemem komiwojażera i ma ono wiele praktycznych zastosowań. Nawet przy tych dodatkowych warunkach problem pozostaje $\mathrm{N}\mathrm{P}$-zupełny (zwykła redukcja problemu HAMILTON CYCLE tworzy instancję metrycznego problemu komiwojażera).

Zauważmy, że konstrukcja, która pokazywała, że ogólny problem komiwojażera nie może być dobrze aproksymowany, tworzyła wejścia, które zdecydowanie nie zachowywały warunku trójkąta. Daje to nadzieję na istnienie algorytmu aproksymacyjnego dla tego podproblemu.

Najpierw pokażemy algorytm $2$-aproksymacyjny, który konstruuje cykl komiwojażera w bardzo sprytny sposób:

Algorytm 5.2 [Algorytm drzewowy]

---

1. Znajdź minimalne drzewo rozpinające $T$ w grafie odległości.
2. Podwój krawędzie drzewa $T$, otrzymując graf $\mathbb{𝕋}$.
3. Znajdź cykl Eulera $\mathbb{ℂ}$ w grafie $\mathbb{𝕋}$.
4. Skonstruuj cykl $C$, przechodząc $\mathbb{ℂ}$ po kolei i dodając każdy wierzchołek, który nie został jeszcze dodany do $C$. (porównaj z rysunkiem Zamiana drzewa rozpinającego na cykl komiwojażera)

Zamiana drzewa rozpinającego na cykl komiwojażera.

Twierdzenie 5.3

Algorytm drzewowy jest algorytmem $2$-aproksymacyjnym.

Dowód

Dowód przeprowadzimy, porównując koszt struktur konstruowanych w kolejnych krokach algorytmu względem optymalnego rozwiązania problemu. Tak więc:

• suma wag krawędzi drzewa $T$ jest mniejsza lub równa kosztowi optymalnego rozwiązania problemu. Jest tak dlatego, gdyż usuwając dowolną krawędź z rozwiązania optymalnego, otrzymujemy drzewo (a raczej ścieżkę) rozpinające grafu. Tymczasem $T$ jest minimalnym drzewem rozpinającym. Mamy więc
• $\text{cost}(T)\le \text{opt}$,
• $\text{cost}(\mathbb{𝕋})=2\text{cost}(T)\le 2$,
• $\text{cost}(\mathbb{ℂ})=\text{cost}(\mathbb{𝕋})\le 2$,

musimy teraz pokazać, że konstruując $C$, nie pogorszymy oszacowania na koszt $\mathbb{ℂ}$. Tutaj właśnie skorzystamy z tego, że odległości zachowują warunek trójkąta. Sprawia to, że pomijając wierzchołki i dodając krawędź bezpośrednią pomiędzy końcami usuniętego fragmentu, możemy tylko zmniejszyć całkowity koszt rozwiązania. W związku z tym $\text{cost}(C)\le \text{cost}(\mathbb{ℂ})\le 2\text{opt}$.

Wyniki osiągane przez ten algorytm można poprawić i otrzymać algorytm $\frac{3}{2}$-aproksymacyjny. Szczegóły tego usprawnienia pozostawiamy na ćwiczenia.

Ćwiczenie 5.4 [Algorytm pre-order]

Poddaj analizie następujący algorytm dla metrycznego problemu komiwojażera:

Algorytm 5.5 [Algorytm pre-order]

---

1. Znajdź minimalne drzewo rozpinające $T$ w grafie odległości.
2. Ukorzeń drzewo $T$ i zwróć wierzchołki w kolejności pre-order.

Wskazówka

Porównaj rozwiązanie znajdowane przez algorytm z wynikiem rozwiązaniem poprzedniego algorytmu.

Rozwiązanie

Wystarczy zauważyć, że jeżeli zaczniemy skracanie cyklu Eulera od wierzchołka $x$, to jest to równoważne wypisaniu drzewa ukorzenionego w wierzchołku $x$ w porządku pre-order. W związku z tym znalezione rozwiązanie ma te same oszacowania co poprzednie. Jest to algorytm $2$-aproksymacyjny.

Ćwiczenie 5.6 [$\frac{3}{2}$-aproksymacja]

Możemy zmodyfikować algorytm tak, żeby osiągał znacznie lepsze oszacowanie aproksymacji. Zauważmy, że punktem, który wymaga poprawienia jest podwajanie drzewa rozpinającego. To podwojenie sprawia, że graf staje się grafem Eulerowskim. Osiągniemy teraz ten sam efekt mniejszym kosztem.

Algorytm 5.7 [Algorytm drzewowo-skojarzeniowy]

---

1. Znajdź minimalne drzewo rozpinające $T$ w grafie odległości.
2. Znajdź najtańsze skojarzenie o maksymalnej liczności $M$ w zbiorze wierzchołków o nieparzystym stopniu w $T$.
3. $\mathbb{𝕋}=T+M$.
4. Znajdź cykl Eulera $\mathbb{ℂ}$ w grafie $\mathbb{𝕋}$.
5. Skonstruuj cykl $C$ przechodząc $\mathbb{ℂ}$ po kolei i dodając każdy wierzchołek, który nie został jeszcze dodany do $C$.

Pokaż, że tak skonstruowany algorytm jest poprawnym $\frac{3}{2}$-aproksymacyjnym algorytmem rozwiązującym metryczny problem TSP.

Wskazówka

Uzasadnij, że w grafie $T+M$ jest ścieżka Eulera. Spróbuj oszacować koszt $M$. Zauważ, że dowolny cykl, a więc również rozwiązanie optymalne, można rozbić na dwa skojarzenia.

Rozwiązanie

Aby udowodnić poprawność algorytmu musimy pokazać, że graf $T+M$ jest Eulerowski. Wystarczy zauważyć, że w każdym drzewie jest parzysta liczba wierzchołków o nieparzystym stopniu. W związku z tym skojarzenie $M$ doda każdemu takiemu wierzchołkowi jedną krawędź i w powstałym grafie każdy wierzchołek będzie miał stopień parzysty.

Pokażemy, że sumaryczny koszt krawędzi w skojarzeniu spełnia nierówność $\text{cost}(M)<\frac{1}{2}\text{opt}$. Niech $W$ będzie zbiorem wierzchołków o nieparzystym stopniu w $T$. Niech $O_W$ oznacza cykl przechodzący przez wierzchołki $W$ powstały przez zawężenie cyklu optymalnego $O$ do wierzchołków $W$. Warunek trójkąta pozwala nam stwierdzić $\text{cost}(O_W)\le \text{cost}(O)=\text{opt}$.

Ponieważ wybór co drugiej krawędzi na cyklu definiuje skojarzenie o maksymalnej liczności, to cykl $O_W$ wyznacza dwa takie rozłączne skojarzenia na wierzchołkach $W$. Tańsze z nich ma koszt nie większy niż połowa $\text{cost}(O_W)$ i jest to koszt nie mniejszy od kosztu najtańszego skojarzenia $M$. W związku z tym:

$\text{cost}(M)\le \frac{1}{2}\text{cost}(O_W)\le \frac{1}{2}\text{opt}\text{.}$

Zatem sumaryczny koszt krawędzi grafu $T+M$ jest nie większy niż $\frac{3}{2}\text{opt}$ i algorytm osiąga stałą aproksymacji równą $\frac{3}{2}$.

Pakowanie BIN PACKING

Kolejnym istotnym i dzięki temu dobrze zbadanym problemem, którym się zajmiemy, jest optymalne pakowanie. Przypomnijmy sformułowanie problemu:

Problem [Pakowanie BIN PACKING]

Mając dany zbiór $n$ przedmiotów o wagach wymiernych $w_1,w_2,\dots ,w_n\in (0,1]$, należy znaleźć przyporządkowanie ich do jak najmniejszej liczby pojemników. Suma wag przedmiotów w jednym pojemniku nie może przekraczać $1$. Zadaniem optymalizacji jest oczywiście minimalizacja liczby użytych pojemników.

$2$-aproksymacja

Bardzo łatwo jest podać algorytm $2$-aproksymacyjny:

Algorytm 6.1 [Algorytm First-Fit]

---

(animacja Algorytm First-Fit)

1. W liście $B$ przechowuj częściowo wypełnione pojemniki. Na początku lista jest pusta.
2. Przeglądając przedmioty w kolejności, dodawaj je do pierwszego pojemnika na liście $B$, w którym jest jeszcze wystarczająco dużo "miejsca". Jeżeli nie można przedmiotu dodać do żadnego z pojemników, to dodaj nowy pojemnik do listy i włóż przedmiot właśnie do niego.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Algorytm First-Fit.

Twierdzenie 6.2

Algorytm First-Fit jest algorytmem $2$-aproksymacyjnym.

Dowód

Zauważmy, że po zakończeniu algorytmu co najwyżej jeden z pojemników jest wypełniony mniej niż w połowie. Załóżmy, że jest przeciwnie i dwa pojemniki $B_i,B_j,i<j$ są wypełnione mniej niż w połowie. Zatem wszystkie przedmioty znajdujące się w $B_j$ mogłyby zostać dodane do pojemnika $B_i$. Zatem algorytm First-Fit tak właśnie by postąpił i pojemnik $B_j$ w ogóle nie byłby potrzebny.

Skoro tak, to liczba pojemników użytych przez algorytm First-Fit $m$ spełnia nierówność:

$m\le 2\sum _{i=1}^n{w}_i\text{.}$

Dla każdego rozwiązania dopuszczalnego, a więc również optymalnego, ilość użytych pojemników $u$ spełnia nierówność:

$u\ge \sum _{i=1}^n{w}_i\text{,}$

gdyż suma wielkości przedmiotów w jednym pojemniku nie przekracza $1$.

Te dwie nierówności pozwalają stwierdzić, że First-Fit jest algorytmem $2$-aproksymacyjnym.

Teraz pokażemy, że niemożliwe jest osiągnięcie lepszej stałej aproksymacji niż $\frac{3}{2}$. Fakt ten wyraża następujące twierdzenie:

Twierdzenie 6.3

O ile $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, to dla żadnego algorytmu aproksymacyjnego ${𝒜}$ nie istnieje stała $a<\frac{3}{2}$ taka, że ${𝒜}$ jest algorytmem $a$-aproksymacyjnym.

Dowód

Dowód oparty jest o redukcję problemu PARTITION. Dla konkretnej instancji problemu PARTITION z elementami $a_1,a_2,\dots ,a_n$ i sumą wag $S=\sum _{i=1}^{n}s(a_i)$ konstruujemy instancję problemu BIN PACKING z wagami $\frac{2s(a_1)}{S},\frac{2s(a_2)}{S},\dots ,\frac{2s(a_n)}{S}$.

Jeżeli istnieje rozwiązanie problemu PARTITION, to w problemie pakowania wystarczy użyć $2$ pojemników. Każdy algorytm aproksymacyjny ${𝒜}$ ze stałą aproksymacji $a<\frac{3}{2}$ musiałby w takim wypadku znaleźć rozwiązanie używające $2$ pojemników i tym samym rozwiązać problem PARTITION.

Zauważmy jeszcze, że przeprowadzone rozumowanie dowodzi również $\mathrm{N}\mathrm{P}$-zupełności decyzyjnej wersji problemu BIN-PACKING.

Do problemu pakowania i jego aproksymacji powrócimy jeszcze w następnym rozdziale, aby przyjrzeć mu się z trochę innej perspektywy.

Ćwiczenie 6.4 [$\frac{5}{3}\text{opt}$ w algorytmie First-Fit]

Podaj przykład danych wejściowych, dla których algorytm First-Fit używa $\frac{5}{3}\text{opt}$ pojemników.

Wskazówka

Można skonstruować taki przykład, korzystając tylko z przedmiotów rozmiaru $\frac{1}{2}+ϵ$, $\frac{1}{3}+ϵ$ oraz $\frac{1}{7}+ϵ$, gdzie $ϵ=\frac{1}{1000}$.

Rozwiązanie

Zauważmy, że jeżeli podamy algorytmowi Firs-Fit następujący ciąg elementów:

$6\times (\frac{1}{7}+ϵ),6\times (\frac{1}{3}+ϵ),6\times (\frac{1}{2}+ϵ)\text{,}$

to użyje on $10$ pojemników. Jeden zostanie wypełniony przez przedmioty rozmiaru $\frac{1}{7}+ϵ$, trzy przez $\frac{1}{3}+ϵ$, a kolejne sześć przez $\frac{1}{2}+ϵ$.

Tymczasem rozwiązanie optymalne używa $6$ pojemników, umieszczając w nich po jednym z przedmiotów każdego rozmiaru.

Możemy te same dane zwielokrotnić. Podać po $12,18,\dots$ przedmiotów każdego rozmiaru. Otrzymamy w ten sposób całą rodzinę przykładów dla których rozwiązanie First-Fit jest $\frac{5}{3}$ razy gorsze od optymlanego.

Ćwiczenie 6.5 [Algorytm Next-Fit]

Rozważ następujący algorytm:

Algorytm 6.6 [Algorytm Next-Fit]

---

1. W liście $B$ przechowuj częściowo wypełnione pojemniki. Na początku lista jest pusta.
2. Przeglądając przedmioty w kolejności, dodawaj je do ostatniego pojemnika na liście $B$, jeżeli jest w nim jeszcze wystarczająco dużo "miejsca". Jeżeli nie można przedmiotu dodać do ostatniego pojemnika, to dodaj nowy pojemnik na koniec listy i włóż przedmiot właśnie do niego.

Pokaż, że jest to algorytm $2$-aproksymacyjny. Pokaż pesymistyczny przypadek dla tego algorytmu, w którym używa on $2\text{opt}-1$ pojemników.

Wskazówka

Zauważ, że suma wielkości przedmiotów w każdych dwóch kolejnych pojemnikach zawsze przekracza $1$.

Rozwiązanie

Pokażemy, że jeżeli algorytm użył $m$ pojemników, to suma wielkości przedmiotów $W=\sum _{i=1}^n{w}_i$ spełnia nierówność: $W>\lfloor \frac{m}{2}\rfloor \text{.}$

Dowód tej nierówności przeprowadzimy indukcyjnie ze względu na $m$. Dla $m=1,2$ dowód jest oczywisty. Dla $m>2$ możemy założyć, że $k$ przedmiotów zostało upakowanych w pierwszych $m-2$ pojemnikach, a pozostałe w ostatnich dwóch. Możemy wtedy rozbić $W$ na dwie części $W_1=\sum _{i=1}^k{w}_i$ i $W_2=\sum _{i=k+1}^n{w}_i$. Z założenia indukcyjnego mamy $W_1>\lfloor \frac{m-2}{2}\rfloor$ i $W_2>1$, co po zsumowaniu daje $W=W_1+W_2>\lfloor \frac{m}{2}\rfloor$. W związku z tym optymalne upakowanie musi użyć co najmniej $\lceil \frac{m}{2}\rceil$ pojemników.

Konstrukcja przypadku pesymistycznego przebiega w taki sposób, że na wejście algorytmu podajemy ciąg przedmiotów o następujących wielkościach:

$\frac{n+1}{2n},\frac{n+2}{2n},\frac{n-1}{2n},\frac{n+3}{2n},\frac{n-2}{2n},\dots ,\frac{n+(n-2)}{2n},\frac{n-(n-3)}{2n},\frac{n+(n-1)}{2n},\frac{n-(n-2)}{2n}$

Algorytm Next-Fit upakuje każdy z przedmiotów w osobnym pojemniku, gdyż suma każdych dwóch kolejnych wielkości przekracza $1$. Zatem użyje on $2n-3$ pojemników. Tymczasem rozwiązanie optymalne używa $n-1$ pojemników, łącząc przedmioty $\frac{n+a}{2n}$ i $\frac{n-a}{2n}$ w $n-2$ par i umieszczając przedmiot o wadze $\frac{n+(n-1)}{2n}$ w osobnym pojemniku.

Ćwiczenie 6.7 [Monotoniczność algorytmów]

O algorytmie aproksymacyjnym ${𝒜}$ dla problemu BIN PACKING powiemy, że jest monotoniczny, jeżeli liczba pojemników użytych przez ${𝒜}$ do upakowania dowolnego podciągu $a_{i_1},a_{i_2},\dots ,a_{i_k}(i_1<i_2<\dots <i_k)$ ciągu przedmiotów $a_1,a_2,\dots ,a_n$ jest nie większa niż liczba pojemników potrzebnych do upakowania całego ciągu.

Pokaż, że algorytm First-Fit nie jest monotoniczny, a algorytm Next-Fit jest.

Rozwiązanie

Przykładem ciągu i podciągu dla których First-Fit zachowuje się niemonotonicznie jest na przykład:

$\frac{3}{12},\underset{\_}{\frac{3}{12},\frac{7}{12},\frac{3}{12},\frac{7}{12},\frac{5}{12},\frac{3}{12},\frac{5}{12}}$

Gdzie podciąg został oznaczony podkreśleniem. Łatwo zauważyć, że First-Fit użyje $3$ pojemników do upakowania całego ciągu i $4$ pojemników do upakowania podciągu.

Pokażemy, że Next-Fit jest monotoniczny oraz że jeżeli dla jakiegoś podciągu używa tyle samo pojemników, co dla całego ciągu, to w ostatnim pojemniku pozostawia co najmniej tyle samo miejsca. Dowód poprowadzimy indukcyjnie ze względu na długość ciągu.

Dla ciągów jednoelementowych sprawa jest oczywista, a dodatkowe założenie o pozostawianiu co najmniej tyle samo miejsca w ostatnim pojemniku pozwala udowodnić krok indukcyjny.

Problem plecakowy KNAPSACK

Pokażemy teraz prosty algorytm aproksymacyjny dla problemu KNAPSACK. Wersja decyzyjna problemu została już przestawiona wcześniej. Przypomnijmy, że mając zbiór przedmiotów $A=a_1,\dots ,a_n$ o rozmiarach $s(a_i)$ i wartościach $v(a_i)$, chcemy wybrać ich podzbiór tak, żeby suma rozmiarów wybranych przedmiotów nie przekraczała zadanej wielkości $B$, jednocześnie maksymalizując sumę wartości.

Najprostsza próba konstrukcji rozwiązania przybliżającego optymalne polega na zastosowaniu algorytmu dla ciągłego problemu plecakowego do sytuacji dyskretnej. Oto algorytm:

Algorytm 7.1 [Algorytm zachłanny]

---

1. Posortuj przedmioty względem malejącej gęstości $\varrho (a_i)=\frac{v(a_i)}{s(a_i)}$.
2. Wybieraj przedmioty po kolei i dodawaj je do rozwiązania, jeżeli tylko jest jeszcze wystarczająco dużo miejsca w plecaku.

Nie jest trudno pokazać, że ten algorytm nie osiąga żadnej stałej aproksymacji. Dowód tego faktu pozostawiamy jako ćwiczenie.

Na szczęście da się poprawić wyniki osiągane przez ten algorytm, wprowadzając niewielką modyfikację:

Algorytm 7.2 [Zmodyfikowany algorytm zachłanny]

---

1. Oblicz rozwiązanie metodą zachłanną.
2. Skonstruuj rozwiązanie zawierające tylko jeden przedmiot - wybierz ten, który ma największą wartość wśród przedmiotów o rozmiarze nie większym niż $B$.
3. Wybierz lepsze z tych dwóch rozwiązań.

Twierdzenie 7.3

Zmodyfikowany algorytm zachłanny jest algorytmem $\frac{1}{2}$-aproksymacyjnym dla problemu plecakowego.

Dowód

Załóżmy, że wszystkie przedmioty mają rozmiar mniejszy lub równy $B$. Jeżeli są jakieś większe przedmioty, to i tak nie mają one znaczenia dla żadengo z rozwiązań dopuszczalnych.

Przyjmijmy, że przedmiot $b$ maksymalizuje wartość: ${\mathrm{\forall }}_{i\le n}v(b)\ge v(a_i)$, a przedmioty są już posortowane malejąco względem wartości gęstości ($\varrho (a_1)\ge \varrho (a_2)\ge \dots \ge \varrho (a_n)$).

Niech $k$ będzie numerem pierwszego przedmiotu, którego nie ma w rozwiązaniu znajdowanym przez algorytm zachłanny. Zauważmy, że $s(a_1)+s(a_2)+\dots +s(a_k)>B$. Gdyby było inaczej, to algorytm zachłanny wybrałby przedmiot $a_k$ do rozwiązania.

Ponieważ przedmioty są posortowane względem $\varrho$, to zachodzi także:

$v(a_1)+v(a_2)+\dots +v(a_k)>\text{opt}.$

Jest tak dlatego, że zarówno sumaryczny rozmiar przedmiotów $a_1,a_2,\dots ,a_k$ jest większy niż w rozwiązaniu optymalnym, jak i średnia gęstość tych przedmiotów jest nie mniejsza.

Zauważmy na koniec, że $vb>v{a}_k$. Możemy więc dokonać podstawienia w poprzednim równaniu otrzymując:

$v(a_1)+v(a_2)+\dots +v(a_{k-1})+v(b)>\text{opt}.$

Lewa strona jest teraz mniejsza od sumy obu rozwiązań rozważanych przez zmodyfikowany algorytm zachłanny. Ponieważ algorytm wybiera lepsze z nich, więc jego wartość musi być większa od $\frac{1}{2}\text{opt}$.

Do problemu plecakowego powrócimy jeszcze w następnym rozdziale, aby pokazać, że można osiągnąć znacznie lepszy wynik, niż tylko aproksymacja ze stałą. Problem plecakowy jest przykładem problemu, który można aproksymować praktycznie z dowolną dokładnością.

Ćwiczenie 7.4 [Algorytm zachłanny dla problemu KNAPSACK]

Pokaż, że zaprezentowany algorytm zachłanny nie jest algorytmem $a$-aproksymacyjnym dla żadnego $a$.

Wskazówka

Użyj małego przedmiotu o dużej gęstości do "zablokowania" droższego przedmiotu.

Rozwiązanie

Wystarczy przeanalizować zachowanie algorytmu na tej instancji problemu dla dowolnego $k$:

$\begin{array}{rlr}n& =& 2\text{,}\\ v(a_1)& =& 2\text{,}\\ s(a_1)& =& 1\text{,}\\ \varrho (a_1)& =& 2\text{,}\\ v(a_2)& =& k\text{,}\\ s(a_2)& =& k\text{,}\\ \varrho (a_2)& =& 1\text{,}\\ B& =& k\text{.}\\ \end{array}$

Nietrudno stwierdzić, że rozwiązaniem optymalnym dającym wynik $k$ jest wybranie drugiego przedmiotu. Algorytm zachłanny tymczasem wybierze przedmiot pierwszy, gdyż ma on większą gęstość. Osiągnie tym samym wynik równy $2$. Dobierając odpowiednio parametr $k>2a$, możemy pokazać, że nie jest to algorytm $a$-aproksymacyjny dla żadnego $a$.