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ć (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ć (nieznana funkcja „\texnormal”): {\displaystyle \texnormal{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 $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) = \begincases 0\quad (x,y) \notin R \\ 1\quad (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 „\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 2.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:

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 \llcorner{\frac{n}{n}}\lrcorner+\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 $\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 2.3 [Algorytm skojarzeniowy]

---

1. Znajdź dowolne skojarzenie maksymalne (w sensie inkluzji) $M$ w grafie $G$.
2. 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 $|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$, co dowodzi że jest to algorytm $2$-aproksymacyjny.

Ćwiczenie 2.5 [Pesymistyczny przypadek dla algorytmu skojarzeniowego]

{{{3}}}

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

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

warunek trójkąta - ZO-7.4

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

zamiana drzewa rozpinającego na cykl komiwojażera - ZO-7.5

Twierdzenie 4.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 \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 4.4 [Algorytm pre-order]

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

Algorytm 4.5 [Algorytm pre-order]

---

 {{{3}}}

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

{{{3}}}