375 lines
22 KiB
TeX
375 lines
22 KiB
TeX
\section{26.01.2013 kolokwium \#2}
|
|
|
|
\task{Alicja i Bogdan wybrali się na zakupy. Przy kasie okazało się, że muszą zapłacić równo 100 zł, a kasa nie zwraca reszty. W portfelu mają: $a_1$ monet 1-złotowych, $a_2$ monet 2-złotowych i analogicznie dla nominałów 5, 10, 20, 50, gdzie $a_i \geq 0$. Zastanawiają się, czy z posiadanych monet mogą uzbierać dokładnie 100 zł.}
|
|
|
|
\subtask{Spróbuj zaprojektować algorytm wielomianowy dla tego problemu decyzyjnego}
|
|
\subtask{Jeśli nie potrafisz, to spróbuj udowodnić jego \NP-zupełność}
|
|
|
|
\begin{solution}
|
|
Przy rozwiązywaniu tego zadania, jedną z pierwszych myśli może być, że jest to problem zbliżony
|
|
do problemu sumy podzbioru - i jest to prawdą, jest to specyficzny wypadek problemu sumy podzbioru.
|
|
|
|
Zauważmy jednak, że do dyspozycji mamy tylko i wyłącznie 6 wartości: 1, 2, 5, 10, 20, 50 oraz, że $n$ jest stałe i wynosi $100$.
|
|
Łatwo zauważyć, że istnieją bardzo proste przypadki, które rozwiązują nasz problem. Przykładowo, jeżeli mamy 2 bankonoty 50zł to
|
|
jesteśmy w stanie zapłacić 100zł bez problemu, tak samo mając 5 banknotów 20zł czy nawet 100 złotówek.
|
|
|
|
\begin{table}[H]
|
|
\begin{tabular}{rrrrrr}
|
|
1zł & 2zł & 5zł & 10zł & 20zł & 50zł \\ \hline
|
|
- & - & - & - & - & 2 \\
|
|
- & - & - & 1 & 2 & 1 \\
|
|
- & - & - & 3 & 1 & 1 \\
|
|
- & - & 2 & 2 & 1 & 1 \\
|
|
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots
|
|
\end{tabular}
|
|
\centering
|
|
\caption{Możliwe kombinacje tworzące 100zł}
|
|
\end{table}
|
|
|
|
Stąd wynika, że istnieje jedynie skończona ilość kombinacji, którymi możemy utworzyć 100zł. Wystarczy zatem sprawdzić
|
|
je wszystkie, a to można wykonac zawsze w tym samym czasie - uzyskany algorytm jest $O(1)$.
|
|
\end{solution}
|
|
|
|
\task
|
|
Ty masz graf 100-wierzchołkowy $G$ zapisany w postaci macierzy sąsiedztwa $A(G)$ i bardzo Ci zależy na tym,
|
|
aby stwierdzić, czy $G$ zawiera klikę $K_{10}$ lub większą. Ja mam program, który rozwiązuje Twój problem, ale tylko
|
|
wtedy kiedy na wejście poda się mu macierz sąsiedztwa grafu niehamiltonowskiego. Jak przerobisz macierz $A(G)$
|
|
byś mógł skorzystać z mojego programu? Zaprojektuj taki program i oszacuj jego złożoność.
|
|
|
|
\begin{solution}
|
|
Nasz graf $G$ może być w zasadzie dowolnym grafem 100-wierzchołkowym, w szczególności nie wiemy nic o tym czy jest
|
|
hamiltonowski czy nie. Do dyspozycji mamy program, który jest w stanie odpowiedzieć na nasze pytanie,
|
|
ale tylko jeżeli graf \textbf{nie} jest hamiltonowski. Potrzebujemy zatem sposobu na przetworzenie naszego grafu $G$ tak,
|
|
aby nie miał szans być hamiltonowski - jednak to przekształcenie nie może wpływać na odpowiedź na nasze pytanie.
|
|
|
|
Na wstępie przypomnijmy, że graf hamiltonowski to taki, w którym istnieje cykl pozwalający przejść po
|
|
wszystkich wierzchołkach dokładnie raz. Co znaczy, że każdy graf hamiltonowski musi być przede wszystkim grafem spójnym.
|
|
Co za tym idzie, jeżeli przekształcimy nasz graf G w taki sposób, że nie będzie spójny to będziemy mieli pewność,
|
|
że nie będzie hamiltonowski.
|
|
|
|
Nie możemy usuwać ani dodawać krawędzi między wierzchołkami naszego grafu $G$, ponieważ mogłoby to wpłynąć na istnienie
|
|
w nim kliki - najprostszym rozwiązaniem będzie więc dodanie zupełnie nowego wierzchołka, nazwijmy go $v_{101}$,
|
|
który nie jest połączony z żadnym innym.
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{gfx/hamilton.tex}
|
|
\caption{Transformacja w graf niehamiltonowski}
|
|
\end{figure}
|
|
|
|
Dodanie jednego swobodnego wierzchołka nie wpłynie na istnienie kliki $K_{10}$ bądź większej ponieważ jeden wierzchołek
|
|
nie wystarczy na utworzenie kliki, a nie dodajemy żadnych krawędzi, które mogłyby doprowadzić do tego, że klika nagle powstała.
|
|
|
|
Innym możliwym rozwiązaniem jest dodanie wierzchołka połączonego z tylko jednym wierzchołkiem - jedyny sposób aby się
|
|
do niego dostać będzie przez 1 wierzchołek, a żeby przejść dalej będziemy musieli się cofnąć do wierzchołka, w którym już byliśmy.
|
|
|
|
Jeżeli zaś chodzi o złożoność, to ważnym jest, że graf jest podany w formie macierzy sąsiedztwa, czyli aby dodać
|
|
wierzchołek musimy do macierzy dodać 1 wiersz i 1 kolumnę - czyli w zasadzie utworzyć nową macierz. Operacja ta wymaga
|
|
utworzenia $(n+1) \times (n+1)$ komórek, czyli teoretycznie jej złożoność to $O(n^2)$ jednak biorąc pod uwagę, że dla
|
|
grafu $G$ z definicji $n = 100$ możemy powiedzieć, że operacja ta dla każdego takiego grafu G jest do wykonania w czasie
|
|
stałym, czyli $O(1)$ - obie odpowiedzi będą poprawne.
|
|
\end{solution}
|
|
|
|
\task{\textit{Ograniczony Problem Kliki} - \problem{OPK} - zdefiniowany jest następująco: ,,Dany jest graf $G$ i liczby
|
|
naturalne $a$, $b$ takie, że $a \leq b$, czy w $G$ istnieje klika o rozmiarze $r$ taka, że $a \leq r \leq b$?''. Pokaż, że:}
|
|
\subtask{$\problem{OPK} \in \problem{NP}$}
|
|
\subtask{$\problem{OPK} \in \problem{NPC}$}
|
|
|
|
\begin{solution}
|
|
Aby udowodnić, że dany problem należy do klasy \NP należy zrobić jedną z dwóch rzeczy - przedstawić niedeterministyczny
|
|
algorytm rozwiązujący ten problem w czasie wielomianowym, bądź zaprezentować wielomianowy algorytm sprawdzający
|
|
rozwiązanie tego problemu. Moim zdaniem, podejście drugie jest o wiele łatwiejsze i przyjemniejsze - zatem to właśnie
|
|
je zaprezentuję i będę wykorzystywał.
|
|
|
|
Aby sprawdzić rozwiązanie, potrzebujemy więcej informacji niż proste \textbf{tak} lub \textbf{nie} - taką dodatkową
|
|
informację nazywamy \textit{certyfikatem}, przykładowo w wypadku pytania, czy liczba $n$ jest złożona, certyfikatem mogą
|
|
być dwie liczby $p$ i $q$ takie, że $n = p \cdot q$ - mając taki certyfikat łatwo jest potwierdzić, że faktycznie
|
|
liczba jest złożona.
|
|
|
|
W naszym wypadku certyfikatem może być lista wierzchołków tworząca klikę $K_n$. Określenie $r$ będzie wymagało
|
|
sprawdzenia długości listy, co z pewnością można wykonać w czasie wielomianowym, a sprawdzenie czy wierzchołki tworzą
|
|
klikę będzie wymagało sprawdzenia czy faktycznie każdy wierzchołek sąsiaduje z każdym innym wierzchołkiem z listy - co
|
|
też można wykonać w czasie wielomianowym. Stąd wynika, że problem należy do klasy \NP.
|
|
|
|
Dowód, że problem należy do \NPC jest trochę trudniejszy do przeprowadzenia - należy mianowicie wykonać
|
|
$\alpha$-redukcję jakiegoś problemu, który wiemy że jest \NPC do problemu, który badamy. Naturalnym kandydatem tutaj
|
|
wydaje się być problem kliki:
|
|
``Czy w grafie $G$ istnieje klika wielkości $n$?,,
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{./gfx/klika-opk.tex}
|
|
\caption{schemat $\alpha$-redukcji \problem{kliki} do \problem{OPK}}
|
|
\end{figure}
|
|
|
|
Aby dokonać $\alpha$-redukcji musimy w wielomianowym czasie na podstawie danych $G, n$ znaleźć takie $G_1, a, b$ aby
|
|
rozwiązując problem \problem{OPK} uzyskać odpowiedź na problem kliki. Wiemy, że \problem{OPK} zwróci nam prawdę jeżeli
|
|
w grafie $G_1$ będzie klika o rozmiarze $r$ takim, że $a \leq r \leq b$. Jeżeli chcemy znaleźć klikę konkretnego
|
|
rozmiaru, wystarczy zauważyć, że jeżeli $a = b \land A \leq r \leq b$ to $a = b = r$. Nasza $\alpha$-redukcja mogłaby
|
|
zatem wyglądać następująco: $G_1 = G, a = n, b = n$. Co z pewnością możemy dokonać w czasie wielomianowym. Fakt, że
|
|
takie podstawienie zachowuje problem udowodniliśmy już powyżej.
|
|
\end{solution}
|
|
|
|
\task{\textit{Problem zanurzenia} (\problem{PZ}) grafu w innym grafie zdefiniowany jest następująco. Dane są dwa grafy:
|
|
$(G, H)$, gdzie $G$ jest \textit{gościem} a $H$ - \textit{gospodarzem}. Czy istnieje takie odwzorowanie wierzchołków
|
|
$f: V(G) \to V(H)$, że każdej krawędzi $\{u, v\} \in G$ odpowiada krawędź $\{f(u), f(v)\} \in H$? Pokaż, że PZ jest
|
|
problemem NP-zupełnym.}
|
|
|
|
\begin{solution}
|
|
Przed dowiedzeniem, że problem jest \NPC najpierw musimy udowodnić, że w ogóle znajduje się w klasie \NP. Po raz
|
|
kolejny wykorzystamy tutaj podejście z certyfikatem, w tym wypadku będzie nim funkcja $f$. Nie rozważamy tutaj tego
|
|
jak trudno jest wyliczyć na komputerze wynik działania funkcji $f$, zatem zakładamy, że $f = O(1)$. Przetworzenie
|
|
wszystkich krawędzi można zatem wykonać w czasie $O(m(G))$. Aby sprawdzić czy krawędź istnieje w grafie $H$ w
|
|
najgorszym wypadku musimy przejrzeć wszystkie krawędzie - co daje nam czas $O(m(H))$, ponieważ dla każdej przetworzonej
|
|
krawędzi w $G$ musimy sprawdzić jej istnienie w $H$ to w najgorszym wypadku uzyskamy czas
|
|
$O(m(H) \cdot m(G))$ - czyli wielomianowy.
|
|
|
|
Aby udowodnić, że \problem{PZ} jest \NPC musimy znaleźć $\alpha$-redukcje jakiegoś innego, najlepiej zbliżonego
|
|
problemu do \problem{PZ}. Na początek zauważmy, że $f$ musi być funkcją różnowartościową, ponieważ gdyby nie była, to
|
|
istniałyby takie $u_1 \neq u_2$, że $f(u_1) = f(u_2) = v$, co dawałoby nieistniejącą krawędź $\{ v, v \}$
|
|
(tj. wierzchołek byłby połączony z samym sobą). Gdybyśmy natomiast rozpatrywali grafy mogące zawierać takie pętle
|
|
własne, to problem dla takich grafów oraz funkcji nieróżnowartościowej stawałby się trywialny - wystarczyłoby zmapować
|
|
wszystkie wierzchołki na ten jeden z pętlą własną i taka funkcja istniałaby zawsze.
|
|
|
|
Z tego, że $f$ jest różnowartościowa wynika, że jeżeli wierzchołek w grafie G $\deg u = \delta$ to w grafie H
|
|
$\deg f(u) \geq \delta$. Można to zaobserwować na rysunku poniżej.
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{gfx/mapowanie.tex}
|
|
\caption{Powiązane wierzchołki mają ten sam kolor w obu grafach.}
|
|
\end{figure}
|
|
|
|
Biorąc pod uwagę ten tok rozumowania, możemy zauważyć że problem ten jest nam w stanie łatwo odpowiedzieć czy w danym
|
|
grafie $H$ występuje podgraf $G$. Znanym problemem \NPC, który wymaga sprawdzenia obecności danego podgrafu w innym
|
|
grafie jest oczywiście problem kliki.
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{./gfx/klika-pz.tex}
|
|
\caption{schemat $\alpha$-redukcji kliki do PZ}
|
|
\end{figure}
|
|
|
|
$\alpha$-redukcja polega na sprawdzeniu czy graf pełny $K_n$ jest podgrafem grafu $G_0$, czyli dla problemu \problem{PZ}
|
|
otrzymalibyśmy tak skonstruowane dane wejściowe:
|
|
$G = K_n, H = G_0$.
|
|
|
|
Problem jest zachowany ponieważ jeżeli w grafie $G_0$ występuje klika o rozmiarze $n$ to możemy każdemu wierzchołkowi
|
|
kliki znalezionej w $G_0$ przypisać unikalny wierzchołek w $K_n$. W drugą stronę analogicznie, jeżeli istnieje takie
|
|
przypisanie to w grafie $G_0$ musi znajdować się klika $K_n$.
|
|
\end{solution}
|
|
|
|
\task{Przedyskutuj złożoność obliczeniową następujących problemów decyzyjnych, zakładając, że $G$ jest kubiczny
|
|
(tj. 3-regularny) i zapamiętany jest w postaci list sąsiedztwa. Ponadto, jeżeli odpowiedź jest oczywista napisz czy
|
|
brzmi ona \textbf{tak} lub \textbf{nie}.}
|
|
|
|
\begin{minipage}{.5\linewidth}
|
|
\subtask{$\chi(X) \leq 1$}
|
|
\subtask{$\chi(X) \leq 2$}
|
|
\subtask{$\chi(X) \leq 3$}
|
|
\subtask{$\chi(X) \leq 4$}
|
|
\end{minipage}%
|
|
\begin{minipage}{.5\linewidth}
|
|
\subtask{$\chi(X) \geq 1$}
|
|
\subtask{$\chi(X) \geq 2$}
|
|
\subtask{$\chi(X) \geq 3$}
|
|
\subtask{$\chi(X) \geq 4$}
|
|
\end{minipage}%
|
|
\\
|
|
\tip{Skorzystaj z twierdzenia Brooksa, które mówi, że $\chi(G) \leq \Delta$ za wyjątkiem
|
|
$G = C_{2k-1}$ (czyli będącego cyklem nieparzystym i $G = K_n$)}
|
|
|
|
\begin{solution}
|
|
Problem dotyczy liczby chromatycznej grafu - $\chi(G)$ - czyli minimalnej liczby kolorów potrzebnej do poprawnego
|
|
pokolorowania grafu. Graf można pokolorować 1 kolorem $\chi(G) = 1$, tylko wtedy kiedy nie ma on krawędzi, a tym wypadku
|
|
wiemy, że graf jest 3-regularny czyli dla każdego wierzchołka $v \in G$ wiemy, że jest połączony z 3 innymi
|
|
wierzchołkami - stąd możemy wywnioskować, że dla tego typu grafów $\chi(G) \geq 2$.
|
|
|
|
Dodatkowo wiemy, że każdy graf dwudzielny można pokolorować za pomocą dokładnie 2 kolorów ponieważ zawiera 2 grupy
|
|
niepołączonych ze sobą wierzchołków - a sprawdzenie dwudzielności grafu można osiągnąć za pomocą BFS-a lub DFS-a,
|
|
czyli w złożoności $O(m+ n)$.
|
|
|
|
Z wskazówki znamy twierdzenie Brooksa - $\chi(G) \leq \Delta$, w naszym wypadku z 3-regularności oczywistym jest, że
|
|
$\Delta = 3$, czyli $\chi(G) \leq 3$, \textbf{CHYBA, że} graf jest nieparzystym cyklem - co możemy wyeliminować ponieważ
|
|
cykl nie jest 3-regularny, lub $G = K_4$, gdzyż klika rozmiaru 4 jest 3-regularna (Ogólnie kliki rozmiaru $n$
|
|
są $(n - 1)$-regularne) i tylko w tym jednym wypadku będziemy potrzebować 4 kolorów, ale nigdy więcej.
|
|
|
|
Zatem podsumowując odpowiedzi:
|
|
|
|
\begin{enumerate}[a)]
|
|
\item $\chi(X) \leq 1$ - \textbf{NIE}
|
|
\item $\chi(X) \leq 2$ - sprawdzenie dwudzielności - $O(n + m)$
|
|
\item $\chi(X) \leq 3$ - sprawdzenie czy $G \neq K_4$ - $O(1)$
|
|
\item $\chi(X) \leq 4$ - \textbf{TAK}
|
|
\item $\chi(X) \geq 1$ - \textbf{TAK} - zawsze potrzebny jest minimum 1 kolor
|
|
\item $\chi(X) \geq 2$ - \textbf{TAK} - minimalna liczba potrzebnych kolorów dla takiego grafu to 2
|
|
\item $\chi(X) \geq 3$ - jeżeli graf nie jest dwudzielny - to na pewno potrzebuje minimum 3 kolorów - $O(n+m)$
|
|
\item $\chi(X) \geq 4$ - graf potrzebuje 4 kolorów tylko, gdy jest kliką $K_4$ - $O(1)$.
|
|
\end{enumerate}
|
|
\end{solution}
|
|
|
|
\task{\NP-trudny problem \textit{Maximum Acyclic Subgraph} (\problem{MAS}) pyta o maksymalny zbiór łuków digrafu $D$,
|
|
który generuje digraf acykliczny. Problem ten ma prosty algorym 2-aproksymacyjny, który polega na podzieleniu $D$ na dwa podgrafy.}
|
|
|
|
\subtask{udowodnij 2-aproksymowalność tego algorytmu}
|
|
\subtask{udowodnij nie wprost, że jeżeli $\mathtt{P} \neq \mathtt{NP}$ to dla \problem{MAS} nie ma schamatu FPTAS}
|
|
\\
|
|
\tip{Zakładamy, że digraf $D$ dany jest w postaci macierzy sąsiedztwa $A$}
|
|
\tip{Jaki digraf definiuje górna/dolna macierz trójkątna macierzy $A$?}
|
|
|
|
\begin{solution}
|
|
Na wstępie - zadanie słabo opisuje problem i więcej informacji można wyciągnąć z nazwy problemu po angielsku niż jego opisu.
|
|
W problemie chodzi o znalezienie największego podgrafu acyklicznego w digrafie $D$.
|
|
\begin{figure}[H]
|
|
\begin{minipage}{.5\linewidth}%
|
|
\centering
|
|
\input{./gfx/mas-1.tex}
|
|
\end{minipage}%
|
|
\begin{minipage}{.5\linewidth}%
|
|
\begin{equation*}
|
|
A_D = \begin{bmatrix}
|
|
0 & 1 & 0 & 0 & 1 \\
|
|
0 & 0 & 1 & 0 & 0 \\
|
|
1 & 0 & 0 & 0 & 1 \\
|
|
0 & 0 & 1 & 0 & 0 \\
|
|
0 & 0 & 0 & 1 & 0 \\
|
|
\end{bmatrix}
|
|
\end{equation*}
|
|
\end{minipage}%
|
|
\caption{Przykładowy digraf $D$ wraz z maksymalnym podgrafem acyklicznym oraz macierzą sąsiedztwa.}
|
|
\end{figure}
|
|
|
|
Z zadania wiemy, że algorytm dzieli digraf $D$ na dwie części, na podstawie wskazówki \#1 możemy się domyślać, że ma to
|
|
coś wspólnego z macierzami trójkątnymi macierzy $A_D$. Zobaczmy, co te macierze reprezentują:
|
|
\begin{figure}[H]
|
|
\begin{minipage}{.5\linewidth}%
|
|
\centering
|
|
\input{./gfx/mas-2.tex}
|
|
\end{minipage}%
|
|
\begin{minipage}{.5\linewidth}%
|
|
\begin{equation*}
|
|
A_D = \begin{bmatrix}
|
|
0 & 1 & 0 & 0 & 1 \\
|
|
& 0 & 1 & 0 & 0 \\
|
|
& & 0 & 0 & 1 \\
|
|
& & & 0 & 0 \\
|
|
& & & & 0 \\
|
|
\end{bmatrix}
|
|
\end{equation*}
|
|
\end{minipage}%
|
|
\caption{Graf opisany przez macierz trójkątną górną macierzy $A_D$}
|
|
\end{figure}
|
|
|
|
\begin{figure}[H]
|
|
\begin{minipage}{.5\linewidth}%
|
|
\centering
|
|
\input{./gfx/mas-3.tex}
|
|
\end{minipage}%
|
|
\begin{minipage}{.5\linewidth}%
|
|
\begin{equation*}
|
|
A_D = \begin{bmatrix}
|
|
0 & & & & \\
|
|
0 & 0 & & & \\
|
|
1 & 0 & 0 & & \\
|
|
0 & 0 & 1 & 0 & \\
|
|
0 & 0 & 0 & 1 & 0 \\
|
|
\end{bmatrix}
|
|
\end{equation*}
|
|
\end{minipage}%
|
|
\caption{Graf opisany przez macierz trójkątną dolną macierzy $A_D$}
|
|
\end{figure}
|
|
|
|
Jak widać górna macierz trójkątna opisuje tylko takie krawędzie (łuki) $(u_1, u_2)$ że $u_1 < u_2$, czyli nie może
|
|
wystąpić cykl ponieważ to wymagałoby powrotu do wierzchołka, który już rozpatrywaliśmy - a to jest niemożliwe w takiej
|
|
macierzy. W macierzy dolnej sytuacja jest analogiczna, z tym że zachodzi warunek $u_1 > u_2$.
|
|
|
|
Rozwiązanie takie gwarantuje brak cyklu, jednak nie jest dokładne, zastanówmy się więc jaki może być najgorszy przypadek.
|
|
Biorąc pod uwagę, że bierzemy połowę grafu możemy być pewni, że algorytm nie pomyli się bardziej niż 2-krotnie, ponieważ
|
|
w najgorszym wypadku cały graf jest już acykliczny, a my bierzemy jego połowę. Nie mamy jednak pewności co do tego,
|
|
czy faktycznie może istnieć acykliczny graf dokładnie 2 krotnie większy od swojej połówki i prawdopodobnie na tym można
|
|
skończyć dowód, jednak udowodnijmy że faktycznie istnieje taki przypadek w którym algorytm zwróci dokładnie
|
|
2-przybliżony.
|
|
|
|
Aby uzyskać taki graf w dolnej i górnej macierzy trójkątnej musimy mieć dokładnie taką samą ilość krawędzi, a ponadto
|
|
graf musi pozostać acykliczny. Nie jesteśmy w stanie stworzyć grafu o 2 wierzchołkach, który spełniałby ten warunek,
|
|
ponieważ albo algorytm zwróci odpowiedź dokładną, albo graf będzie cykliczny tj. wierzchołek 1 będzie połączony z 2 oraz
|
|
2 z 1. Jesteśmy w stanie skonstruować jednak taki graf 3 wierzchołkowy, ponieważ wystarczy że będziemy mieli dokładnie
|
|
jedno połączenie wierzchołka ,,mniejszego'' z ,,większym'' oraz dokładnie jedno ,,większego'' z ,,mniejszym'' przy czym jedynym
|
|
ograniczeniem jest to, że nie mogą to być te same wierzchołki.
|
|
|
|
\begin{figure}[H]
|
|
\begin{minipage}{.5\linewidth}%
|
|
\centering
|
|
\input{./gfx/mas-4.tex}
|
|
\end{minipage}%
|
|
\begin{minipage}{.5\linewidth}%
|
|
\begin{equation*}
|
|
A_D = \begin{bmatrix}
|
|
0 & 1 & 0 \\
|
|
0 & 0 & 0 \\
|
|
0 & 1 & 0 \\
|
|
\end{bmatrix}
|
|
\end{equation*}
|
|
\end{minipage}%
|
|
\caption{Graf opisany przez macierz trójkątną dolną macierzy $A_D$}
|
|
\end{figure}
|
|
|
|
W tym wypadku digraf $D$ jest acykliczny, jednak algorytm będzie w stanie znaleźć tylko podgraf $\{ (1, 2) \}$
|
|
lub $\{ (1, 3) \}$, czyli zwróci 2-krotnie za mały wynik.
|
|
|
|
Istnienie schematu (F)PTAS mówi nam, że jesteśmy w stanie znaleźć wielomianowy algorytm o dowolnie dobrym przybliżeniu,
|
|
tj. algorytm $(1 + \varepsilon)$-aproksymacyjny, gdzie $\varepsilon > 0$. Znalezienie takiego schematu jest trudne i jak
|
|
mniemam wykraczające poza obszar przedmiotu a na pewno kolokwium, jednak stosunkowo prosto udowodnić, że taki schemat
|
|
nie może istnieć. Wystarczy udowodnić, że dla każdych możliwych danych wejściowych istnieje taki epsilon, że z
|
|
odpowiedzi przybliżonej jesteśmy w stanie ze 100\% pewnością wywnioskować odpowiedź dokładną - a to znaczyłoby, że
|
|
posiadamy wielomianowy algorytm rozwiązujący dany problem \NP-trudny dokładnie, co znaczyłoby, że $\P = \NP$
|
|
|
|
W tym wypadku rozważamy problem maksymalizacyjny, czyli wiemy że odpowiedź dokładna $N_\text{opt}$ jest większa bądź
|
|
równa od odpowiedzi naszego algorytmu $N$:
|
|
\begin{equation}
|
|
N_{\text{opt}} \geq N
|
|
\end{equation}
|
|
|
|
Co za tym idzie, z definicji przybliżalności wynika, że:
|
|
\begin{equation*}
|
|
\frac{N_{\text{opt}}}{N} \leq 1+\varepsilon \iff N_\text{opt} \leq N(1 + \varepsilon)
|
|
\end{equation*}
|
|
|
|
łącząc te dwie wiadomości możemy wywnioskować, że
|
|
\begin{equation}
|
|
\label{eqn:2013:fptas}
|
|
N \leq N_\text{opt} \leq N + N\varepsilon
|
|
\end{equation}
|
|
|
|
ponieważ wiemy, że liczba krawędzi w grafie jest zawsze liczbą naturalną ($N_\text{opt} \in \mathbb{N}$ oraz $N \in \mathbb{N}$),
|
|
wystarczy że w nierówności \ref{eqn:2013:fptas} będzie spełniony warunek
|
|
\begin{equation}
|
|
\label{eqn:2013:fptas-condition}
|
|
N\varepsilon < 1
|
|
\end{equation}
|
|
|
|
A uzyskamy
|
|
\begin{equation*}
|
|
N \leq N_\text{opt} \leq N + N\varepsilon \Rightarrow N \leq N_\text{opt} \leq N
|
|
\end{equation*}
|
|
\begin{equation*}
|
|
N_\text{opt} = N
|
|
\end{equation*}
|
|
czyli algorytm zwróci nam odpowiedź dokładną.
|
|
|
|
Należy więc udowodnić że dla każdych danych wejściowych jesteśmy w stanie znaleźć dostatecznie mały $\varepsilon$,
|
|
który spowoduje że nasza odpowiedź będzie dokładna. Aby tego dokonać ograniczmy przybliżoną odpowiedź algorytmu z
|
|
dołu. Oczywistym jest, że w grafie o $m$ krawędziach nie będzie grafu o ilości krawędzi $N$ większej niż $m$, a już
|
|
na pewno większej niż $m+1$:
|
|
\begin{equation*}
|
|
N < m + 1
|
|
\end{equation*}
|
|
|
|
Jeżeli teraz przedzielimy obie strony nierówności przez $m + 1$ uzyskamy po prawej stronie 1, dokładnie tak jak w nierówności \ref{eqn:2013:fptas-condition}
|
|
\begin{equation*}
|
|
\frac{1}{m+1}N < 1
|
|
\end{equation*}
|
|
|
|
a co za tym idzie wystarczy, że $\varepsilon < \frac{1}{m+1}$ a będziemy w stanie wywnioskować dokładny wynik w czasie wielomianowym, co jest możliwe tylko gdy $\P = \NP$.
|
|
\end{solution}
|