|
|
| Linia 1: |
Linia 1: |
| {mwart}
| |
|
| |
|
| {prelude}
| |
|
| |
| ==Wprowadzenie==
| |
|
| |
| Na poprzednim wykładzie zajmowaliśmy się algorytmami
| |
| aproksymacyjnymi dla przykładowych trudnych problemów
| |
| optymalizacyjnych. Dla większości z tych algorytmów udawało nam się
| |
| podać gwarancję dokładności za pomocą stałego współczynnika
| |
| efektywności przybliżenia.
| |
|
| |
| W tym module postawimy sobie znacznie ambitniejsze zadanie -
| |
| będziemy szukać algorytmów, którym na wejściu ustala się
| |
| dopuszczalny błąd przybliżenia rozwiązania optymalnego. Pokażemy
| |
| problemy, dla których jest możliwa taka "dowolnie dokładna"
| |
| aproksymacja.
| |
|
| |
| W drugiej części poznamy klasę <math>\displaystyle \cc{MAXSNP}</math> - jest to bardzo szeroka i interesująca klasa problemów optymalizacyjnych, a pytanie o to, czy należące do niej problemy mogą być dowolnie dobrze aproksymowane było bardzo istotnym zagadnieniem teorii algorytmów aproksymacyjnych. Odpowiedź na to pytanie poznamy dopiero w następnym module.
| |
|
| |
| ==Schematy aproksymacji==
| |
|
| |
| Żeby wyrazić te nowe oczekiwania potrzebujemy nowych notacji:
| |
|
| |
| {{definicja|||
| |
| Mówimy, że algorytm <math>\displaystyle \mathcal{A}</math> jest {schematem aproksymacji} dla problemu <math>\displaystyle \cc{NP}</math>-optymalizacyjnego <math>\displaystyle \Pi</math>, jeżeli dla wejścia <math>\displaystyle \braq{I,\epsilon}</math>, gdzie <math>\displaystyle I</math> jest instancją problemu <math>\displaystyle \Pi</math>, a <math>\displaystyle \epsilon > 0</math> opisuje dopuszczalny błąd, znajduje rozwiązanie takie, że:
| |
| * <math>\displaystyle \func{\obj_\Pi}{I,{\func{\mathcal{A}}{I,\epsilon}}} \leq \braq{1 + \epsilon} \func{\opt_\Pi}{I}</math> dla problemu minimalizacji.
| |
| * <math>\displaystyle \func{\obj_\Pi}{I,{\func{\mathcal{A}}{I,\epsilon}}} \geq \braq{1 - \epsilon} \func{\opt_\Pi}{I}</math> dla problemu maksymalizacji.
| |
|
| |
| }}
| |
|
| |
| {{definicja|||
| |
| Jeśli dla dowolnego <math>\displaystyle \epsilon > 0</math> czas działania <math>\displaystyle \mathcal{A}</math> na wejściu <math>\displaystyle \braq{I,\epsilon}</math> jest wielomianowy względem <math>\displaystyle \size{I}</math>, to <math>\displaystyle \mathcal{A}</math> jest {wielomianowym schematem aproksymacji}. Będziemy używać skróconej notacji PTAS (od ''polynomial time approximation scheme'') dla oznaczenia tego faktu.
| |
| }}
| |
|
| |
| Zauważmy, że w tej definicji wymagamy wielomianowego czasu działania
| |
| tylko względem rozmiaru instancji przy ustalonym dopuszczalnym
| |
| błędzie. Oznacza to, że czas działania może być nawet wykładniczy
| |
| względem wartości parametru <math>\displaystyle \epsilon</math>. Nie jest to sytuacja
| |
| komfortowa. Możemy w związku z tym wzmocnić wymagania postawione dla
| |
| algorytmu.
| |
|
| |
| {{definicja|||
| |
| Jeżeli czas działania algorytmu <math>\displaystyle \mathcal{A}</math> jest wielomianowy względem <math>\displaystyle \size{I}</math>
| |
| oraz wartości <math>\displaystyle \frac{1}{\epsilon}</math>, to <math>\displaystyle \mathcal{A}</math> jest
| |
| {w pełni wielomianowym schematem aproksymacji}.
| |
| Omawiając takie algorytmy będziemy używać notacji FPTAS (''fully
| |
| polynomial time approximation scheme'').
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| FPTAS dla problemów silnie <math>\displaystyle \cc{NP}</math>-zupełnych.
| |
|
| |
| Wykaż, że o ile <math>\displaystyle \pneqnp</math>, i <math>\displaystyle \Pi</math> jest silnie <math>\displaystyle \cc{NP}</math>-zupełnym
| |
| problemem optymalizacyjnym takim, że funkcja celu <math>\displaystyle \obj_\Pi</math>
| |
| przyjmuje wartości całkowite i ograniczone wielomianowo od rozmiaru
| |
| instancji wejściowej oraz jej największej liczby, to nie istnieje
| |
| algorytm FPTAS dla <math>\displaystyle \Pi</math>.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wykorzystaj ograniczenie na wartości funkcji celu do zdefiniowania odpowiedniego
| |
| progu dopuszczalnego błędu w algorytmie FPTAS. Otrzymasz algorytm pseudowielomianowy
| |
| dla silnie <math>\displaystyle \cc{NP}</math>-zupełnej decyzyjnej wersji problemu <math>\displaystyle \Pi</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Niech <math>\displaystyle \Pi</math> będzie problemem maksymalizacji z funkcją celu
| |
| <math>\displaystyle \obj_\Pi</math> (dla problemu minimalizacji dowód przebiega
| |
| analogicznie). Załóżmy, że jej wartości są całkowite dodatnie oraz
| |
| dla każdej instancji <math>\displaystyle I</math>, <math>\displaystyle \obj_\Pi(I) < p(|I|,NUM(I))</math>, gdzie <math>\displaystyle p</math>
| |
| jest pewnym wielomianem dwóch zmiennych, a <math>\displaystyle NUM(I)</math> jest skojarzoną
| |
| z problemem funkcją określającą wartość największej liczby
| |
| występującej w instancji. Załóżmy, że <math>\displaystyle A</math> jest FPTAS dla <math>\displaystyle \Pi</math>.
| |
| Skonstruujemy algorytm pseudowielomianowy dla <math>\displaystyle \Pi</math>.
| |
|
| |
| Na wejściu dana jest instancja <math>\displaystyle I</math>. Algorytm składa sie z dwóch
| |
| kroków:
| |
|
| |
| 1. oblicz <math>\displaystyle \delta = 1/p(|I|,NUM(I))</math>
| |
|
| |
| 2. zastosuj <math>\displaystyle A</math> dla instancji <math>\displaystyle I</math> i dokładności <math>\displaystyle \delta</math>, obliczone
| |
| rozwiązanie dopuszczalne <math>\displaystyle S</math> wypisz na wyjście.
| |
|
| |
| Ponieważ <math>\displaystyle \Pi</math> jest maksymalizacyjny, więc <math>\displaystyle \obj_\Pi(I,S)\geq
| |
| (1-\delta)</math>. Zatem <math>\displaystyle opt(I)-\obj_\Pi(I,S) \leq \delta \, opt(I) < 1</math>.
| |
|
| |
| Z tego, że wartości funkcji celu są całkowitoliczbowe, wynika
| |
| <math>\displaystyle \obj_\Pi(I,S)=opt(I)</math>, a zatem nasz algorytm znajduje rozwiązania
| |
| optymalne. Zgodnie z definicja FPTAS, algorytm działa w czasie
| |
| wielomianowym od <math>\displaystyle |I|</math> oraz <math>\displaystyle 1/\delta</math>, jest to więc algorytm
| |
| pseudowielomianowy dla <math>\displaystyle \Pi</math>.
| |
|
| |
| Z analizowanych na poprzednim wykładzie własności silnej
| |
| NP-zupełności wynika, że musi to być algorytm wielomianowy dla
| |
| <math>\displaystyle \Pi</math>, co oczywiście jest sprzeczne z założeniem <math>\displaystyle \pneqnp</math>.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==Schemat aproksymacji dla problemu KNAPSACK==
| |
|
| |
| Pokazaliśmy, że nie warto szukać algorytmów FPTAS dla problemów silnie <math>\displaystyle \cc{NP}</math>-zupełnych. Rozpoczniemy w związku z tym dalsze poszukiwania schematów aproksymacyjnych od przyjrzenia się raz jeszcze problemowi plecakowemu. Wiemy, że nie jest to problem silnie <math>\displaystyle \cc{NP}</math>-zupełny i znamy dla niego algorytm pseudowielomianowy. Bardzo często istnienie algorytmu pseudowielomianowego można wykorzystać przy konstrukcjii schematów aproksymacji. Zobaczymy teraz klasyczną konstrukcję opartą o ten pomysł.
| |
|
| |
| Pokażemy teraz algorytm pseudowielomianowemu rozwiązujący problem KNAPSACK. Poznaliśmy już jeden taki alorytm, ale tamten nie nadaje się do konstrukcji schematu aproksymacji.
| |
|
| |
| Algorytm pseudowielomianowy dla problemu plecakowego.
| |
| # Oblicz <math>\displaystyle V = \max_{i=1,2,\ldots,n} \func{v}{a_i}</math>.
| |
| # Oblicz <math>\displaystyle W_{i,u}</math> określone dla <math>\displaystyle 0 \leq i \leq n</math> i <math>\displaystyle 0 \leq u \leq nV</math> jako "minimalny sumaryczny rozmiar podzbioru przedmiotów <math>\displaystyle S \subseteq{a_1,a_2,\ldots,a_i}</math> taki że sumaryczna wartość tych przedmiotów wynosi dokładnie <math>\displaystyle u</math>". Obliczenia można dokonać metodą dynamiczną korzystając z następujących własności rekurencyjnych:
| |
|
| |
| <center><math>\displaystyle \aligned W_{0,u} &= \infty \\
| |
| W_{i+1,u} &= \func{\min}{W_{i,u},W_{i,u-\func{v}{a_{i+1}}}+\func{w}{a_{i+1}}}
| |
| \endaligned</math></center>
| |
| # Odczytaj rozwiązanie z wartości <math>\displaystyle W</math>.
| |
|
| |
| Algorytm ten można zakodować tak, aby znajdował optymalne rozwiązanie w czasie <math>\displaystyle \notO{n^2V}</math>. Szczegóły implementacji pozostawiamy jako ćwiczenie.
| |
|
| |
| Zauważmy, że gdyby wartości przedmiotów były ograniczone przez wielomianową funkcję <math>\displaystyle n</math>, to skonstruowany algorytm byłby wielomianowy. To jest podstawą schematu aproksymacji, który będzie zaokrąglał wartości przedmiotów tak, aby były one wielomianowe względem <math>\displaystyle n</math> i <math>\displaystyle \frac{1}{\epsilon}</math>. Oto algorytm:
| |
|
| |
| Algorytm zaokrągleniowy.
| |
| # Oblicz <math>\displaystyle K = \frac{\epsilon V}{n}</math>.
| |
| # Dla każdego przedmiotu oblicz <math>\displaystyle \func{v'}{a_i} = \floor{\frac{\func{v}{a_i}}{K}}</math>.
| |
| # Używając algorytmu pseudowielomianowego rozwiąż problem z wartościami <math>\displaystyle v'</math>.
| |
|
| |
| {{twierdzenie|||
| |
| Algorytm zaokrągleniowy jest FPTAS dla problemu plecakowego.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Musimy pokazać, że dla zbioru <math>\displaystyle S</math> znajdowanego przez algorytm zachodzi:
| |
|
| |
| <center><math>\displaystyle \sum_{i \in S} \func{v}{a_i} \geq \braq{1 - \epsilon} \opt
| |
| </math></center>
| |
|
| |
| Niech <math>\displaystyle O</math> będzie rozwiązaniem optymalnym. Możemy wtedy zapisać ciąg nierówności:
| |
|
| |
| <center><math>\displaystyle \sum_{i \in S} \func{v}{a_i} \geq \sum_{i \in S} \floor{\frac{\func{v}{a_i}}{K}} K \geq \sum_{i \in O} \floor{\frac{\func{v}{a_i}}{K}} K \geq \sum_{i \in O} \braq{\func{v}{a_i} - K} \geq \sum_{i \in O} \func{v}{a_i} - nK
| |
| </math></center>
| |
|
| |
| Korzystamy po kolei z własności zaokrąglenia, optymalności rozwiązania <math>\displaystyle S</math> przy wartościach wydzielonych przez <math>\displaystyle K</math>, własności zaokrąglenia i tego, że <math>\displaystyle \size{S} \leq n</math>.
| |
|
| |
| Udowodniliśmy, że wartość rozwiązania znajdowanego przez algorytm jest nie mniejsze niż <math>\displaystyle \opt - nK = \opt - \epsilon V \geq \braq{1-\epsilon} \opt</math>. Jest to zatem schemat aproksymacyjny. Musimy jeszcze oszacować czas działania algorytmu. Wynosi on <math>\displaystyle \notO{n^2\floor{\frac{V}{K}}} = \notO{n^2\floor{\frac{n}{\epsilon}}}</math>, a więc jest wielomianowy zarówno względem <math>\displaystyle n</math>, jak i <math>\displaystyle \frac{1}{\epsilon}</math>.
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Algorytm pseudowielomianowy.
| |
|
| |
| Doprecyzuj implementację algorytmu pseudowielomianowego dla problemu plecakowego. Jak odzyskać wybór przedmiotów z tablicy <math>\displaystyle W_{i,u}</math>?
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Użyj standardowej konstrukcji algorytmu dynamicznego w oparciu o
| |
| podane własności rekurencyjne.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Następujący program wypełni tablicę <math>\displaystyle W_{i,u}</math>:
| |
|
| |
| '''for''' <math>\displaystyle u=0,1,\ldots,V\displaystyle W_{0,u} = \infty</math>
| |
| '''endfor'''
| |
| '''for''' <math>\displaystyle i=1,2,\ldots,n</math>
| |
| '''for''' <math>\displaystyle u=0,1,\ldots,nV\displaystyle W_{i,u} = W_{i-1,u}</math>
| |
| '''if''' <math>\displaystyle u-\func{v}{a_i} \geq 0</math> '''and''' <math>\displaystyle W_{i-1,u-\func{v}{a_i}}+\func{w}{a_i} < W_{i,u}\displaystyle W_{i,u} = W_{i-1,u-\func{v}{a_i}}+\func{w}{a_{i}}</math>
| |
| '''endif'''
| |
| '''endfor'''
| |
| '''endfor'''
| |
|
| |
| A ten pozowoli odszukać rozwiązanie optymalne:
| |
|
| |
| <math>\displaystyle S=\emptyset\displaystyle o=0</math>
| |
| '''for''' <math>\displaystyle u=0,1,\ldots,nV</math>
| |
| '''if''' <math>\displaystyle W_{n,u} \leq B\displaystyle o=u</math>
| |
| '''endif'''
| |
| '''endfor'''
| |
| <math>\displaystyle i=n</math>
| |
| '''while''' <math>\displaystyle o > 0</math>
| |
| '''if''' <math>\displaystyle W_{i,o} = W_{i-1,o}\displaystyle i = i-1</math>
| |
| '''else'''
| |
| <math>\displaystyle S = S \cup \{i\}\displaystyle o = o - \func{v}{a_i}\displaystyle i = i-1</math>
| |
| '''endif'''
| |
| '''endwhile'''
| |
| '''return''' <math>\displaystyle S</math>
| |
|
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==Asymptotyczny PTAS dla BIN PACKING==
| |
|
| |
| Pokazaliśmy, że problem plecakowy może być aproksymowalny z dowolną
| |
| dokładnością w czasie wielomianowo zależnym od wielkości danych i
| |
| dopuszczalnego błędu. Dla problemuu pakowania nie możemy się
| |
| spodziewać równie dobrych wyników. Jest to problem silnie
| |
| <math>\displaystyle \cc{NP}</math>-zupełny i o ile <math>\displaystyle \pneqnp</math>, to nie może istnieć FPTAS.
| |
| Pokazaliśmy również, że nie ma algorytmu osiągającego stałą
| |
| aproksymacji mniejszą od <math>\displaystyle \frac{3}{2}</math>. Dowód opierał się o fakt, że
| |
| o ile <math>\displaystyle \pneqnp</math>, to nie da się efektywnie sprawdzać, czy da się
| |
| przedmioty upakować do dwóch pojemników.
| |
|
| |
| Instancje, które zabraniały aproksymacji lepszej niż <math>\displaystyle \frac{3}{2}</math>
| |
| miały ograniczoną wartość optimum. Skonstruujemy teraz asymptotyczny
| |
| PTAS dla problemu pakowania, który może osiągać dowolnie dobrą
| |
| aproksymację ale dla odpowiednio dużych wartości optimum.
| |
|
| |
| Precyzując, podamy rodzinę algorytmów <math>\displaystyle \mathcal{A}_\epsilon</math> dla <math>\displaystyle 0 < \epsilon \leq \frac{1}{2}</math> działających w czasie wielomianowym od liczby przedmiotów i znajdujących rozwiązanie używające co najwyżej <math>\displaystyle \braq{1 + 2\epsilon}\opt + 1</math> pojemników.
| |
|
| |
| Zanim będziemy mogli przedstawić algorytmy <math>\displaystyle \mathcal{A}_\epsilon</math> musimy pokazać dwa pomocnicze lematy, które pokazują rozwiązania dla pewnych uproszczonych instancji problemu.
| |
|
| |
| {{lemat|||
| |
| Dla dowolnego <math>\displaystyle \epsilon > 0</math> oraz liczby całkowitej <math>\displaystyle K</math> istnieje algorytm wielomianowy rozwiązujący problem pakowania dla instancji, w których występują przedmioty o co najwyżej <math>\displaystyle K</math> różnych rozmiarach, z których każdy jest nie mniejszy niż <math>\displaystyle \epsilon</math>.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Liczba przedmiotów w jednym pojemniku jest ograniczona przez <math>\displaystyle M=\floor{\frac{1}{\epsilon}}</math>. Suma rozmiarów większej liczby przedmiotów musi przekraczać <math>\displaystyle 1</math>, gdyż każdy z nich ma rozmiar nie mniejszy niż <math>\displaystyle \epsilon</math>.
| |
|
| |
| Liczba możliwych zawartości jednego pojemnika jest zatem ograniczona przez <math>\displaystyle R=\binom{M+K}{M}</math>. Ograniczenie to uzyskujemy, gdyż jest to liczba <math>\displaystyle M</math>-elementowych multipodzbiorów zbioru <math>\displaystyle K</math>-elementowego. Zauważmy, że liczb <math>\displaystyle R</math> jest stałą zależną tylko od <math>\displaystyle K</math> i <math>\displaystyle \epsilon</math>.
| |
|
| |
| Liczba pojemników w rozwiązaniu jest ograniczona w oczywisty sposób przez <math>\displaystyle n</math>. Zatem liczba możliwych rozwiązań dopuszczalnych jest ograniczona przez <math>\displaystyle P=\binom{n+R}{R}</math>. Tym razem jest to liczba <math>\displaystyle n</math>-elementowych multipodzbiorów zbioru <math>\displaystyle R</math>-elementowego.
| |
|
| |
| Liczba <math>\displaystyle P</math> wyraża się wielomianem względem <math>\displaystyle n</math>. Możemy w związku z tym w czasie wielomianowy przejrzeć wszystkie rozwiązania dopuszczalne i wybrać optymalne.
| |
|
| |
| {{uwaga|||
| |
| Niestety czas tego algorytmu jest wielomianem stopnia <math>\displaystyle R</math>. Jest to bardzo wysoki stopień i przez to algorytm ten nie może być traktowany jako praktyczne rozwiązanie problemu.
| |
| }}
| |
|
| |
| }}
| |
|
| |
| {{lemat|||
| |
| Dla dowolnego <math>\displaystyle \epsilon > 0</math> istnieje wielomianowy algorytm <math>\displaystyle \braq{1+\epsilon}</math>-aproksymacyjny dla problemu pakowania dla instancji, w których występują przedmioty o rozmiarach nie mniejszych niż <math>\displaystyle \epsilon</math>.
| |
| }}
| |
|
| |
| {{dowod|||
| |
|
| |
| Algorytm dzielący na grupy.
| |
| # Oblicz <math>\displaystyle K=\ceil{\frac{1}{\epsilon^2}}</math>.
| |
| # Posortuj przedmioty względem rosnącego rozmiaru i podziel posortowany ciąg na <math>\displaystyle K</math> grup tak, aby w każdej grupie było co najwyżej <math>\displaystyle Q=\floor{n\epsilon^2}</math> przedmiotów.
| |
| # Zamień rozmiar każdego z przedmiotów na rozmiar największego przedmiotu w tej samej grupie.
| |
| # Użyj algorytmu z poprzedniego lematu działającego na przedmiotach o <math>\displaystyle K</math> różnych rozmiarach nie mniejszych niż <math>\displaystyle \epsilon</math>.
| |
|
| |
| Niech <math>\displaystyle I</math> będzie instancją podaną na wejściu algorytmu. Niech <math>\displaystyle I^*</math> będzie instancją otrzymaną w trzecim kroku algorytmu, a <math>\displaystyle I_*</math> instancją, którą otrzymalibyśmy zamieniając rozmiar każdego z przedmiotów na rozmiar najmniejszego w tej samej grupie.
| |
|
| |
| Wynikiem działania algorytmu jest rozwiązanie optymalne dla instancji <math>\displaystyle I^*</math>. Musimy wykazać, że <math>\displaystyle \func{\opt}{I^*} \leq \braq{1+\epsilon} \func{\opt}{I}</math>. Łatwo jest uzasadnić oszacowanie <math>\displaystyle \func{\opt}{I_*} \leq \func{\opt}{I}</math>.
| |
|
| |
| Możemy teraz zauważyć, że każde rozwiązanie instancjii <math>\displaystyle I_*</math> wyznacza pewne rozwiązanie dla <math>\displaystyle I^*</math>. Ponieważ najmniejszy przedmiot z <math>\displaystyle i+1</math> grupy przedmiotów jest większy lub równy największemu przedmiotowi z grupy <math>\displaystyle i</math>. Zatem rozwiązanie instancji <math>\displaystyle I_*</math> pozwala upakować wszystkie przedmioty z instancji <math>\displaystyle I^*</math> oprócz ostatniej grupy. Więc nawet jeżeli każdy z tych przedmiotów zostałby upakowany do osobnego pojemnika, otrzymujemy ograniczenie:
| |
|
| |
| <center><math>\displaystyle \func{\opt}{I^*} \leq \func{\opt}{I_*} + Q \leq \func{\opt}{I} + Q \leq \func{\opt}{I} + \floor{n\epsilon^2} \leq \braq{1+\epsilon}\func{\opt}{I}
| |
| </math></center>
| |
|
| |
| Ostatnia nierówność wynika z tego, że <math>\displaystyle n\epsilon \leq \func{\opt}{I}</math>. Pokazaliśmy zatem, że algorytm jest <math>\displaystyle \braq{1+\epsilon}</math>-aproksymacyjny.
| |
| }}
| |
|
| |
| Mając w ręku te dwa pomocnicze lematy możemy już pokazać algorytm <math>\displaystyle \mathcal{A}_\epsilon</math>.
| |
|
| |
| Algorytm <math>\displaystyle \mathcal{A}_\epsilon</math>.
| |
| # Stwórz instancję <math>\displaystyle I_{\geq\epsilon}</math> usuwając wszystkie przedmioty o rozmiarze mniejszym od <math>\displaystyle \epsilon</math> z <math>\displaystyle I</math>.
| |
| # Oblicz instancję <math>\displaystyle I_{\geq\epsilon}^*</math> i znajdź dla niej optymalne upakowanie korzystając z algorytmu przeglądającego wszystkie rozwiązania dopuszczalne.
| |
| # Dopakuj przedmioty o rozmiarze mniejszym od <math>\displaystyle \epsilon</math> za pomocą algorytmu First-Fit otrzymując rozwiązanie dla instancji wejściowej <math>\displaystyle I</math>.
| |
|
| |
| {{twierdzenie|||
| |
| Dla dowolnego <math>\displaystyle 0 < \epsilon \leq \frac{1}{2}</math> algorytm <math>\displaystyle \mathcal{A}_\epsilon</math> znajduje upakowanie przedmiotów instancji <math>\displaystyle I</math> w co najwyżej <math>\displaystyle \braq{1 + 2\epsilon}\func{\opt}{I} + 1</math> pojemnikach.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Jeżeli w ostatnim kroku algorytmu nie zostały utworzone żadne nowe pojemniki, to rozwiązanie znalezione dla <math>\displaystyle I_{\geq\epsilon}</math> używa <math>\displaystyle \braq{1+\epsilon}\func{\opt}{I_{\geq\epsilon}}</math> pojemników, a więc spełnia warunki twierdzenia.
| |
|
| |
| Jeżeli natomiast zostały utworzone nowe pojemniki, to zauważmy, że tylko w jednym ze wszystkich pojemników mogą znajdować się przedmioty o sumarycznym rozmiarze mniejszym niż <math>\displaystyle 1 - \epsilon</math>. Zatem jeżeli oznaczymy przez <math>\displaystyle M</math> liczbę wszystkich użytych pojemników, to sumarczyny rozmiar wszystkich przedmiotów (a więc i optimum) możemy ograniczyć z dołu przez <math>\displaystyle \braq{M-1}\braq{1-\epsilon}</math>. W związku z tym możemy napisać:
| |
|
| |
| <center><math>\displaystyle M \leq \frac{\func{\opt}{I}}{1-\epsilon} + 1 \leq \braq{1 + 2\epsilon}\func{\opt}{I} + 1
| |
| </math></center>
| |
|
| |
| Druga nierówność wynika z prostego przekształcenia arytmetycznego przy <math>\displaystyle 0 < \epsilon \leq \frac{1}{2}</math>.
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Aproksymacja dla problemu PARTITION.
| |
|
| |
| Optymalizacyjna wersja problemu PARTITION powstaje, kiedy chcemy wybrać podzbiór <math>\displaystyle A' \subseteq A</math> taki, że minimalizuje wartość <math>\displaystyle \size{\sum_{a \in A'} \func{s}{a} - \sum_{a \in A \setminus A'} \func{s}{a}}</math>
| |
|
| |
| Uzasadnij, że dla tego problemu nie ma algorytmu PTAS.
| |
|
| |
| Inna wersja optymalizacyjna problemu PARTITION powstaje, kiedy mierzymy odległość od równomiernego podziału przez iloraz zamiast przez różnicę. Chcemy wtedy wybrać podzbiór <math>\displaystyle A' \subseteq A</math> taki, że iloraz
| |
|
| |
| <center><math>\displaystyle \frac{\sum_{a \in A'} \func{s}{a}}{\sum_{a \in A \setminus A'} \func{s}{a}} \geq 1
| |
| </math></center>
| |
|
| |
| jednocześnie minimalizując wartość tego ilorazu.
| |
|
| |
| Pokaż algorytm FPTAS dla tej wersji problemu PARTITION.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Zauważ, że optimum dla pierwszego problemu wynosi <math>\displaystyle 0</math> wtedy i tylko wtedy, gdy elementy wejściowe są pozytywnym przykładem dla zwykłego problemu PARTITION.
| |
|
| |
| Konstrukcję FPTAS dla drugiego problemu rozpocznij od przypomnienia sobie algorytmu pseudowielomianowego.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Pokażemy, że dla pierwszego problemu nie istnieje żaden algorytm <math>\displaystyle a</math>-aproksymacyjny. To w oczywisty sposób pociąga za sobą brak algorytmu PTAS.
| |
| Ponieważ optimum dla pierwszego problemu wynosi <math>\displaystyle 0</math> tylko dla takiego zbioru <math>\displaystyle A</math>, który da się podzielić na dwie równe części, więc dowolny algorytm <math>\displaystyle a</math>-aproksymacyjny musiałby znajdować rozwiązanie nie większe niż <math>\displaystyle a\cdot 0 = 0</math> i tym samym rozstrzygać problem PARTITION.
| |
|
| |
| Żeby skonstruować FPTAS dla drugiego problemu załóżmy, że <math>\displaystyle A=\{a_1,a_2,\ldots,a_n\}</math> i przypomnijmy, że znamy algorytm pseudowielomianowy dla tego problemu.
| |
|
| |
| Algorytm FPTAS dla tego problemu powstaje poprzez zaokrąglenie liczb podanych na wejściu i wykonanie pseudowielomianowego algorytmu dokładnego.
| |
|
| |
| Przyjmując <math>\displaystyle T=\sum_{i=1}^n \func{s}{a_i}</math> i <math>\displaystyle K=\frac{\epsilon T}{4n}</math> i znajdując rozwiązanie dokładne przy <math>\displaystyle \func{s'}{a} = \frac{\func{s}{a}}{K}</math> możemy przeprowadzić analizę podobną do tej wykorzystanej w problemie KNAPSACK. Są jednak subtelne różnice.
| |
|
| |
| Może się zdarzyć, że podzbiór <math>\displaystyle A'</math> znaleziony przy wagach <math>\displaystyle s'</math> nie jest rozwiązaniem dopuszczalnym przy wagach <math>\displaystyle s</math>, gdyż <math>\displaystyle \frac{\sum_{a \in A'} \func{s'}{a}}{\sum_{a \in A\setminus A'} \func{s'}{a}} \geq 1</math> nie pociąga za sobą takiej samej nierówności przy wagach <math>\displaystyle s</math>. Z problemem tym możemy sobie na szczęście łatwo poradzić zamieniając znaleziony zbiór <math>\displaystyle A'</math> na <math>\displaystyle A\setminus A'</math>. Dalszą analizę przeprowadzimy tylko w przypadku kiedy nie jest potrzebna taka zamiana, gdyż drugi przypadek jest analogiczny.
| |
|
| |
| Możemy zatem zapisać następujący ciąg nierówności, gdzie <math>\displaystyle O</math> jest rozwiązaniem optymalnym:
| |
|
| |
| <center><math>\displaystyle \frac{T}{2} \leq \sum_{a \in A'} \func{s}{a} \leq \sum_{a \in A'} \floor{\frac{\func{s}{a}+K}{K}}K \leq \sum_{a \in O} \floor{\frac{\func{s}{a}}{K}}K + Kn \leq \opt + 2Kn \leq \opt + \epsilon\frac{T}{2} \leq \braq{1+\epsilon} \opt
| |
| </math></center>
| |
|
| |
| Przy przekształceniach korzystamy z własności zaokrągleń, a ostatnia nierówność wynika z tego, że <math>\displaystyle \opt \geq \frac{T}{2}</math>.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Problem BIN COVERING.
| |
|
| |
| Rozważ problem dualny do BIN PACKING:
| |
|
| |
| {{problem|||
| |
| Pokrywanie - BIN COVERING.
| |
|
| |
| Mając dany zbiór <math>\displaystyle n</math> przedmiotów o wagach wymiernych <math>\displaystyle w_1, w_2, \ldots, w_n \in \left(0,1\right]</math>. Należy znaleźć przyporządkowanie ich do jak największej liczby pojemników. Suma wag przedmiotów w jednym pojemniku musi przekraczać <math>\displaystyle 1</math>, a część przedmiotów może być w ogóle nie wykorzystana.
| |
| }}
| |
|
| |
| Można się domyślać, ze problem ten ma charakterystykę podobną do BIN PACKING.
| |
|
| |
| Pokaż, że o ile <math>\displaystyle \pneqnp</math> to nie ma dla niego algorytmu <math>\displaystyle a</math>-aproksymacyjnego dla <math>\displaystyle a>\frac{1}{2}</math>. Skonstruuj asymptotyczny PTAS przy dodatkowym założeniu, że rozmiary wszystkich przedmiotów są większe niż pewna stała <math>\displaystyle c>0</math> (istnieje również asymptotyczny PTAS bez tego dodatkowego założenia, ale jego analiza jest znacznie trudniejsza).
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wykorzystaj te same techniki co w problemie BIN PACKING. Użyj redukcji problemu PARTITION do pokazania, że nie istnieje algorytm <math>\displaystyle a</math>-aproksymacyjny. Skonstruuj rodzinę algorytmów <math>\displaystyle \mathcal{A}_\epsilon</math> pokrywających conajmniej <math>\displaystyle \braq{1 - \epsilon}\opt</math> pojemników przy pomocy grupowania, zaokrąglania i przeglądania wyczerpującego. Dzięki stałej <math>\displaystyle c</math> nie musisz się przejmować przedmiotami o wadze mniejszej niż <math>\displaystyle \epsilon</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Aby pokazać pierwszą część wystarczy zauważyć, że jeżeli mamy instancję problemu PARTITION z elementami <math>\displaystyle a_1,a_2,\ldots,a_n</math> i sumą wag <math>\displaystyle S=\sum_{i=1}^{n}\func{s}{a_i}</math>, to przy użyciu przedmiotów o wagach <math>\displaystyle \frac{\func{s}{a_1}}{S},\frac{\func{s}{a_2}}{S},\ldots,\frac{\func{s}{a_n}}{S}</math> można pokryć <math>\displaystyle 2</math> pojemniki tylko wtedy kiedy da się elementy <math>\displaystyle A</math> rozbić na dwa podzbiory o tej samej wadze sumarycznej. Zatem algorytm <math>\displaystyle a</math>-aproksymacyjny dla <math>\displaystyle a> \frac{1}{2}</math> pozwoliłby rozstrzygać o problemie PARTITION.
| |
|
| |
| Konstrukcja asymptotycznego PTAS przebiega dokładnie tak samo jak dla prolemu BIN PACKING.
| |
|
| |
| Istnieje algorytm, który dla instancji z co najwyżej <math>\displaystyle K</math> różnymi wagami większymi niż <math>\displaystyle \epsilon</math> w czasie wielomianowym podaje rozwiązanie optymalne. Tak jak poprzednio można wtedy rozważyć wszystkie przypadki, których jest wielomianowo wiele.
| |
|
| |
| Dla zadanego <math>\displaystyle \epsilon</math> i ograniczeniu instancji do zawierających przedmioty większe niż <math>\displaystyle \epsilon</math> możemy przeprowadzić taki sam podział przedmiotów na <math>\displaystyle K=\ceil{\frac{1}{\epsilon^2}}</math> grup tak, aby w każdej grupie było co najwyżej <math>\displaystyle Q=\floor{n\epsilon^2}</math> przedmiotów, a następnie zastosować algorytm dokładny dla zaokrągleń do najmniejszego przedmiotu w grupie.
| |
|
| |
| Powtórzenie tej samej analizy pokazuje, że jest to algorytm <math>\displaystyle \braq{1-\epsilon}</math>-aproksymacyjny.
| |
|
| |
| Dodatkowe założenie o tym, że <math>\displaystyle w_i > c</math> pozwala dla <math>\displaystyle \epsilon < c</math> nie rozważać przedmiotów o wagach mniejszych od <math>\displaystyle \epsilon</math>. Jeżeli natomiast <math>\displaystyle \epsilon > c</math> możemy uzyć algorytmu <math>\displaystyle \mathcal{A}_c</math>.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==L-redukcje==
| |
|
| |
| Wprowadzimy teraz pojęcie redukcji zachowującej aproksymację. Pozwoli nam to na bardziej systematyczne niż do tej pory zbadanie klasy problemów, dla których możliwa jest aproksymacja. W dalszej części będziemy poszukiwać klasy problemów aproksymowalnych i problemów w tej klasie zupełnych względem podanej redukcji. Definicja interesującej nas redukcji jest podobna do tej jaką wprowadziliśmy pomiędzy problemami funkcyjnymi.
| |
|
| |
| {{definicja|||
| |
| Dla dwóch problemów optymalizacyjnych <math>\displaystyle A</math> i <math>\displaystyle B</math>, parę funkcji <math>\displaystyle R: D_A \rightarrow D_B</math> i <math>\displaystyle S: S_B \rightarrow S_A</math> obliczalnych w pamięci logarytmicznej nazywamy L-redukcją, jeżeli istnieją dwie stałe dodatnie <math>\displaystyle \alpha</math> i <math>\displaystyle \beta</math> takie, że spełnione są następujące własności:
| |
| * Dla dowolnej instancji <math>\displaystyle x</math> problemu <math>\displaystyle A</math> zachodzi:
| |
|
| |
| <center><math>\displaystyle \func{\opt_B}{\func{R}{x}} \leq \alpha \cdot \func{\opt_A}{x}
| |
| </math></center>
| |
| * Dla dowolnego rozwiązania dopuszczalnego <math>\displaystyle s</math> instancji <math>\displaystyle \func{R}{x}</math> zachodzi:
| |
|
| |
| <center><math>\displaystyle \size{\func{\opt_A}{x} - \func{\obj_A}{x,\func{S}{s}}} \leq \beta \size{\func{\opt_B}{\func{R}{x}} - \func{\obj_B}{\func{R}{x},s}}
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| Intuicyjnie, funkcja <math>\displaystyle R</math> L-redukcji (redukcji liniowej) zamienia instancję problemu <math>\displaystyle A</math> na instancję problemu <math>\displaystyle B</math> nie zmieniając wartości rozwiązania optymalnego bardziej niż o stałą <math>\displaystyle \alpha</math>. Funkcja <math>\displaystyle S</math> pozwala natomiast przeprowadzić dowolne z rozwiązań z powrotem na rozwiązanie instancji <math>\displaystyle A</math> nie zmieniając odległości od optimum bardziej niż o stałą <math>\displaystyle \beta</math>.
| |
|
| |
| {{uwaga|||
| |
| Warto zauważyć, że definicja L-redukcji nie zależy od tego, czy problemy <math>\displaystyle A</math> i <math>\displaystyle B</math> są problami minimalizacyjnymi, czy maksymalizacyjnymi.
| |
| }}
| |
|
| |
| Przyjrzyjmy się teraz jeszcze raz redukcji problemu zbioru niezależnego do pokrycia wierzchołkowego. Jest ona oparta o fakt, że problemy te są do siebie dualne. Dopełnienie dowolnego zbioru niezależnego jest pokryciem wierzchołkowym i na odwrót.
| |
|
| |
| Definicje odpowiednich funkcji są w związku z tym bardzo proste. <math>\displaystyle R</math> to po prostu funkcja identycznościowa na grafach, a <math>\displaystyle S</math> zwraca dopełnienie zbioru wierzchołków. Okazuje się, że nie jest to jednak L-redukcja, gdyż stosunku rozmiarów rozwiązań obu problemów nie da się w żaden sposób ograniczyć przez stałe.
| |
|
| |
| Takie ograniczenie można uzyskać zawężając klasę grafów. Jeżeli ograniczymy maksymalny stopień wierzchołków występujących w grafie przez liczbę <math>\displaystyle k</math>, to otrzymamy problemy <math>\displaystyle k</math>-INDPENDENT SET i <math>\displaystyle k</math>-VERTEX COVER. Przypomnijmy, że z redukcji problemu <math>\displaystyle 3</math>SAT wynika, że już problem <math>\displaystyle 4</math>-INDEPENDENT SET jest <math>\displaystyle \cc{NP}</math>-zupełny.
| |
|
| |
| Pokażemy, że funkcje <math>\displaystyle R</math> i <math>\displaystyle S</math> tworzą L-redukcję problemu <math>\displaystyle k</math>-INDEPENDENT SET do <math>\displaystyle k</math>-NODE COVER.
| |
|
| |
| Zauważmy, że dla grafu <math>\displaystyle G=\braq{V,E}</math> ze stopniem wierzchołków ograniczonym przez <math>\displaystyle k</math> rozmiar maksymalnego zbioru niezależnego to co najmniej <math>\displaystyle \frac{\size{V}}{k+1}</math> - dla każdego zbioru niezależnego o mniejszym rozmiarze, zbiór jego wszystkich sąsiadów jest co najwyżej <math>\displaystyle k</math> razy większy i nie obejmuje w związku z tym całego grafu. Można zatem taki zbiór niezależny poszerzyć.
| |
|
| |
| Tymczasem minimalne pokrycie wierzchołkowe ma w oczywisty sposób co najwyżej <math>\displaystyle \size{V}</math> elementów. W związku z tym możemy ustalić wartość parametru <math>\displaystyle \alpha</math> na <math>\displaystyle k+1</math>.
| |
|
| |
| Wystarczy teraz zauważyć, że odległość rozwiązania znalezionego od optymalnego nie zmienia się przy przejściu przez funkcję <math>\displaystyle S</math>. W związku z tym możemy ustalić wartość parametru <math>\displaystyle \beta</math> na <math>\displaystyle 1</math>.
| |
|
| |
| Ta krótka analiza pozwala stwierdzić, że para <math>\displaystyle \braq{R,S}</math> jest L-redukcją problemu <math>\displaystyle k</math>-INDEPENDENT SET do <math>\displaystyle k</math>-NODE COVER.
| |
|
| |
| Można też skonstruować odwrotną L-redukcję problemu <math>\displaystyle k</math>-NODE COVER do <math>\displaystyle k</math>-INDEPENDENT SET. Oczywiście należy użyć tych samych funkcji <math>\displaystyle R</math> i <math>\displaystyle S</math>, ale żeby uzyskać liniową zależność rozmiaru maksymalnego zbioru niezależnego od minimlanego pokrycia wierzchołkowego trzeba się trochę postarać. Zauważmy, że dla antykliki rozmiar minimalnego pokrycia wierzchołkowego wynosi <math>\displaystyle 0</math>, a maksymalny zbiór niezależny ma rozmiar równy ilości wierzchołków. Wynika stąd, że punkty izolowane mogą sprawiać problem dla L-redukcji.
| |
|
| |
| W nowej redukcji funkcja <math>\displaystyle R</math> będzie usuwać wierzchołki izolowane z grafu (które i tak nie należą do minimalnego pokrycia wierzchołkowego). Funkcja <math>\displaystyle S</math> nadal będzie zamieniać zbiór wierzchołków na jego uzupełnienie (ale tylko w obrębie wierzchołków nie izolowanych). Rozmiar minimalnego pokrycia wierzchołkowego w grafie bez wierzchołków izolowanych wynosi co najmniej <math>\displaystyle \frac{\size{V}}{k}</math> - ponieważ jest co najmniej <math>\displaystyle \size{V}</math> krawędzi, a każdy wierzchołek pokrywa co najwyżej <math>\displaystyle k</math> z nich. To oszacowanie pozwala nam stwierdzić, że nowa redukcja jest L-redukcją z parametrami <math>\displaystyle k</math> i <math>\displaystyle 1</math>.
| |
|
| |
| {{cwiczenie|||
| |
| Złożenie L-redukcji.
| |
|
| |
| Pokaż, że jeżeli para <math>\displaystyle \braq{R_1,S_1}</math> jest L-redukcją problemu <math>\displaystyle \Pi_1</math> do <math>\displaystyle \Pi_2</math>, a para <math>\displaystyle \braq{R_2,S_2}</math> L-reduckją <math>\displaystyle \Pi_2</math> do <math>\displaystyle \Pi_3</math>, to <math>\displaystyle \braq{R_1 \circ R_2, S_2 \circ S_1}</math> jest L-redukcją <math>\displaystyle \Pi_1</math> do <math>\displaystyle \Pi_3</math>.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Współczynniki nowej redukcji są iloczynami współczynników redukcji <math>\displaystyle \braq{R_1,S_1}</math> i <math>\displaystyle \braq{R_2,S_2}</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Niech <math>\displaystyle \alpha_1</math> i <math>\displaystyle \beta_1</math> będą współczynnikami pierwszej redukcji, a <math>\displaystyle \alpha_2</math> i <math>\displaystyle \beta_2</math> drugiej. Zatem dla dowolnej instancji <math>\displaystyle x</math> problemu <math>\displaystyle \Pi_1</math> zachodzi:
| |
|
| |
| <center><math>\displaystyle \func{\opt_{\Pi_3}}{\func{R_2}{\func{R_1}{x}}} \leq \alpha_2 \func{\opt_{\Pi_2}}{\func{R_1}{x}} \leq \alpha_1 \alpha_2 \func{\opt_{\Pi_1}}{x}
| |
| </math></center>
| |
|
| |
| Dla dowolnego rozwiązania dopuszczalnego <math>\displaystyle s</math> dla <math>\displaystyle \func{R_2}{\func{R_1}{x}}</math> zachodzi:
| |
|
| |
| <center><math>\displaystyle \size{\func{\opt_{\Pi_1}}{x} - \func{\obj_{\Pi_1}}{x,\func{S_1}{\func{S_2}{s}}}} \leq
| |
| \beta_1 \size{\func{\opt_{\Pi_2}}{\func{R_1}{x}} - \func{\obj_{\Pi_2}}{\func{R_1}{x},\func{S_2}{s}}} \leq
| |
| \beta_1 \beta_2 \size{\func{\opt_{\Pi_3}}{\func{R_2}{\func{R_1}{x}}} - \func{\obj_{\Pi_3}}{\func{R_2}{\func{R_1}{x}},s}}
| |
| </math></center>
| |
|
| |
| Zatem skonstruowana redukcja jest L-redukcją z parametrami <math>\displaystyle \alpha_1 \alpha_2</math> i <math>\displaystyle \beta_1 \beta_2</math>.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Przenoszenie aproksymacji przez L-redukcje.
| |
|
| |
| Pokaż, że jeżeli problem minimalizacyjny <math>\displaystyle A</math> L-redukuje się do problemu <math>\displaystyle B</math> i dla problemu <math>\displaystyle B</math> istnieje algorytm <math>\displaystyle b</math>-aproksymacyjny, to istnieje stała <math>\displaystyle a</math> taka, że dla problemu <math>\displaystyle A</math> istnieje algorytm <math>\displaystyle a</math>-aproksymacyjny.
| |
|
| |
| Pokaż, że dla dowolnych problemów optymalizacyjnych <math>\displaystyle A</math> i <math>\displaystyle B</math>, że jeżeli <math>\displaystyle A</math> L-redukuje się do <math>\displaystyle B</math> i istnieje wielomianowy schemat aproksymacji dla problemu <math>\displaystyle B</math>, to istnieje też taki schemat dla problemu <math>\displaystyle A</math>.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Przeprowadź instancję problemu <math>\displaystyle A</math> na instnację <math>\displaystyle B</math>, użyj algorytmu aproksymacyjnego i przeprowadź znalezione rozwiązanie z powrotem na wynik problemu <math>\displaystyle A</math>. Użyj ograniczeń <math>\displaystyle \alpha</math> i <math>\displaystyle \beta</math> do przeniesienia gwarancji aproksymacji.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Niech <math>\displaystyle \braq{R,S}</math> będzie L-redukcją problemu <math>\displaystyle A</math> do <math>\displaystyle B</math> ze stałymi <math>\displaystyle \alpha</math> i <math>\displaystyle \beta</math>.
| |
| Niech <math>\displaystyle \mathcal{B}</math> będzie <math>\displaystyle b</math>-aproksymacyjnym algorytmem dla problemu <math>\displaystyle B</math>. Skonstruujemy teraz algorytm <math>\displaystyle \mathcal{A}</math> dla problemu <math>\displaystyle A</math>, którego działanie dla dowolnej instancji <math>\displaystyle x</math> można opisać poprzez równanie:
| |
|
| |
| <center><math>\displaystyle \func{\mathcal{A}}{x} = \func{S}{\func{\mathcal{B}}{\func{R}{x}}}
| |
| </math></center>
| |
|
| |
| Załóżmy, że <math>\displaystyle B</math> jest problemem maksymalizacyjnym.
| |
| Fakt, że <math>\displaystyle \mathcal{B}</math> jest algorytmem <math>\displaystyle b</math>-aproksymacyjnym i własności L-redukcji gwarantują nam wtedy następujące nierówności:
| |
|
| |
| <center><math>\displaystyle \aligned \func{\opt_B}{\func{R}{x}} &\leq \alpha \func{\opt_A}{x} \\
| |
| \func{\obj_B}{\func{R}{x},\func{\mathcal{B}}{\func{R}{x}}} &\geq b \cdot \func{\opt_B}{\func{R}{x}} \\
| |
| \func{\obj_A}{x,\func{\mathcal{A}}{x}} - \func{\opt_A}{x} &\leq \beta\braq{\func{\opt_B}{\func{R}{x}} - \func{\obj_B}{\func{R}{x},\func{\mathcal{B}}{\func{R}{x}}}} </math> , <math>\displaystyle
| |
| \endaligned</math></center>
| |
|
| |
| co po prostym przekształceniu daje:
| |
|
| |
| <center><math>\displaystyle \func{\obj_A}{x,\func{\mathcal{A}}{x}} \leq \braq{1 + \alpha\beta\braq{1-b}}\func{\opt_A}{x}
| |
| </math></center>
| |
|
| |
| i pozwala stwierdzić, że <math>\displaystyle \mathcal{A}</math> jest algorytmem <math>\displaystyle \braq{1+\alpha\beta\braq{1-b}}</math>-aproksymacyjnym.
| |
|
| |
| Jeżeli <math>\displaystyle B</math> jest problemem minimalizacyjnym to analogiczna analiza dowodzi, że <math>\displaystyle \mathcal{A}</math> jest algorytmem <math>\displaystyle a</math>-aproksymacyjnym dla <math>\displaystyle a=1+\alpha\beta\braq{b-1}</math>.
| |
|
| |
| Przeprowadzenie analogicznego rozumowania przy założeniu, że <math>\displaystyle A</math> jest problemem maksymalizacyjnym prowadzi do następujących nierówności:
| |
|
| |
| <center><math>\displaystyle \func{\obj_A}{x,\func{\mathcal{A}}{x}} \geq \braq{1 - \alpha\beta\braq{1-b}}\func{\opt_A}{x}
| |
| </math></center>
| |
|
| |
| dla <math>\displaystyle B</math> maksymalizacyjnego i
| |
|
| |
| <center><math>\displaystyle \func{\obj_A}{x,\func{\mathcal{A}}{x}} \geq \braq{1 - \alpha\beta\braq{b-1}}\func{\opt_A}{x}
| |
| </math></center>
| |
|
| |
| dla <math>\displaystyle B</math> minimalizacyjnego.
| |
|
| |
| Te wyniki nie pozwalają przenieść gwarancji aproksymacji, gdyż otrzymane współczynniki mogą być ujemne, ale wszystkie cztery ograniczenia mają tą własność, że zmierzają do <math>\displaystyle 1</math> przy <math>\displaystyle b</math> zmierzającym do <math>\displaystyle 1</math>. To pozwala przenieść PTAS dla problemu <math>\displaystyle B</math> na PTAS dla problemu <math>\displaystyle A</math>.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Różnica optimum dla NODE COVER i INDEPENDENT SET.
| |
|
| |
| Pokaż, że dla dowolnej liczby wymiernej <math>\displaystyle q > 0</math> można skonstruować graf, dla którego iloraz rozmiaru maksymalnego zbioru niezależnego do minimalnego pokrycia wierzchołkowego wynosi <math>\displaystyle q</math>.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| {różnica optimum NC i IS - ZO-8.1}
| |
| Przykładem grafu spełniającego warunki zadania dla liczby <math>\displaystyle q=\frac{k}{l}</math> jest graf składający się z <math>\displaystyle k-1</math> elementowej antykliki i <math>\displaystyle l+1</math> elementowej kliki. Rozmiar minimalnego pokrycia wierzchołkowego dla tego grafu to <math>\displaystyle l</math>, a największy zbiór niezależny ma <math>\displaystyle k</math> wierzchołków.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==Klasa <math>\displaystyle \cc{MAXSNP}</math>==
| |
|
| |
| Wprowadzimy teraz formalną definicję klasy <math>\displaystyle \cc{MAXSNP}</math>, która pozwoli nam bardziej metodycznie zbadać problemy optymalizacyjne. Dalsze badania nad tą klasą doprowadzą nas do bardzo ciekawych rezultatów dotyczących możliwości aproksymacji.
| |
|
| |
| Zaczniemy od zdefiniowania klasy <math>\displaystyle \cc{MAXSNP}_0</math>, która opisuje problemy maksymalizacyjne. Jej charakteryzacja jest analogiczna do charakteryzacji klasy <math>\displaystyle \cc{NP}</math> podanej w twierdzeniu Fagina.
| |
|
| |
| {{definicja|||
| |
| Problem <math>\displaystyle A</math> należy do klasy <math>\displaystyle \cc{MAXSNP}_0</math>, jeżeli można go wyrazić za pomocą formuły:
| |
|
| |
| <center><math>\displaystyle \max_{S}\defset{\braq{x_1,x_2,\ldots,x_k} \in V^k}{\func{\phi}{G_1,G_2,\ldots,G_m,S,x_1,x_2,\ldots,x_k}}
| |
| </math></center>
| |
|
| |
| Wejściem dla problemu <math>\displaystyle A</math> jest ciąg relacji (być może wieloargumentowych) <math>\displaystyle G_i,i=1,2,\ldots,m</math> nad skończonym uniwersum <math>\displaystyle V</math>. Poszukiwana jest natomiast relacja <math>\displaystyle S</math>, która maksymalizowałaby liczbę naborów zmiennych <math>\displaystyle x_i</math> takich że formuła pierwszego rzędu bez kwantyfikatorów <math>\displaystyle \phi</math> jest spełniona.
| |
| }}
| |
|
| |
| {{definicja|||
| |
| Klasa <math>\displaystyle \cc{MAXSNP}</math> jest domknięciem <math>\displaystyle \cc{MAXSNP}_0</math> ze względu na L-redukcje.
| |
| }}
| |
|
| |
| Zobaczmy teraz przykład problemu, który należy do <math>\displaystyle \cc{MAXSNP}_0</math>. Wybierzemy problem <math>\displaystyle k</math>-INDEPENDENT SET. Zwykła reprezentacja grafu poprzez relację binarną nie pozwala wygodnie przedstawić ograniczenia stopnia wierzchołka i raczej nie prowadzi do reprezentacji poprzez odpowiednią formułę. Dlatego użyjemy niestandardowej reprezentacji grafu poprzez <math>\displaystyle k+1</math>-argumentową relację <math>\displaystyle H</math>. Każdemu wierzchołkowi <math>\displaystyle G</math> odpowiada jedna krotka relacji <math>\displaystyle H</math> - <math>\displaystyle \braq{x,y_1,y_2,\ldots,y_k}</math>, która koduje sąsiedztwo wierzchołka <math>\displaystyle x</math>. Wierzchołki <math>\displaystyle y_1,y_2,\ldots,y_k</math> to sąsiedzi <math>\displaystyle x</math>. Jeżeli <math>\displaystyle x</math> nie ma <math>\displaystyle k</math> sąsiadów, to na brakujących pozycjach występuje <math>\displaystyle x</math>. Problem <math>\displaystyle k</math>-zbioru niezależnego koduje się wtedy w następujący sposób:
| |
|
| |
| <center><math>\displaystyle \aligned \max_{S\subseteq V}\{\braq{x,y_1,y_2,\ldots,y_k} \in V^k : \braq{x,y_1,y_2,\ldots,y_k} \in H \wedge x \in S \wedge \\
| |
| \wedge \left[x = y_1 \vee y_1 \notin S\right] \wedge \left[ x = y_2 \vee y_2 \notin S\right] \wedge \ldots \wedge \left[ x = y_k \vee y_k \notin S\right]\}
| |
| \endaligned</math></center>
| |
|
| |
| Wybór relacji <math>\displaystyle S</math> koduje pewien podzbiór wierzchołków. Formuła kodująca problem jest spełniona dla krotek odpowiadających tym wierzchołkom <math>\displaystyle x</math>, które należą do wybranego zbioru, a żaden z sąsiadów nie należy. Odpowiada to więc zbiorowi niezależnemu.
| |
|
| |
| Pokazaliśmy zatem, że problem <math>\displaystyle k</math>-INDEPENDENT SET należy do klasy <math>\displaystyle \cc{MAXSNP}_0</math>.
| |
| Natychmiastowym wnioskiem jest, że problem <math>\displaystyle k</math>-NODE COVER jest problemem z <math>\displaystyle \cc{MAXSNP}</math>. Znamy przecież jego L-redukcję do <math>\displaystyle k</math>-INDEPENDENT SET.
| |
|
| |
| {{cwiczenie|||
| |
| MAX CUT w <math>\displaystyle \cc{MAXSNP}</math>.
| |
|
| |
| Pokaż, że problem MAX CUT należy do <math>\displaystyle \cc{MAXSNP}</math>.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Użyj zwykłej binarnej reprezentacji grafu do skonstruowania odpowiedniej formuły pokazującej, że MAX CUT należy do <math>\displaystyle \cc{MAXSNP}_0</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Formuła kodująca problem MAX CUT to
| |
|
| |
| <center><math>\displaystyle \max_{S\subseteq V}\defset{\braq{x,y} \in V^2}{\braq{x,y}\in G \wedge x \in S \wedge y \notin S}
| |
| </math></center>
| |
|
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==Problemy MAXSAT i MAX FUNCTION SAT==
| |
|
| |
| Problem maksymalnej spełnialności MAXSAT i jego zawężenia pełnią podobną rolę dla klasy <math>\displaystyle \cc{MAXSNP}</math> jak problem SAT dla <math>\displaystyle \cc{NP}</math>. W tej części przyjrzymy się dokładniej temu problemow i jego różnym wersjom. Podamy również algorytmy aproksymacyjne i udowodnimy zupełność zawężeń tego problemu dla klasy <math>\displaystyle \cc{MAXSNP}</math>.
| |
|
| |
| Przypomnijmy, że na wejściu problemu MAXSAT dostajemy formułę logiczną w koniunkcyjnej postaci normalnej z <math>\displaystyle n</math> zmiennymi. Poszukujemy takiego wartościowania tych zmiennych, które zmaksymalizowałoby liczbę spełnionych klauzul. Dla wygody dodajemy warunek, aby każda z klauzul była inna.
| |
|
| |
| <math>\displaystyle \frac{1}{2}</math>-aproksymację problemu MAXSAT można osiągnąć bardzo prostą metodą:
| |
|
| |
| Algorytm wybierający wartościowanie <math>\displaystyle x</math> lub <math>\displaystyle \overline{x}</math>.
| |
| # Wybierz dowolne wartościowanie <math>\displaystyle x</math> dla <math>\displaystyle n</math> zmiennych występujących w formule.
| |
| # Skonstruuj wartościowanie <math>\displaystyle \overline{x}</math>, które przyporządkowuje zmiennym wartościowanie odwrotne do <math>\displaystyle x</math>.
| |
| # Jako wynik podaj to z wartościowań <math>\displaystyle x</math>, <math>\displaystyle \overline{x}</math>, przy którym więcej klauzul jest spełnionych.
| |
|
| |
| {{twierdzenie|||
| |
| Podany algorytm jest algorytmem <math>\displaystyle \frac{1}{2}</math>-aproksymacyjnym.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Zauważmy, że jeżeli któraś z alternatyw jest niespełniona przy wartościowaniu <math>\displaystyle x</math>, to musi być spełniona przy wartościowaniu <math>\displaystyle \overline{x}</math>. Jeżeli alternatywa jest niespełniona przy jakimś wartościowaniu, to znaczy, że każda ze zmiennych występujących w klauzuli jest wartościowana odwrotnie niż jej wystąpienie. Zatem przy wartościowaniu odwrotnym każdy z literałów występujących w alternatywie jest wartościowany pozytywnie i alternatywa musi być spełniona.
| |
|
| |
| Jeżeli zatem oznaczymy przez <math>\displaystyle m</math> - liczbę alternatyw w formule, przez <math>\displaystyle c</math> - liczbę alternatyw spełnionych przy wartościowaniu <math>\displaystyle x</math>, a przez <math>\displaystyle \overline{c}</math> - liczbę alternatyw spełnionych przy wartościowaniu <math>\displaystyle \overline{x}</math>, to zachodzą następującee nierówności:
| |
|
| |
| <center><math>\displaystyle \aligned c &\geq m - \overline{c} \\
| |
| \overline{c} &\geq m - c \\
| |
| c + \overline{c} &\geq 2m - c - \overline{c} \\
| |
| c + \overline{c} &\geq m
| |
| \endaligned</math></center>
| |
|
| |
| Ponieważ algorytm wybiera to z wartościowań <math>\displaystyle x</math> lub <math>\displaystyle \overline{x}</math>, przy którym więcej alternatyw jest spełnionych, to liczba spełnionych alternatyw jest nie mniejsza niż <math>\displaystyle \frac{1}{2}m</math>. Nawet jeżeli rozwiązanie optymalne zapewnia spełnienie wszystkich <math>\displaystyle m</math> alternatyw, to algorytm jest <math>\displaystyle \frac{1}{2}</math>-aproksymacyjny.
| |
| }}
| |
|
| |
| Pokażemy teraz pewną wariację na temat problemu MAXSAT.
| |
|
| |
| {{problem|||
| |
| Problem maksymalnej spełnialności funkcyjnej MAX FUNCTION SAT
| |
|
| |
| Danych jest <math>\displaystyle n</math> zmiennych logicznych <math>\displaystyle x_1,x_2,\ldots,x_n</math> oraz <math>\displaystyle m</math> funkcji logicznych <math>\displaystyle f_1,f_2,\ldots,f_m</math>. Należy znaleźć wartościowanie zmiennych <math>\displaystyle x_1,x_2,\ldots,x_n</math> przy którym największa liczba funkcji daje wynik pozytywny.
| |
| }}
| |
|
| |
| Ciekawym i istotnym dla dalszych rozważań zawężeniem problemów MAXSAT i MAX FUNCTION SAT jest ograniczenie liczby różnych zmiennych występujących w pojedynczej klauzuli lub funkcji logicznej. Jeżeli ta liczba jest ograniczonaa przez <math>\displaystyle k</math>, to mamy do czynienia z problemem MAX<math>\displaystyle k</math>SAT i MAX<math>\displaystyle k</math>FSAT.
| |
|
| |
| Przypomnijmy, że pokazaliśmy, że już problem MAX<math>\displaystyle 2</math>SAT jest <math>\displaystyle \cc{NP}</math>-zupełny (mimo że problem <math>\displaystyle 2</math>SAT nie jest). Teraz okaże się dlaczego te problemy są dla nas tak interesujące:
| |
|
| |
| {{twierdzenie|||
| |
| Problemy MAX<math>\displaystyle k</math>SAT należą do klasy <math>\displaystyle \cc{MAXSNP}_0</math>.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Pokażemy, że problem MAX<math>\displaystyle 2</math>SAT należy do <math>\displaystyle \cc{MAXSNP}_0</math>. Konstrukcja reprezentacji formuły i kodowania problemu dla większych <math>\displaystyle k</math> jest analogiczna.
| |
|
| |
| Zatem ustalamy, że uniwersum <math>\displaystyle V</math> to zbiór zmiennych występujących w formule, a trzy relacje binarne <math>\displaystyle G_0,G_1,G_2</math> kodują formułę. Para <math>\displaystyle \braq{x_1,x_2}</math> w relacji <math>\displaystyle G_i</math> koduje wystąpienie klauzuli zawierającej literały <math>\displaystyle x_1</math> i <math>\displaystyle x_2</math> z których <math>\displaystyle i</math> występuje pozytywnie. Żeby zapewnić reprezentację każdej alternatywy przez dokładnie jedną krotkę którejś z relacji wprowadzamy taką odpowiedniość pomiędzy relacjami i klauzulami:
| |
|
| |
| <center><math>\displaystyle \aligned \func{G_0}{x_i,x_j} & \Longleftrightarrow & \braq{\neg x_i \vee \neg x_j}; i < j \\
| |
| \func{G_1}{x_i,x_j} & \Longleftrightarrow & \braq{x_i \vee \neg x_j} \\
| |
| \func{G_2}{x_i,x_j} & \Longleftrightarrow & \braq{x_i \vee x_j}; i < j
| |
| \endaligned</math></center>
| |
|
| |
| Możemy teraz użyć następującej formuły reprezentującej problem MAX<math>\displaystyle 2</math>SAT:
| |
|
| |
| <center><math>\displaystyle \max_{S\subseteq V}\defset{\braq{x,y}}{\left[\func{G_0}{x,y} \wedge \braq{\neg \func{S}{x} \vee \neg \func{S}{y}}\right] \vee \left[\func{G_1}{x,y} \wedge \braq{\func{S}{x} \vee \neg \func{S}{y}}\right] \vee \left[\func{G_2}{x,y} \wedge \braq{\func{S}{x} \vee \func{S}{y}}\right]}
| |
| </math></center>
| |
|
| |
| Wybór relacji <math>\displaystyle S</math> odpowiada ustaleniu wartościowania, a konstrukcja formuły zapewnia, że liczba krotek <math>\displaystyle \braq{x,y}</math> spełniających formułę odpowiada liczbie alternatyw spełnionych przy danym wartościowaniu.
| |
| }}
| |
|
| |
| Zbudowanie algorytmu aproksymacyjnego dla problemu MAX<math>\displaystyle k</math>FSAT nie jest już tak proste, jak dla problemu MAXSAT. Załóżmy, że mamy <math>\displaystyle n</math> zmiennych <math>\displaystyle x_1,x_2,\ldots,x_n</math> i <math>\displaystyle m</math> funkcji logicznych <math>\displaystyle f_1,f_2,\ldots,f_m</math>, z których każda zależy od co najwyżej <math>\displaystyle k</math> zmiennych. Żeby dobrze zobrazować działanie algorytmu wyobraźmy sobie pełne drzewo binarne o <math>\displaystyle 2^n</math> liściach. Każdy węzeł wewnętrzny reprezentuje pewne częściowe wartościowanie zmiennych.
| |
|
| |
| {drzewo wartościowań - ZO-8.2}
| |
|
| |
| Dla każdego węzła drzewa <math>\displaystyle t</math> i funkcji <math>\displaystyle f_i</math> określamy funkcję:
| |
|
| |
| <center><math>\displaystyle \func{p}{t,f_i} = \frac{\text{liczba wartościowań rozszerzających }t\text{ przy których }f_i\text{ daje wynik pozytywny}}{\text{liczba wszystkich wartościowań rozszerzających }t}
| |
| </math></center>
| |
|
| |
| Łatwo zauważyć, że jeżeli węzły <math>\displaystyle t_0</math> i <math>\displaystyle t_1</math> są dziećmi <math>\displaystyle t</math> w drzewie wartościowań, to zachodzi:
| |
|
| |
| <center><math>\displaystyle \func{p}{t,f_i} = \frac{1}{2}\braq{\func{p}{t_0,f_i} + \func{p}{t_1,f_i}}
| |
| </math></center>
| |
|
| |
| Rozważmy teraz funkcję <math>\displaystyle \func{P}{t} = \sum_{i=1}^{m} \func{p}{t,f_i}</math>. Oczywistym wnioskiem z poprzedniej równości jest:
| |
|
| |
| <center><math>\displaystyle \func{P}{t} = \frac{1}{2}\braq{\func{P}{t_0} + \func{P}{t_1}}
| |
| </math></center>
| |
|
| |
| Zauważmy jeszcze, że obliczenia wartości <math>\displaystyle \func{P}{t}</math> dla konkretnego <math>\displaystyle t</math> można dokonać w czasie wielomianowym. Ponieważ każda z funkcji <math>\displaystyle f_i</math> zależy tylko od <math>\displaystyle k</math> zmiennych, więc można dokonać wyczerpującego przeglądu wszystkich <math>\displaystyle 2^k</math> wartościowań tych zmiennych zliczając te dla których <math>\displaystyle f_i</math> daje wynik pozytywny i są rozszerzeniami wartościowania <math>\displaystyle t</math>. Można zatem w czasie wielomianowym zsumować wartości <math>\displaystyle \func{p}{t,f_i}</math> dla wszystkich <math>\displaystyle m</math> funkcji <math>\displaystyle f_i</math>.
| |
|
| |
| Możemy już teraz przedstawić algorytm:
| |
|
| |
| Algorytm schodzący po drzewie wartościowań
| |
| # Ustaw zmienną <math>\displaystyle t</math> na korzeń <math>\displaystyle r</math> drzewa wartościowań.
| |
| # Dopóki <math>\displaystyle t</math> nie będzie liściem drzewa wartościowań:
| |
|
| |
| ;
| |
| : Obliczaj wartość <math>\displaystyle \func{P}{t_0}</math> i <math>\displaystyle \func{P}{t_1}</math> dla dzieci węzła <math>\displaystyle t</math> i ustaw <math>\displaystyle t</math> na to z dzieci, dla którego wartość <math>\displaystyle \func{P}{t_i}</math> jest większa.
| |
|
| |
| : Podaj wartościowanie opisywane przez węzeł <math>\displaystyle t</math> jako wynik.
| |
|
| |
| {{twierdzenie|||
| |
| Algorytm schodzący po drzewie wartościowań jest algorytmem <math>\displaystyle \frac{1}{2^k}</math>-aproksymacyjnym dla problemu MAX<math>\displaystyle k</math>FSAT.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Liczba funkcji dających wynik pozytywny przy wartościowaniu <math>\displaystyle t</math> znalezionym przez algorytm jest równa dokładnie <math>\displaystyle \func{P}{t}</math>. Ponieważ węzeł <math>\displaystyle t</math> określa wartość każdej ze zmiennych, to <math>\displaystyle \func{p}{t,f_i}</math> jest równe <math>\displaystyle 1</math> dla funkcji dających wynik pozytywny, a <math>\displaystyle 0</math> dla tych dających wynik negatywny.
| |
|
| |
| Zauważmy, że <math>\displaystyle \func{P}{t} \geq \func{P}{r}</math>. Jest tak dlatego, że przy każdym zejściu w dół drzewa od węzła <math>\displaystyle s</math> jest spełnione <math>\displaystyle \func{P}{s} = \frac{1}{2}\braq{\func{P}{s_0} + \func{P}{s_1}}</math>, więc któraś z wartości <math>\displaystyle \func{P}{s_0}</math>, lub <math>\displaystyle \func{P}{s_1}</math> jest większa lub równa <math>\displaystyle \func{P}{s}</math>, a algorytm wybiera zejście w kierunku większej z nich. W związku z tym wartość funkcji <math>\displaystyle P</math> dla aktualnie przeglądanego węzła nigdy nie maleje.
| |
|
| |
| Zatem liczba funkcji z wynikiem pozytywnym w rozwiązaniu znalezionym przez algorytm jest nie mniejsza niż <math>\displaystyle \ceil{\func{P}{r}}</math>. Ponieważ dla każdej funkcji, która może w ogóle dać wynik pozytywny przy jakimkolwiek wartościowaniu zachodzi <math>\displaystyle \func{p}{r,f_i} \geq \frac{1}{2^k}</math>, to liczba funkcji, które dają wynik pozytywny w rozwiązaniu optymalnym jest ograniczona z góry przez <math>\displaystyle \frac{\func{P}{r}}{\frac{1}{2^k}}</math>. To dowodzi że algorytm jest algorytmem <math>\displaystyle \frac{1}{2^k}</math>-aproksymacyjnym.
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Kodowanie MAX<math>\displaystyle k</math>FSAT w MAX<math>\displaystyle 3</math>SAT.
| |
|
| |
| Pokaż L-redukcję problemu MAX<math>\displaystyle k</math>FSAT do MAX<math>\displaystyle 3</math>SAT.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Użyj reprezentacji funkcji logicznej przez układ bramek logicznych, a następnie przedstaw każdą bramkę jako klauzulę <math>\displaystyle 3</math>SAT.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Dla wygody załóżmy, że żadna z funkcji nie przyjmuje stale wartości negatywnej. Gdyby któraś z nich miała taką własność, to możemy to rozpoznać i usunąć ją z instancji problemu.
| |
|
| |
| Skorzystamy teraz z tego, że każdą funkcję logiczną można przedstawić jako układ bramek logicznych zbudowany z bramek:
| |
| * wejściowych
| |
| * negacji (<math>\displaystyle \neg</math>)
| |
| * koniunkcji (<math>\displaystyle \wedge</math>)
| |
| * alternatywy (<math>\displaystyle \vee</math>)
| |
| * jednej bramki wyjściowej
| |
|
| |
| Skonstruowana formuła <math>\displaystyle 3</math>SAT będzie modelować układ takich bramek. Zmienne formuły będą odpowiadać bramkom i zmiennym występującym w modelowanej funkcji.
| |
| Dla każdej bramki wejściowej <math>\displaystyle g</math> dodajemy klauzule:
| |
| * <math>\displaystyle \braq{g \vee \neg x} \wedge \braq{\neg g \vee x}</math> - jeżeli bramka <math>\displaystyle g</math> odpowiada zmiennej <math>\displaystyle x</math>.
| |
| * <math>\displaystyle \braq{g}</math> lub <math>\displaystyle \braq{\neg g}</math> - jeżeli bramka <math>\displaystyle g</math> ma stałą wartość logiczną.
| |
|
| |
| Dalej, konstrukcja dla bramek operatorów logicznych jest następująca:
| |
| * <math>\displaystyle \braq{g \vee a} \wedge \braq{\neg g \vee \neg a}</math> - bramka <math>\displaystyle g</math> odpowiadająca operacji <math>\displaystyle \neg</math> z wejściem z bramki <math>\displaystyle a</math>.
| |
| * <math>\displaystyle \braq{g \vee \neg a} \wedge \braq{g \vee \neg b} \wedge \braq{\neg b \vee a \vee b}</math> - bramka <math>\displaystyle g</math> odpowiadająca operacji <math>\displaystyle \vee</math> z wejściami z bramek <math>\displaystyle a</math> i <math>\displaystyle b</math>.
| |
| * <math>\displaystyle \braq{\neg g \vee a} \wedge \braq{\neg g \vee b} \wedge \braq{g \vee \neg a \vee \neg b}</math> - bramka <math>\displaystyle g</math> odpowiadająca operacji <math>\displaystyle \wedge</math> z wejściami z bramek <math>\displaystyle a</math> i <math>\displaystyle b</math>.
| |
|
| |
| Dla bramki wyjściowej <math>\displaystyle g</math> dodajemy jedną klauzulę <math>\displaystyle \braq{g}</math>. W tak skonstruowanej formule wszystkie klauzule mogą być spełnione być może z wyjątkiem ostatniej. Wystarczy zawuażyć, że w każdej dodanej grupie mogą być spełnione wszystkie klauzule, o ile wartościowania są "zgodne" z zachowaniem bramki.
| |
|
| |
| Możemy zatem zamienić wszystkie funkcje logiczne występujące w problemie MAX<math>\displaystyle k</math>FSAT na formuły MAX<math>\displaystyle 3</math>SAT. Optimum tego drugiego problemu będzie równe ilości wszystkich bramek poza wyjściowymi zwiększonym o liczbę funkcji, które mogą jednocześnie dawać wynik pozytywny. Stąd możemy ustalić współczynnik <math>\displaystyle \beta</math> redukcji na <math>\displaystyle 1</math>.
| |
|
| |
| Żeby uzasadnić, że optimum w skonstruowanej formule jest ograniczone liniowo od optimum problemu MAX<math>\displaystyle k</math>FSAT przypomnijmy dowód dla algorytmu aproksymacyjnego dla problemu MAX<math>\displaystyle k</math>FSAT. Pokazaliśmy tam, że optimum problemu wynosi co najmniej <math>\displaystyle \frac{1}{2^k}m</math>, gdzie <math>\displaystyle m</math> jest liczbą funkcji. Tymczasem liczba klauzul zależy liniowo od liczby funkcji. Skonstruowana redukcja jest zatem L-redukcją.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Lepsza aproksymacja MAXSAT.
| |
|
| |
| Pokaż, że jeżeli wymagalibyśmy od instancji problemu MAXSAT aby w każdej alternatywie występowało przynajmniej <math>\displaystyle k</math> literałów, to istnieje algorytm <math>\displaystyle \braq{1-\frac{1}{2^k}}</math>-aproksymacyjny dla takiego problemu.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Jak wygląda oszacowanie <math>\displaystyle \func{P}{r,f_i}</math>, gdy <math>\displaystyle f_i</math> reprezentuje klauzulę?
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Wystarczy zauważyć, że jeżeli <math>\displaystyle f_i</math> reprezentuje klauzulę z <math>\displaystyle j</math> literałami, to <math>\displaystyle \func{P}{r,f_i}=1-\frac{1}{2^j}</math>, gdyż jest tylko jedno wartościowanie występujących w niej zmiennych, które jej nie spełnia. Możemy w związku z tym powtórzyć rozumowanie z dowodu aproksymacji problemu MAX<math>\displaystyle k</math>FSAT i podany tam algorytm w tym wypadku jest algorytmem <math>\displaystyle \braq{1-\frac{1}{2^k}}</math>-aproksymacyjnym.
| |
| </div></div>
| |
|
| |
| }}
| |
|
| |
| ==Problemy <math>\displaystyle \cc{MAXSNP}</math>-zupełne==
| |
|
| |
| Pokażemy teraz, że problem MAX<math>\displaystyle 3</math>SAT jest problemem zupełnym w sensie L-redukcji w klasie <math>\displaystyle \cc{MAXSNP}</math>. Jest to bardzo istotny fakt, bo oznacza, że pozytywne wyniki aproksymacjii tego elementarnego problemu przekładają się poprzez L-redukcje na wszystkie problemy z klasy <math>\displaystyle \cc{MAXSNP}</math>. Jest też to fakt interesujący ze względu na to, że wcale nie jest oczywiste, że problemy <math>\displaystyle \cc{MAXSNP}</math>-zupełne muszą w ogóle istnieć.
| |
|
| |
| {{twierdzenie|||
| |
| MAX<math>\displaystyle 3</math>SAT jest problemem zupełnym w sensie L-redukcji w klasie <math>\displaystyle \cc{MAXSNP}</math>.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Przypomnijmy, że klasa <math>\displaystyle \cc{MAXSNP}</math> jest definiowana jako klasa problemów L-redukowalnych do problemów z <math>\displaystyle \cc{MAXSNP}_0</math>. Zatem wystarczy, że pokażemy, że każdy problem z <math>\displaystyle \cc{MAXSNP}_0</math> jest L-redukowalny do problemu MAX<math>\displaystyle 3</math>SAT i skorzystamy z tego, że złożenie L-redukcji jest L-redukcją.
| |
|
| |
| Rozważmy zatem problem <math>\displaystyle A</math> z klasy <math>\displaystyle \cc{MAXSNP}_0</math> definiowany formułą:
| |
|
| |
| <center><math>\displaystyle \max_S\defset{\braq{x_1,x_2,\ldots,x_k}}{\phi}
| |
| </math></center>
| |
|
| |
| Rozważymy teraz konkretną instancję problemu <math>\displaystyle A</math> z ustalonym uniwersum <math>\displaystyle V</math> i relacjami <math>\displaystyle G_1,G_2,\ldots,G_m</math>. Dla każdej krotki <math>\displaystyle v = \braq{v_1,v_2,\ldots,v_k} \in V^k</math> definiujemy formułę <math>\displaystyle \phi_v</math>, która powstaje z <math>\displaystyle \phi</math> przez podstawienie wartości <math>\displaystyle v_1,v_2,\ldots,v_k</math> za zmienne <math>\displaystyle x_1,x_2,\ldots,x_k</math>. Każdą w formuł <math>\displaystyle \phi_v</math> możemy uprościć zamieniając każde wystąpienie relacji <math>\displaystyle G</math> i symbolu <math>\displaystyle =</math> wartościami prawdy i fałszu, które w konkretnej instancji są ustalone. W wyniku otrzymujemy formułę <math>\displaystyle \phi_v</math>, w której występują tylko symbole logiczne i relacja <math>\displaystyle S</math>.
| |
|
| |
| Możemy teraz spojrzeć na rozwiązanie tej instancjii problemu <math>\displaystyle A</math> jak na ustalenie wartościowania formuł <math>\displaystyle \func{S}{v_{i_1},v_{i_2},\ldots,v_{i_r}}</math> tak aby zmaksymalizować liczbę spełnionych formuł <math>\displaystyle \phi_v</math>. Jeżeli któraś z formuł <math>\displaystyle \phi_v</math> jest niespełnialna dla żadnego wartościowania, to już na tym etapie usuwamy ją z opisu problemu.
| |
|
| |
| Właśnie opisaliśmy redukcję problemu <math>\displaystyle A</math> do problemu MAX<math>\displaystyle l</math>FSAT, gdzie jest <math>\displaystyle \size{V}^r</math> zmiennych odpowiadających <math>\displaystyle \func{S}{v_{i_1},v_{i_2},\ldots,v_{i_r}}</math> i <math>\displaystyle \size{V}^r</math> funkcji logicznych odpowiadających formułom <math>\displaystyle \phi_v</math>. Stała <math>\displaystyle l</math> zależy tylko od postaci formuły <math>\displaystyle \phi</math> i należy ją ustalić równą liczbie wystąpień symbolu relacyjnego <math>\displaystyle S</math> w formule <math>\displaystyle \phi</math>. Możemy teraz użyć redukcji MAX<math>\displaystyle l</math>FSAT do MAX<math>\displaystyle 3</math>SAT.
| |
|
| |
| Musimy teraz pokazać, że otrzymana w ten sposób redukcja jest L-redukcją. Na podstawie instancji <math>\displaystyle x</math> problemu <math>\displaystyle A</math> możemy zbudować <math>\displaystyle \func{R}{x}</math> instancję problemu MAX<math>\displaystyle 3</math>SAT. Rozwiązanie <math>\displaystyle \func{S}{s}</math> możemy łatwo obliczyć odczytując relację <math>\displaystyle S</math> z wartości zmiennych występujących w rozwiązaniu problemu <math>\displaystyle \func{R}{x}</math>.
| |
|
| |
| Musimy teraz skorzystać z pewnych własności problemu MAX<math>\displaystyle l</math>FSAT i jego redukcji do MAX<math>\displaystyle 3</math>SAT.
| |
|
| |
| Po pierwsze - każda formuła <math>\displaystyle \phi_v</math> jest reprezentowana przez co najwyżej <math>\displaystyle c</math> klauzul, gdzie <math>\displaystyle c</math> zależy tylko od liczby bramek potrzebnych do wyrażenia formuły <math>\displaystyle \phi</math>.
| |
|
| |
| Po drugie - istnieje stała <math>\displaystyle d</math> taka, że dla <math>\displaystyle m</math> funkcji w problemie MAX<math>\displaystyle l</math>SAT istnieje wartościowanie, przy którym przynajmniej <math>\displaystyle dm</math> spośród funkcji ma wartość pozytywną. Skorzystamy z tego, że odrzuciliśmy funkcje, które stale przyjmują wartość negatywną. Stałą <math>\displaystyle d</math> równą <math>\displaystyle \frac{1}{2^l}</math> otrzymujemy z dowodu, że algorytm schodzący po drzewie wartościowań jest algorytmem <math>\displaystyle \frac{1}{2^l}</math>-aproksymacyjnym.
| |
|
| |
| Po trzecie - zastosowana redukcja MAX<math>\displaystyle l</math>FSAT do MAX<math>\displaystyle 3</math>SAT gwarantuje, że w rozwiązaniu optymalnym problemu <math>\displaystyle \func{R}{x}</math> wszystkie klauzule poza tymi przechowującymi wyniki funkcji są spełnione.
| |
|
| |
| Te trzy fakty sprawiają, że opisana redukcja jest L-redukcją z parametrami <math>\displaystyle \alpha = \frac{c}{d}</math> (<math>\displaystyle \func{\opt}{x} \geq dm</math>, <math>\displaystyle \func{\opt}{\func{R}{x}} \leq cm</math>) i <math>\displaystyle \beta = 1</math> (w rozwiązaniu optymalnym <math>\displaystyle \opt</math> problemu <math>\displaystyle \func{R}{x}</math> liczba spełnionych alternatyw zmniejszona o liczbę alternatyw innych niż przechowujące wyniki funkcji wyznacza dokładnie liczbę krotek <math>\displaystyle V^k</math>, dla których relacja <math>\displaystyle S</math> zachodzi).
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Problemy z <math>\displaystyle \cc{MAXSNP}_0</math> są aproksymowalne ze stałą.
| |
|
| |
| Pokaż, że dla każdego problemu z klasy <math>\displaystyle \cc{MAXSNP}</math> istnieje algorytm <math>\displaystyle a</math>-aproksymacyjny dla pewnej stałej.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wykorzystaj technikę użytą w dowodzie <math>\displaystyle \cc{MAXSNP}</math>-zupełności problemu MAX<math>\displaystyle 3</math>SAT.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| W dowodzie <math>\displaystyle \cc{MAXSNP}</math>-zupełności problemu MAX<math>\displaystyle 3</math>SAT pokazaliśmy, że na każdy problem <math>\displaystyle A</math> z klasy <math>\displaystyle \cc{MAXSNP}_0</math> można patrzeć jak na problem MAX<math>\displaystyle k</math>FSAT dla pewnego <math>\displaystyle k</math>. Tymczasem pokazaliśmy wcześniej, że problem MAX<math>\displaystyle k</math>FSAT może być aproksymowany ze stałą <math>\displaystyle \frac{1}{2^k}</math>, co przenosi się bezpośrednio na taką samą aproksymację dla problemu <math>\displaystyle A</math>.</div>
| |
