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

Wprowadzenie

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 2.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ć (błąd składni): {\displaystyle \textnormal{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 2.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ć (błąd składni): {\displaystyle \textnormal{opt}_\Pi}{I}} i nazywamy optimum. Często będziemy używać skróconej notacji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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ć (błąd składni): {\displaystyle \textnormal{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 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 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 $a\in {\mathbb{ℝ}}^{+}$, taka że:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \geq 1 \wedge \forall_{I \in D_\Pi} \textnormal{obj}_\Pi(I,\func{\mathcal{A}}(I)) \leq a \cdot \textnormal{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ć (błąd składni): {\displaystyle a \leq 1 \wedge \forall_{I \in D_\Pi} \textnormal{obj}_\Pi(I,\func{\mathcal{A}}(I)) \geq a \cdot \textnormal{opt}_\Pi(I). }

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:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \forall_{n \in \mathbb N} \func{\alpha}(n) \geq 1 \wedge \forall_{I\in D_\Pi} \textnormal{obj}_\Pi(I,\func{\mathcal{A}}(I)) \leq \func{\alpha|I|} \cdot \textnormal{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 (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 $|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ć (błąd składni): {\displaystyle \textnormal{obj}_{\Pi_L}(x,y) = \begin{cases} 0\quad (x,y) \notin R \\ 1\quad (x,y) \in R \end{cases}. }

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 „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} , 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ć (błąd składni): {\displaystyle \textnormal{opt}_{\Pi_L}(x) = 1} , a w przeciwnym wypadku Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 „\func”): {\displaystyle (x,\func{\mathcal{A}}(x)) \in R} , bo w przeciwnym wypadku Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{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 „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} .

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:

<flash>file=ZO-7-1.swf|width=300|height=300</flash>

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

<flashwrap>file=ZO-7-2.swf|size=small</flashwrap> <div.thumbcaption>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|,$

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]

{{{3}}}

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

{{{3}}}

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 Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle G=\braq{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 przekrój dokonuj takiego przesunięcia.

Twierdzenie 4.3

Algorytm zachłanny i poszukujacy 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}$

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 zwiekszył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|$

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

{{{3}}}

Problem komiwojażera - TSP

Teraz przyjrzymy się innemu klasycznemu problemowi - problemowi komiwojażera. Jest to jeden z najlepiej zbadanych problemów Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełnych ze względu na swoje praktyczne znaczenie. Warto sobie teraz przypomnieć dowód Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} , to nie ma możliwości skonstruowania dobrego algorytmu aproksymacyjnego. Fakt ten wyraża następujące twierdzenie:

Twierdzenie 5.1

O ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} , 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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} .

Załóżmy, że ${𝒜}$ jest algorytmem $\alpha$-aproksymacyjnym dla problemu TSP. Chcąc zredukować problem cyklu Hamiltona dla grafu Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle G=\braq{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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\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ż Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\alpha}{n} \cdot n} .

Pokazany algorytm rozstrzyga Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -zupełny problem HAMILTON CYCLE i działa w czasie wielomianowym. Jest to sprzecznie z założeniem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} .

Wersja metryczna

<flash>file=ZO-7-4.swf|width=300|height=150</flash>

<div.thumbcaption>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):

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{d}(x,y) \leq \func{d}(x,z) + \func{d}(z,y) }

Takie zawężenie problemu nazywa się metrycznym problemem komiwojażera i ma ono wiele praktycznych zastosowań. Nawet przy tych dodatkowych warunkach problem pozostaje Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -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)

<flash>file=ZO-7-5.swf|width=300|height=300</flash>

<div.thumbcaption>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
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(T) \leq \textnormal opt} ,
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}({\mathbb{T}}) = 2 \textnormal{cost}(T) \leq 2 \opt} ,
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}({\mathbb{C}}) = \textnormal{cost}({\mathbb{T}}) \leq 2 \opt} ,

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(C) \leq \textnormal{cost}({\mathbb{C}}) \leq 2 \textnormal{opt}} .

Wyniki osiągane przez ten algorytm można poprawić i dostać 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ść Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(M) < \frac{1}{2} \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ć Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(O_W) \leq \textnormal{cost}(O) = \textnormal 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(O_W)} i jest to koszt nie mniejszy od kosztu najtańszego skojarzenia $M$. W związku z tym:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{cost}(M) \leq \frac{1}{2} \textnormal{cost}(O_W) \leq \frac{1}{2} \textnormal opt }

Zatem sumaryczny koszt krawędzi grafu $T+M$ jest nie większy niż Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{3}{2} \textnormal 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.

<flashwrap>file=ZO-7-6.swf|size=small</flashwrap>

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle u \geq \sum_{i=1}^{n}w_i\textnormal{,} }

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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}\neq\cc{NP}} , 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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle S=\sum_{i=1}^{n}\func{s}(a_i)} konstruujemy instancję problemu BIN PACKING z wagami Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \frac{2 \func{s}(a_1)}{S},\frac{2 \func{s}(a_2)}{S},\ldots,\frac{2 \func{s}(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ż Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} -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 [Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{5}{3} \textnormal opt} w algorytmie First-Fit]

{{{3}}}

Ć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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2 \textnormal 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$

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 następujący sposób, że na wejście algorytmu podajemy ciąg przedmiotów o następujących wielkościach:

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \frac{n+1}{2n}, \frac{n+2}{2n}, \frac{n-1}{2n}, \frac{n+3}{2n}, \frac{n-2}{2n}, \ldots, \frac{n+\braq(n-2)}{2n}, \frac{n-\braq(n-3)}{2n}, \frac{n+\braq(n-1)}{2n}, \frac{n-\braq(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 Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \frac{n+\braq(n-1)}{2n}} w osobnym pojemniku.

Ćwiczenie 6.7 [Monotoniczność algorytmów]

{{{3}}}

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 Parser nie mógł rozpoznać (nieznana funkcja „\set”): {\displaystyle A=\set{a_1,\ldots,a_n}} o rozmiarach Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{s}(a_i)} i wartościach Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\varrho}(a_i) = \frac{\func{v}(a_i)}{\func{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ść: Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \forall_{i \leq n}\func{v}(b) \geq \func{v}(a_i)} , a przedmioty są już posortowane malejąco względem wartości gęstości (Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{\varrho}(a_1) \geq \func{\varrho}(a_2) \geq \ldots \geq \func{\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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{s}(a_1) + \func{s}(a_2) + \ldots + \func{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:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{v}(a_1) + \func{v}(a_2) + \ldots + \func{v}(a_k) > \textnormal 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 Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{v}{b} > \func{v}{a_k}} . Możemy więc dokonać podstawienia w poprzednim równaniu otrzymując:

Parser nie mógł rozpoznać (nieznana funkcja „\func”): {\displaystyle \func{v}(a_1) + \func{v}(a_2) + \ldots + \func{v}(a_{k-1}) + \func{v}(b) > \textnormal 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{1}{2} \textnormal 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]

{{{3}}}