\section{`Harte' Probleme} \subsection{Typische Problemklassen} \inhalta{9-15} \inhaltb{15} \begin{frame} Grundform einer algorithmischen Aufgabenstellung: \begin{itemize} \item i.d.R. nicht als Entscheidungsproblem\pause \item sondern sondern als \Fb{funktionales Problem} (oder Suchproblem)\pause \Fb{ Gegeben $x$, bestimme eine ,,Lösung'' $y$, falls eine solche existiert.} \end{itemize}\pause $y$ ist dabei i.d.R. Resultat der Guess-Phase bei Guess-and-Check \pause\\ und kann schnell überprüft werden\pause\\ (Bsp: Variaben-Belegung, Isomorphismus, Färbung,...)\pause Wichtig auch: Bei nichtdeterministischen Algorithmen ist es nicht gleichgültig, ob man \begin{itemize} \item die Existenz einer Lösung zeigen will oder \pause \item aber zeigen will, dass gar keine Lösung existiert \end{itemize} \end{frame} \begin{frame} \begin{definition} Zu einem Problem $K$ aus einer Grundmenge $M$ sei co-$K:=M\setminus K$.\pause Die Problemklasse co-NP besteht aus allen Problemen $K$, für die co-$K$ in NP liegt. \end{definition} \pause Es ist noch unbekannt, ob co-NP=NP gilt (vermutlich nicht...)\pause \begin{itemize} \item Unbekannt ist z.B. ob co-SAT in NP liegt\pause (Wie soll man durch Raten feststellen, dass z.B. keine erfüllende Belegung existiert?) \pause \item Bei deterministischen Entscheidungsalgorithmen kann man das Resultat einfach negieren, d.h. co-P=P. \end{itemize} \end{frame} \begin{frame} weitere Form: \Fb{Optimierungsprobleme}\pause \begin{itemize} \item\Fb{ Zu Eingabe bestimme Lösung, die eine gegebene Kostenfunktion maximiert (oder minimiert)} \end{itemize} \pause Bei NP-vollständigen Problemen:\pause \begin{itemize} \item funktionales Problem oder Optimierungsproblem auf Entscheidungsproblem polynomial ``reduzierbar''\pause \item gibt es polynomialen Algorithmus für das Entscheidungsproblem,\\ so auch für das funktionale oder Optimierungsproblem \end{itemize} \pause Entscheidungsprobleme für Theorie ausreichend\\\pause (aber nicht für Praxis: hier genauere Betrachtung notwendig...) \end{frame} \begin{frame} Optimierungsprobleme werden spezifiziert durch:\pause \begin{itemize} \item die Menge der zulässigen Eingaben \pause \item die zulässigen Lösungen $S(x)$ für zulässige Eingaben $x$\pause \item eine Bewertungsfunktion $v$, die Lösungen $y$ mit $v(y)$ bewertet. \end{itemize} \pause Jede der drei Komponenten sollte polynomiale Komplexität haben: \pause \begin{itemize} \item Zulässigkeit sollte mit polynomialer Komplexität überprüfbar sein!\pause \item $y\in S(x)$ sollte in polynomialer Komplexität entscheidbar sein.\pause \item $v$ sei in polynomialer Komplexität berechenbar. \end{itemize} \pause Optimierungsprobleme sind gegliedert in\pause \begin{itemize} \item Minimierungsprobleme:\pause\\ suche Lösung $y \in S(x)$ mit $v(y) = min\{v(s) \mid \in S(x)\}$. \pause \item Maximierungsprobleme:\pause\\ suche analog Lösung mit maximalem $v$-Wert \end{itemize} \end{frame} \begin{frame} \begin{example} {\bfseries Traveling Salesman Problem} (TSP) als Minimierungsproblem:\pause \begin{itemize} \item zulässige Eingaben: $n\times n$ Entfernungsmatrix $M = (m_{i,j})$\pause\\ (Abstände/Kosten zuje zwei Städten $i$ und $j$, $(i, j\in\{1,\dots,n\}$)\pause \item Erlaubt: Einträge mit Wert $\infty$\pause \\(keine direkte Straßenverbindung zwischen Ort $i$ und Ort $j$)\pause \item zulässige Lösungen sind Permutationen $\pi$ auf $\{1, 2,\ldots, n\}$\pause (repräsentieren Rundreise durch alle Städte)\pause\\ zulässige Rundreise müssen ohne $\infty$-Einträge auskommen\pause \item Bewertung $v$ einer zulässigen Permutation $\pi$ für $M$ \pause ist definiert als $$v(\pi)=\sum_{k=1}^{n-1}m_{\pi(k),\pi(k+1)} + m_{\pi(n),\pi(1)}$$\pause \item O.B.d.A. betrachte nur Permutationen $\pi$ mit $\pi(1) = 1$. \end{itemize} \pause Ziel: {\bfseries Suche $\pi$ mit minimalen Gesamtkosten $v(\pi)$} \end{example} \end{frame} \begin{frame} \begin{example} {\bfseries MaxSAT} als Maximierungsproblem: \pause \begin{itemize} \item Gegeben: eine {\em Menge} $F$ von Klauseln,\pause\\ gesucht: eine Belegung, die möglichst viele Klauseln erfüllt.\pause \item Zulässige Eingaben: syntaktisch korrekte Klauselmengen.\pause \item Jede Belegung $\Phi$ der Variablen ist zulässige Lösung! \pause \item Bewertung $v(\Phi)=$ Anzahl der durch $\Phi$ erfüllten Klauseln \end{itemize}\pause Beispiel: $$F=\{(x_1\vee x_2\vee x_3),(\neg x_2\vee x_3), \neg x_1, \neg x_2, \neg x_3\}$$ \pause mit (nicht-eindeutiger aber) optimaler Lösung $$\Phi: x_1\mapsto 1, x_2\mapsto 0, x_3\mapsto 0$$ und $v(\Phi)=4$. \end{example} \end{frame} \begin{frame} Umwandlung vom Optimierungs- zum Entscheidungsproblem:\pause \begin{itemize} \item natürliche Zahl $k$ als weiterer Bestandteil der Eingabe,\pause\\ d.h. Eingaben sind $$\{ (x,k) \mid x \mbox{ ist zulässig, } k\in\nz\}$$\pause \item gesucht: Gibt es Lösung der Güte $k$ oder besser? \end{itemize} \pause Bei Minimierungsproblemen lautet das Entscheidungsproblem also: \pause \begin{itemize} \item Ist zu $(x,k)$ die Menge $\{ y\in S(x)\mid v(y)\leq k\}$ nichtleer? \end{itemize} \end{frame} \begin{frame} weitere Form: \Fb{Zählprobleme}\pause \begin{itemize} \item Zu Eingabe bestimme genaue Anzahl der Lösungen \end{itemize} \pause Für NP-vollständige Probleme sind die Zählprobleme wohl schwieriger als die Entscheidungsprobleme!\pause Andererseits beim Graphenisomorphieproblem: \pause \begin{itemize} \item Aus fiktiven polynomialen Entscheidungsalgorithmus würde polynomialer Algorithmus für das Zählproblem (ohne Beweis...) \pause \item daher Vermutung: Graphenisomorphieproblem ist evtl. nicht NP-vollständig... \end{itemize} \end{frame} \begin{frame} Im Folgenden: Algorithmen für NP-vollständige Probleme \pause \begin{itemize} \item insbesondere für Traveling Salesman Problem und Erfüllbarkeitsproblem als Beispiele \end{itemize} \pause Algorithmen für exakte Lösungen (für funktionales oder Optimierungsproblem) haben (derzeit) exponentielle Laufzeit \pause Daher folgende Möglichkeiten:\pause \begin{itemize} \item Suche nach exakten Algorithmen, die zumindest besser sind als naive Suche\pause \item Suche nach polynomialen Algorithmen, die akzeptable Näherungslösungen berechnen\pause \item Benutze dabei insbesondere Zufallszahlen als Hilfsmittel \end{itemize} \end{frame} \subsection{Exakte Verfahren} \subsubsection{Dynamisches Programmieren} \inhaltb{15} \begin{frame} Bekannt: {\bf Divide and Conquer}\pause \begin{itemize} \item \emph{Top-Down}-Verfahren\pause \item Zerlege Problem in Teilprobleme, die getrennt gelöst werden\pause \item Einfaches Zusammensetzen der Teillösungen\pause \item Wichtig für Komplexität: Unabhängigkeit der Teilprobleme\pause \item Parade-Beispiel: Quicksort\pause \item Negativ-Beispiel: Fibonacci-Zahlen \end{itemize} \pause Jetzt: {\bf Dynamisches Programmieren}\pause \begin{itemize} \item \emph{Bottom-Up}-Verfahren\pause \item Löse erst triviale Probleme\pause \item Setze Teillösungen zu größeren Lösungen zusammen\pause \item Wichtig für Algorithmus: Speicherung der Teillösungen!\pause \item Bereits bekannt: CYK-Algorithmus für kontextfreie Grammatiken \end{itemize} \end{frame} \begin{frame} Beispiel: {\bfseries TSP}\pause Naiver Algorithmus: \pause \begin{itemize} \item Untersuche alle Permutationen (d.h. $\Omega(n!)$ )...\pause \item Triviale Verbesserung: Starte immer in Stadt $1$ (d.h. $\Omega((n-1)!)$ ) \end{itemize} \pause Laufzeit (geschätzt, bei 1.000.000 Permutationen pro Sekunde): \pause $$\begin{array}{c|r} n&\mbox{Zeit}\\\hline 10& 0.3~ s\\ 11& 3.6~ s\\ 12& 40~ s \\ 13& 8~ m \\ 14& 1~ h~ 43~ m \\ 15& 1~d\\ 16& 15~ d \\ 17& 240~ d\\ 18& 11~ j \\ 19&202~j \\ 20&3836~j \\ \end{array}$$ \end{frame} \begin{frame} Uminterpretation von {\bfseries TSP}:\pause \begin{itemize} \item Betrachte {\bfseries TSP} als (kantenbewerteten) Graphen\pause \item Knotenmenge $V=\{1,\ldots,n\}$\pause \item Kantenmenge $E=V\times V$, Bewertung: $m_{i,j}$ für Kante $(i,j)$ \end{itemize}\pause Teil-Lösungen für {\bfseries TSP}:\pause \begin{itemize} \item zu Knoten $i$ und $S\subset V$ setze $$g(i,S)=\begin{tabular}[t]{l} Gewicht des besten Weges von $i$ nach $1$,\\ der nur über Knoten aus $S$ führt und zudem\\\pause jeden Knoten $j\in S$ genau einmal berührt\end{tabular}$$\pause \item Dann ist $g(1,V\setminus\{1\})$ gesuchte Lösung des TSP\pause \item Rekursive Beschreibung von $g$: $$g(i,S)=\left\{\pause\begin{array}{ll} m_{i,1}& S=\emptyset\\ \pause\min_{j\in S}\left( m_{i,j} + g(j,S\setminus\{j\}\right) &\pause S\neq \emptyset\end{array}\right.$$ \end{itemize} \end{frame} \begin{frame} Beispiel: $$M=\left[\begin{array}{ccccc} 0 & 10 & 15 & 20\\ 5 & 0 & 9 & 10 \\ 6 & 13 & 0 & 12 \\ 8 & 8 & 9 & 0 \end{array}\right]$$ \[\includegraphics[width=.65\textwidth]{grafik/TSP-rekursiv.pdf}\] \pause Rekursive Implementierung $\leadsto$ `überflüssige' Auswertungen von $g$! \end{frame} \begin{frame}[fragile] `{\bfseries Dynamisches Programm}' für {\bfseries TSP}:\pause \begin{itemize} \item Bottom-Up Auswertung\pause \item Speicherung der Funktionswerte in Tabelle \end{itemize} \pause Iterativ programmiert: \begin{programm} \begin{semiverbatim}\bfseries FOR i:=2 TO n DO g[i,\(\emptyset\)]=m[i,1];\pause FOR k:=1 TO n-2 DO FOR S, |S|=k, 1\(\not\in\)S DO FOR i \(\in\)\{2,...,n\}\(\setminus\)S DO berechne g[i,S] nach Formel\pause berechne g[1,\{2,...,n\}] nach Formel \end{semiverbatim} \end{programm} \pause Aufwand: \begin{itemize} \item Speicherplatz: \pause Tabelle mit $< n\cdot 2^n$ Einträgen\pause \item Zeit: \pause(Größe der Tabelle) $ \cdot$ (Aufwand pro Eintrag), d.h. $n^2\cdot 2^n$ \end{itemize} \pause (Hilfsmittel zum Programmieren mit (kleinen) Mengen in \verb#C++# oder \verb#Java# z.B. \verb#bitset#) \end{frame} % \begin{frame}[fragile] % % rekursive Implementierung in \verb#C++# % \begin{programm} % \begin{semiverbatim}\bfseries\scriptsize % #include % #include % #include % using namespace std; % % /* Achtung: V={0,1,...,n-1} % Modifikation: Nicht pi(1)=1 sondern pi(n)=n, % damit S nur aus {0,1,...,n-2} % */ % % unsigned long formel( % unsigned int n, unsigned int m[], % unsigned int i, bitset<30> S)\{ % bitset<30> S2; % unsigned int minimum=2000000000, m2; % if (S.none()) return m[i+n*(n-1)] ; % else \{ % for (unsigned j=0; j> n; % unsigned int zpn = 1<<(n-1); % unsigned int m[n*n]; % cout << "Parameter: "<< n <<", Teilmengen: "<< zpn; % % for ( unsigned int i=0; i % #include % #include % using namespace std; % % /* Achtung: V={0,1,...,n-1} % Modifikation: Nicht pi(1)=1 sondern pi(n)=n, % damit S nur aus {0,1,...,n-2} % */ % % unsigned long formel( % unsigned int n, unsigned int m[]\Fb{, unsigned int g[]}, % unsigned int i, bitset<30> S)\{ % bitset<30> S2; % unsigned int minimum=2000000000, m2; % if (S.none()) return m[i+n*(n-1)] ; % else \{ % for (unsigned j=0; j> n; % unsigned int zpn = 1<<(n-1); % unsigned int m[n*n]\Fb{, g[n*zpn]}; % cout << "Parameter: "<< n <<", Teilmengen: "<< zpn; % % for ( unsigned int i=0; i S(iS); % if (S.count()==k) \{ % for ( unsigned int i=0; i G$ \end{itemize}\pause \item bei $n>1$ Objekten teste zwei Möglichkeiten:\pause \begin{itemize} \item Objekt $n$ gehört zu optimaler Menge $I$:\pause\\ $I$ nutzt Teil-Lösung $I'\subseteq\{1,...,n-1\}$ mit Schranke $G-g_n$\pause\\ \item Objekt $n$ gehört nicht zu optimaler Menge $I$:\pause\\ $I$ ist identisch zu Teil-Lösung $I'\subseteq\{1,...,n-1\}$ mit Schranke $G$, \typeout{ } \typeout{ } \typeout{ Hier noch mal genauer formulieren } \typeout{ } \typeout{ } \end{itemize} \end{itemize}\pause Daher setze $$w(i,h):=\left\{\begin{tabular}{l}maximaler Lösungswert\\ für erste $i$ Objekte bei Schranke $h$ \end{tabular}\right.$$ \pause mit rekursiver Formulierung\pause $$w(i,h)=\left\{\begin{array}{ll} 0&i=0\\ \pause w(i-1,h)&\pause i>0\wedge h< g_i\\ \pause\max\left\{\begin{array}{l} w(i{-}1,h),\\ w(i{-}1, h{-}g_i)+v_i\end{array}\right\}&\pause\mbox{sonst} \end{array}\right.$$ \end{frame} \begin{frame}[fragile] Dynamisches Programm dazu:\pause \begin{itemize} \item verwende Tabelle für $w(i,h)$ mit $0\leq i0$ \pause \item Einzelheiten: Übung... \end{itemize} \end{frame} \subsubsection{Backtracking} \inhaltb{15} \begin{frame}[fragile] Backtracking:\pause \begin{itemize} \item Durchlauf durch (großen) Suchbaum\pause \item Baum i.d.R. nur implizit gegeben\pause \item wichtiges Teilziel: Ausschluss von Teilbäumen\pause \item i.d.R. rekursive Implementierung \end{itemize}\pause Grundstruktur der Rekursion:\pause \begin{programm} \begin{semiverbatim}\bfseries PROCEDURE \Fb{backtrack}(Lösungsansatz);\pause IF (Lösungsansatz == vollständige Lösung) THEN gib Lösung aus\pause ELSE FOR (wichtige Erweiterungen des Lösungsansatzes) DO \Fb{backtrack}(Lösungsansatz mit Erweiterung) ENDFOR\pause ENDIF RETURN ENDPROCEDURE \end{semiverbatim} \end{programm}\pause Aufruf mit \verb#backtrack(leere Lösung)# \end{frame} \begin{frame}[fragile] \begin{itemize} \item Rekursion führt implizit zu Baumstruktur!\pause \item Anzahl der Erweiterungen der Lösungsansätze klein halten!\pause \item zur `Wichtigkeit' der Erweiterungen:\pause \begin{itemize} \item Jede Erweiterung, die noch zu Lösung werden könnte, ist wichtig!\pause \item Leicht erkennbar, dass keine Lösung mehr entstehen kann: unwichtige Erweiterung\pause \item ansonsten: vorsichtshalber als wichtige Erweiterung einstufen... \end{itemize}\pause \item falls keine Erweiterung wichtig $\leadsto$ Teilbaum wird ausgelassen! \end{itemize} \pause Insbesondere bei CSP mit $n$ Variablen, $|D|=d$ und Ordnung $k$: \pause \begin{itemize} \item Erweiterung eines Lösungsansatzes = Belegung einer weiteren Variablen!\pause \item Teste pro Variable alle $d$ möglichen Werte\pause \item Also: $d$-ärer Suchbaum mit Tiefe $n$, Größe $d^n$\pause \item Sobald für ein Constraint $C_j$ alle Variablen belegt sind:\\\pause Falls $C_j$ dabei falsch wird: Werte weiterer Variablen unwichtig! \end{itemize} \end{frame} \begin{frame}Grobe Abschätzung des Effektes: \begin{itemize} \item Constraint der Ordnung $k$ führt zur $d^k$ Teilbäumen\pause \item Für jedes falsche Resultat: Ein Teilbaum weniger...\pause \item Da jedes Constraint falsch werden kann (sonst trivial...):\\ \pause Statt $d^k$ Teilbäumen i.d.R. nur $d^k-1$ \pause \item Komplexität statt $d^n$ nur $(d^k-1)^{n/k}$ \end{itemize}\pause heuristische Verbesserungen:\pause \begin{itemize} \item Sortiere Variablen nach Ordnung der Constraints:\pause \item Erst Variablen in Constraints mit kleiner Ordnung belegen\pause \item Bei Constraints mit gleicher minimaler Ordnung: \pause Häufigst benutzte Variable zuerst belegen (reduziert Ordnung anderer Constraints!) \end{itemize} \end{frame} \begin{frame}[fragile] Beispiel KNF-SAT:\pause \begin{itemize} \item Gegeben: Formel $F$ in KNF mit $n$ Variablen\pause \item Gesucht: Erfüllende Belegung $\Phi$ \end{itemize}\pause naiver Algorithmus: Durchsuche alle möglichen Belegungen, z.B.\pause \begin{programm} \begin{semiverbatim}\bfseries Gegeben \(F\) mit \(n\) Variablen\pause FOR \(b\) := 0 TO \(power(2,n)-1\) DO\pause Interpretiere die Einzelbits von \(b\) als Belegung \(\Phi\).\pause Teste, ob \(F\) durch \(\phi\) erfüllt wird.\pause Wenn ja: RETURN TRUE\pause RETURN FALSE \end{semiverbatim} \end{programm}\pause Aufwand \begin{itemize} \item Formel nicht erfüllbar: $2^n\cdot$(Bestimmung des Wertes von $F$ bei $\phi$)\pause \item Formel erfüllbar: schrumpft mit wachsender Zahl an Lösungen... \end{itemize} \end{frame} \begin{frame}[fragile] Backtracking-Algorithmus (einfachste Form): \pause \begin{programm} Gegeben: Formel $F$ mit Variablen $\{x_1,...,x_n\}$\pause Belegung $\Phi$ ist String der Länge $n$ über $\{0,1,u\}$ (mit $0$: falsch, $1$: wahr, $u$: unbelegt)\pause \begin{semiverbatim}\bfseries BOOLEAN PROCEDURE backtrack(belegung \(\Phi\);\pause IF (\(\Phi\) enthält kein \(u\)) THEN RETURN \(F(\Phi)\) ENDIF\pause IF (\(\Phi\) setzt eine Klausel in \(F\) auf \(0\) ) THEN RETURN \(0\) ENDIF\pause wähle unbelegte Variable, Index sei \(i\)\pause IF backtrack( \(\Phi[i:0]\) ) THEN RETURN \(1\) ENDIF\pause RETURN backtrack( \(\Phi[i:1]\) ) ENDPROCEDURE\pause main: backtrack( \( u...u\) ) \end{semiverbatim} \end{programm} \end{frame} \begin{frame} Beispiel: $F=\underbrace{(x_1\vee x_2)}_{c_1}\wedge \underbrace{(x_1\vee\overline{x_2})}_{c_2}\wedge \underbrace{(\overline{x_1}\vee x_3\vee x_4)}_{c_3}\wedge \underbrace{(\overline{x_1}\vee \overline{x_3}\vee x_4}_{c_4})$ \[\includegraphics[width=.85\textwidth]{grafik/backtrack.pdf}\] \end{frame} \begin{frame} Backtracking bei {\bfseries 2-KNF-SAT}:\pause \begin{itemize} \item Pro Klausel von 4 Wahrheitswerten nur 3 wichtig\pause \item Formal damit statt $2^n$ nur $(\sqrt{3})^{n}$\pause \item zudem: jede Variablen-Belegung legt Werte vieler direkt/indirekt verbundener Variablen fest! \pause \item Damit nur noch 2 Versuche pro `Zusammenhangskomponente'! \pause \item Topologische Sortierung der Komponenten $\leadsto$ Polynomialer Algorithmus (bei Modifikation des Backtracking) \end{itemize} \pause Backtracking bei {\bfseries 3-KNF-SAT}:\pause \begin{itemize} \item Statt $2^n$ nur $\approx 7^{n/3}=1{,}913^n$,\pause \item formal: bei $n=30$ nur 1/4 der Komplexität\pause \item Hauptvorteil aber: \pause Jede Variablenbelegung macht aus manchen 3er-Klauseln kleinere 2er-Klauseln, \pause d.h. dieser Teil dann wie 2-KNF-SAT behandelbar! \end{itemize} \end{frame} \subsubsection{Branch and Bound} \inhaltb{15} \begin{frame} \Fb{Branch and Bound}: Kombination zweier Strategien bei \Fb{Optimierungsproblemen}: \pause \begin{itemize} \item Aufgabe: suche beste von allen(!) Lösungen\pause \item wie bei Backtracking: Ausschluß von Lösungsansätzen\pause \item zudem: bevorzugte Behandlung aussichtsreicher Lösungsansätze \end{itemize} \pause Dazu benötigt:\pause \begin{itemize} \item Optimierungsproblem mit baumartigem Lösungsalgorithmus\pause \item einfache Bewertungsmöglichkeit $g$ der Güte eines Lösungsansatzes\pause \item evtl. (möglichst gute) Schranke $G$ für die beste Gesamtlösung \end{itemize}\pause Vergleich:\pause \begin{itemize} \item Backtracking: Suche mit `nächster' Teil-Lösung fortgesetzt\pause \item Branch and Bound: Suche mit `bestem' Lösungsansatz fortgesetzt\pause \item statt Rekursionsstack wird Priority Queue verwendet \end{itemize} \end{frame} \begin{frame}[fragile] Branch-and-Bound-Algorithmus (einfachste Form): \pause \begin{itemize} \item Gegeben: Mimimierungsproblem\pause \begin{itemize} \item mit Bewertungsfunktion $v$ für Lösungen,\pause \item mit Gütefunktion $g$ (`Bound') für Lösungsansätze \end{itemize}\pause \item Bedingung an $v$ und $g$:\pause\\ Ist Lösung $L$ Erweiterung des Ansatzes $A$, \pause dann $v(L)\geq g(A)$ \end{itemize} \begin{programm} \pause \begin{semiverbatim}\bfseries Ansatz \(A\) \pause:= leerer Lösungsansatz\pause Schranke \(G\) := \(\infty\)\pause Lösung \(L\)\pause Priority Queue \(pq\);\pause \(pq\).insert( \(A,\) \(g(A)\) )\pause WHILE \(pq\).not_empty DO\pause \(A\) := \(pq\).extract_min;\pause IF (\(A\) ist vollständige Lösung) THEN\pause IF ( \(v(A) < G\) ) THEN \(L\) := \(A\); \(G\) := \(v(A)\) ENDIF \pause ELSE\pause FORALL ( \(E\) Erweiterung von \(A\) ) DO\pause IF ( \(g(E) < G\) ) THEN \(pq\).insert( \(E\), \(g(E)\) ) ENDIF \pause ENDFOR\pause ENDIF ENDDO\pause RETURN \(L\) \end{semiverbatim}\end{programm} \end{frame} \begin{frame} Beispiel: TSP \begin{itemize} \item $m_{i,j}$ Kosten/Gewicht der Kante $(ij)$\pause \item $g$ Gewicht eines Pfades $i_1i_2 ... i_n$\pause $$g(i_1i_2 ... i_n)=m_{i_1,i_2}+...+m_{i_{n-1},i_n}$$ \pause \item $v$ Gewicht einer kompletten Rundreise $i_1i_2 ...i_n$ mit $i_1=i_n$\pause $$v(i_1i_2 ... i_n)=g(i_1 ... i_n)$$ \pause \item bei nichtnegativen(!) Kosten $m_{i,j}$ gilt für $k\leq n$ \pause $$v( i_1i_2 ... i_n)\geq g(i_1i_2 ... i_k)$$ \end{itemize} \end{frame} \begin{frame} Betrachte TSP mit {\scriptsize $M=\left[\begin{array}{ccccc} - & 10 & 15 & 20\\ 5 & - & 9 & 10 \\ 6 & 13 & - & 12 \\ 8 & 8 & 9 & - \end{array}\right]$}\pause, Start mit $G=\infty$\pause {\scriptsize$$\begin{array}{|l|}\hline \mbox{Inhalt (Pfad,Gewicht) der Priority Queue:}\\\hline (1,0)\\\hline \pause\Fa{(12,10)}~~\Fa{(13,15)}~~\Fa{(14,20)}\\\hline % \pause(13,15)~~\Fb{(123,19)}~~\Fb{(124,20)}~~(1 4,20)\\\hline % \pause(123,19)~~(124,20)~~(14,20)~~\Fa{(134,27)}~~\Fa{(132,28)}\\\hline % \pause(124,20)~~(14,20)~~(134,27)~~(132,28)~~\Fb{(1234,31)}\\\hline % \pause(14,20)~~(134,27)~~(132,28)~~\Fa{(1243,29)}~~(1 234,31)\\\hline % \pause(134,27)~~(132,28)~~\Fb{(142,28)}~~\Fb{(143,29)}~~(1243,29)~~ (1 234,31)\\\hline % \pause(132,28)~~(142,28)~~(143,29)~~(1243,29)~~(1 234,31)~~ \Fa{(1342,35)})\\\hline % \pause(142,28)~~(143,29)~~(1243,29)~~(1234,31)~~ (1342,35)~~\Fb{(1324,38)}\\\hline % \pause(143,29)~~(1243,29)~~(1234,31)~~(1342,35)~~ \Fa{(1423,37)}~~(1324,38)\\\hline % \pause(1243,29)~~(1234,31)~~(1342,35)~~ (1423,37)~~(1324,38)~~\Fb{(1432,42)}\\\hline % \pause\mbox{erste Lösung gefunden: }\Fa{L=(12431)},\mbox{ neue Schranke }G=35\\ \pause(1234,31)~~(1342,35)~~(1423,37)~~(1324,38)~~(1432,42)\\\hline \pause\mbox{ab hier: }pq\mbox{ wird nur noch geleert...}\\\hline \end{array}$$} \pause Optimale Lösung ist $L=(12431)$ \pause mit Gewicht $35$ \end{frame} \begin{frame} Verbesserungen des Algorithmus:\pause \begin{itemize} \item[(1)] Suche besseren Startwert der Schranke $G$\pause \begin{itemize} \item z.B. durch Vorab-Bestimmung einer (nicht zu schlechten) Lösung \end{itemize}\pause \item[(2)] Bessere Datenstrukturen:\pause\\ Für TSP statt Pfad besser Paare (Knotenmenge, letzter Knoten)\pause \begin{itemize} \item z.B. statt $(1243,29)$ und $(1423,37)$ \pause nur $(~(\{2,4\},3)~,29)$ in $pq$\pause \item benötigt \texttt{decreaseKey}-Operation für Priority Queues \end{itemize} \pause \item[(3)] Versuche die Unterschiede zwischen guten und schlechten Pfaden zu vergrößern...\pause\\ \begin{itemize} \item Reduziere Gewichte der Pfade um Anteile, die allen Pfaden gemeinsam sind\pause \item von Reduktion profitieren insbesondere gute Lösungen \end{itemize} \end{itemize} \end{frame} \begin{frame} Anwendung von (3) im Beispiel TSP: \pause Reduktion von $M$ wie folgt\pause \begin{itemize}\item subtrahiere von jeder Zeile in $M$ das Minimum $z_i$ der Zeile $i$,\pause\\ damit Gewicht jeder(!) Lösung um $\sum k_i$ erniedrigt\pause {\scriptsize $$M=\left[\begin{array}{ccccc} - & 10 & 15 & 20\\ 5 & - & 9 & 10 \\ 6 & 13 & - & 12 \\ 8 & 8 & 9 & - \end{array}\right] ~~~\leadsto ~~~M'=\left[\begin{array}{ccccc} - & 0 & 5 & 10\\ 0 & - & 4 & 5 \\ 0 & 7 & - & 6 \\ 0 & 0 & 1 & - \end{array}\right]$$} \pause mit Minima $10,5,6,8$, \pause d.h. mit Erniedrigung um $10+5+6+8=29$\pause \item subtrahiere von jeder Spalte in $M'$ das Minimum $s_i$ der Spalte $i$,\pause\\ damit Gewicht jeder(!) Lösung weiter um $\sum s_i$ erniedrigt\pause {\scriptsize $$M'=\left[\begin{array}{ccccc} - & 0 & 5 & 10\\ 0 & - & 4 & 5 \\ 0 & 7 & - & 6 \\ 0 & 0 & 1 & - \end{array}\right] ~~~\leadsto ~~~M''=\left[\begin{array}{ccccc} - & 0 & 4 & 5\\ 0 & - & 3 & 0 \\ 0 & 7 & - & 1 \\ 0 & 0 & 0 & - \end{array}\right]$$} \pause mit Erniedrigung um $0+0+1+5=6$\pause \item Optimale Lösungen bei $M$ und $M''$ gleich,\\ aber im Gewicht verschieden\pause, sogar um $29+6=35$ \end{itemize} \end{frame} \begin{frame} Betrachte TSP mit {\scriptsize$ M''=\left[\begin{array}{ccccc} - & 0 & 4 & 5\\ 0 & - & 3 & 0 \\ 0 & 7 & - & 1 \\ 0 & 0 & 0 & - \end{array}\right]$}, Start mit $G=\infty$\pause {\scriptsize$$\begin{array}{|l|}\hline \mbox{Inhalt (Pfad,Gewicht) der Priority Queue:}\\\hline \pause(1,0)\\\hline \pause\Fa{(12,0)}~~\Fa{(13,4)}~~\Fa{(14,5)}\\\hline % \pause\Fb{(124,0)}~~\Fb{(123,3)}~~(13,4)~~(14,5)\\\hline % \pause\Fa{(1243,0)}~~(123,3)~~(13,4)~~(14,5)\\\hline % \pause\mbox{erste Lösung gefunden: }\Fb{L=(12431)},\mbox{ neue Schranke }G=0\\ \pause(123,3)~~(13,4)~~~~(14,5)\\\hline \pause\mbox{ab hier: }pq\mbox{ wird nur noch geleert...}\\\hline \end{array}$$} \pause Optimale Lösung für $M''$ ist $L=(12431)$ mit Gewicht $0$\pause, damit wieder: \pause Optimale Lösung für $M$ ist $L=(12431)$ mit Gewicht $35+0=35$ \end{frame} \begin{frame} Bestimmung guter Schrankenfunktionen:\pause \begin{itemize} \item Gegeben: Mimimierungsproblem $P$\pause \begin{itemize} \item mit Bewertungsfunktion $v$ für Lösungen, \item benötigt: Gütefunktion $g$ (`Bound') für Lösungsansätze \end{itemize}\pause \item bestimme $g$ mit:\pause\\ Ist Lösung $L$ Erweiterung des Ansatzes $A$, dann $v(L)\geq g(A)$ \end{itemize} \pause oft wird dazu {\bf Relaxation} benutzt:\pause \begin{itemize} \item Aufweichung der Aufgabenstellung von $P$ zu $P'$,\pause\\ z.B. Weglassen eigentlich notwendiger Bedingungen\pause \item $\leadsto$ Lösungsraum von $P'$ \pause umfasst Lösungsraum von $P$\pause \item evtl. effizienter Algorithmus für aufgeweichtes Problem $P'$ bekannt\pause \item Gütefunktion $g'$ für $P'$ ist auch Gütefunktion $g$ für $P$... \end{itemize} \pause Auch TSP-Beispiel als Relaxation interpretierbar: \begin{itemize} \item zyklenfreie Pfade als Lösung betrachten (statt Permutationen)\pause \item dann: beste Lösung zu Ansatz $i_1...i_k$ \pause ist gerade $i_1...i_k$ selbst... \end{itemize} \end{frame} \subsection{Approximative Verfahren} \subsubsection{Grundlegende Definitionen} \inhaltb{15} \begin{frame} Betrachte Optimierungsprobleme\pause Da vermutlich $P\neq NP$:\pause \begin{itemize} \item Dynamisches Programmieren, Backtracking, Branch-and-Bound sind i.d.R. nicht polynomial!\pause \item als Alternative: statt `optimaler' nur `gute' Lösungen verlangen!\pause \item suche Lösung $y \in S (x)$, so dass $v(y)$ nicht `allzu weit' von optimalen $v^*(x)=opt\{v(z)\mid z\in S(x)\}$ weg ist \end{itemize}\pause Anmerkung: das Finden einer zulässigen Lösung $y\in S (x)$ sollte nicht bereits $NP$-vollständig sein, \pause Beispiele:\pause \begin{itemize} \item Finden zulässiger Lösungen bei MaxSAT ist trivial.\pause \item Finden zulässiger Lösungen bei TSP ist trivial, \pause\\ wenn $\infty$ in Lösungen zulässig ist\pause \item Finden zulässiger Lösungen bei TSP ist NP-vollständig, \pause\\ wenn $\infty$ in Lösungen nicht zulässig ist \pause (da damit die Existenz von Hamiltonkreisen getestet werden kann!) \end{itemize} \end{frame} \begin{frame} \begin{definition} Für ein Optimierungsproblem $P$ mit zulässiger Eingabe $x$ und Lösungsmenge $S(x)$ ist die \emph{Performanz} $r(x,y)$ \pause einer Lösung $y\in S(x)$ definiert durch\pause $$r(x,y):= \min\pause\left\{\frac{v(y)}{v^*(x)},\pause\frac{v^*(x)}{v(y)}\right\}$$ \pause wobei $v^*(x):=$ Optimum aus $\{v(z)\mid z\in S(x)\}$ \end{definition} \pause Anmerkungen:\pause \begin{itemize} \item Bei Minimierungsproblemen: $v^*(x):=\min\{v(z)\mid z\in S(x)\}$\pause \item Bei Maximierungsproblemen: $v^*(x):=\max\{v(z)\mid z\in S(x)\}$\pause \item Stets $r(x,y)\leq 1$, \pause gute Approximationen haben $r(x,y)\approx 1$\pause \item in Literatur auch Definition über Kehrwert $1/r$,\\\pause dann Performanz stets $\geq 1$ ... \end{itemize} \end{frame} \begin{frame} \begin{definition}[APX]\pause Ein Optimierungsproblem liegt in \Fb{\bfseries APX}, \pause wenn es {\bfseries eine Zahl} $\delta\in(0,1)$ und einen polynomialen Algorithmus gibt, \pause der bei jeder zulässigen Eingabe $x$ eine Lösung $y\in S(x)$ liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-\delta$. \pause Die Abkürzung {\bfseries APX} deutet an, dass das Optimierungsproblem - bis zu einem gewissen Grad - approximierbar ist. \end{definition}\pause $\delta$ darf beliebig nahe an $1$ sein, \pause d.h. schlechte Performanz erlaubt...\pause Stärkere Einschränkung / bessere Approximationen:\pause \begin{definition}[PTAS] Ein Optimierungsproblem liegt in \Fb{\bfseries PTAS}, \pause wenn es {\bfseries für jede Zahl} $\delta\in(0,1)$ einen polynomialen Algorithmus gibt, \pause der bei jeder zulässigen Eingabe $x$ eine Lösung $y\in S(x)$ liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-\delta$. \pause Die Abkürzung {\bfseries PTAS} steht für \Fb{polynomial time approximation scheme}. \end{definition} \pause Hier ist jede beliebig gute Performanzschranke $\delta$ erreichbar. \end{frame} \begin{frame} \begin{definition}[FPTAS] Ein Optimierungsproblem liegt in \Fb{\bfseries FPTAS}, \pause wenn es einen Algorithmus gibt, \pause der bei jedem zulässigen $x$ und $k\in\nz$ als Eingabe \pause eine Lösung $y\in S(x)$ liefert mit einer zugehörigen Performanz $r(x,y)\geq 1-1/k$. \pause Die Komplexität des Algorithmus muss polynomial in $x$ und $k$ sein.\pause Die Abkürzung {\bfseries FPTAS} steht für \Fb{fully polynomial-time approximation scheme}. \end{definition} \pause Bei FPTAS ist selbst die Abhängigkeit von der Performanzschranke noch polynomiell!\pause Damit ergibt sich folgende Inklusionskette\pause $$\begin{tabular}{c} \bfseries\small Menge exakt lösbarer Optimierungsprobleme aus $P$ \\ \pause $\subseteq$ {\bfseries FPTAS} \pause$\subseteq$ {\bfseries PTAS} \pause$\subseteq$ {\bfseries APX} $\subseteq$ \\ \pause\bfseries\small Menge aller $NP$-Optimierungsprobleme \end{tabular}$$ \end{frame} \begin{frame} Falls $P\neq NP$, sind alle Inklusionen echt: \pause $$\begin{tabular}{c}\bfseries\small Menge exakt lösbarer Optimierungsprobleme aus $P$\\ $\stackrelsub{\subset}{\neq}$ {\bfseries FPTAS} $\stackrelsub{\subset}{\neq}$ {\bfseries PTAS} $\stackrelsub{\subset}{\neq}$ {\bfseries APX} $\stackrelsub{\subset}{\neq}$ \\\bfseries \bfseries\small Menge aller $NP$-Optimierungsprobleme \end{tabular}$$ \pause Typische Beispiele einiger Klassen sind:\pause \begin{itemize} \item {\bfseries Menge exakt lösbarer Optimierungsprobleme aus $P$}:\pause\\ Maximale Flüsse in Graphen\pause\\ ($\leadsto$ Vorlesung Netzwerkalgorithmen)\pause \item{\bfseries FPTAS}: \pause $0/1$-Rucksackproblem\pause\\ ($\leadsto$ über dynamisches Programmieren, s.u.)\pause \item {\bfseries APX}: \pause MaxSAT \pause \begin{itemize} \item probabilistisches Approximationsverfahren (analog APX)\pause\\ ($\leadsto$ Vorl.\ Approximative Algorithmen)\pause \item $P\neq NP \Rightarrow$ MaxSAT $\not\in$ PTAS: \pause über `PCP-Theorem' \pause \\ (PCP: probabilistically checkable proofs) \pause \\ ($\leadsto$ Vorlesung Approximative Algorithmen) \end{itemize} \pause \item {\bfseries Menge aller $NP$-Optimierungsprobleme}: \pause TSP\pause\\ (vermutlich nicht in {\bfseries APX}, s.u.) \end{itemize} \end{frame} \begin{frame} \begin{example}[zur Approximierbarkeit von TSP] Annahme: Es gibt polynomialen Algorithmus für TSP und $\delta\in(0, 1)$ mit Performanz von mindestens $1-\delta$\pause \begin{itemize} \item Sei $G$ beliebiger Graph mit $n$ Knoten, \pause definiere dazu TSP $x$ durch \GLA m_{i,j}=\left\{\begin{array}{l}1,\mbox{ falls }(i,j)\mbox{ Kante in }G\\ 1+\lceil\frac{n}{1-\delta}\rceil, \mbox{ sonst} \end{array}\right. \GLE \item \pause TSP-Approximation liefert zu $x$ Lösung $y$ mit Performanz $r(x,y)=\frac{v^*(x)}{v(y)}\geq 1-\delta$\pause \item Existiert Hamilton-Kreis in $G$, dann $v^*(x)=n$, \pause also $v(y)< \frac{n}{1-\delta}$, \pause d.h. $y$ nutzt nur Kanten aus $G$ (d.h. findet Hamilton-Kreis in $G$)\pause \item Über $v(y)$ kann also entschieden werden, ob in $G$ ein Hamilton-Kreis existiert ... \end{itemize} \pause also $$\mbox{\bfseries TSP}\in\mbox{\bfseries APX} \Longrightarrow P=NP$$ d.h. {\bfseries TSP} liegt vermutlich nicht in {\bfseries APX}! \end{example} \end{frame} \begin{frame} \begin{example}[$0/1$-Rucksack liegt in {\bfseries FPTAS}]\pause Löse $0/1$-Rucksack über `minimales Gewicht für gesuchten Gewinn':\pause \begin{itemize} \item Gegeben: $n\in\nz$, $G\in\nz$, Vektoren $(v_1,...,v_n),(g_1,...,g_n)\in \nz^n$\pause \item definiere $g(i,w):=$ minimales Gewicht für Teilmengen von Objekten aus $\{1,...,i\}$, \pause die zum Gewinn $\geq w$ führen\pause \item formal: berechne $$g(i,w)=\min\{ \sum_{j\in I}g_j\mid I\subseteq\{1,...,i\}\wedge\sum_{j\in I}v_j\geq w\}$$ \pause \item Gesucht: größter Gewinn $w$ mit $g(n,w)\leq G$\pause \item rekursive Formulierung von $g(i,w)$:\pause $$g(i,w)=\left\{\begin{array}{ll} 0&w\leq 0\\ \infty& w> 0 \wedge i=0\\ \pause\min\left\{\begin{array}{l} g(i{-}1,w),\\ g(i{-}1, w{-}v_i)+g_i\end{array}\right\}&\pause\mbox{sonst} \end{array}\right.$$ \end{itemize} \end{example} \end{frame} \begin{frame}[fragile] \begin{cont}{0/1-Rucksack in FPTAS} Dynamisches Programm dazu (für exakte Lösung):\pause \begin{itemize} \item statt Funktion $g(i,w)$ verwende Tabelle $g[i,w]$ mit $0\leq i\) G ENDFOR\pause Ausgabe: w-1 \end{semiverbatim} \end{programm}\pause \begin{itemize}\item Ausgabe also: größtes $W$ mit $g[n,W]\leq G$\pause \item $I$ sei zu $W$ gehörige optimale Teilmenge von $\{1,...,n\}$\pause \item zur Tabellengröße: Zugriffe nur auf $g[i,w]$ mit $w\leq W+1$\pause \item Aufwand: ${\cal O}(n\cdot W)$ (Funktionsauswerungen ignorierbar!) \end{itemize} \end{cont} \end{frame} \begin{frame}[fragile] \begin{cont}{0/1-Rucksack in FPTAS} jetzt approximative Lösung:\pause \begin{itemize}\item wähle $m$ geeignet (s.u.), \pause setze \Fb{$v'_i:= \lfloor v_i/m\rfloor$}\pause \item löse $(0,1)$-Rucksack für $(v'_1,...,v'_n)$\pause\\ (aber mit unveränderten $(g_1,...,g_n)$ und $G$)\pause \item $J$ sei die dabei gefundene optimale Menge, \pause mit $V':=\sum_{i\in J}v'_i$\pause \item setze $V:=\sum_{i\in J}v_i$ \pause (d.h. neue optimale Menge, aber alte Kosten!) \end{itemize} \pause Vergleiche nun $J$ mit $I$ \pause sowie die drei Werte $W$, $V'$ und $V$:\pause \begin{itemize} \item Zwischen $J$ und $I$ lässt sich kein direkter Zusammenhang finden\pause, Objekte der Lösungen $I$ und $J$ können komplett verschieden sein!\pause \item $J$ erfüllt $\sum_{i\in J}g_i\leq G$\pause, d.h. $J$ ist auch (i.d.R. nicht-optimale) Lösung für das Ursprungsproblem, \pause d.h $V\leq W$, \pause zudem \GLA V'=\sum_{i\in J}v'_i\pause\leq\sum_{i\in J}v_i/m\pause=V/m\leq W/m\GLE \item \pause damit sofort: Aufwand für die Lösung des modifizierten Problems mit $(v'_1,...,v'_n)$ ist ${\cal O}(n\cdot V')={\cal O}(n\cdot W/m)$ \end{itemize} \end{cont} \end{frame} \begin{frame} \begin{cont}{0/1-Rucksack in FPTAS} Betrachte folgendes Beispielproblem:\pause $$\Fb{ n=3, (v_1,v_2,v_3)=(3,5,6), (g_1,g_2,g_3)=(1,2,3), G=5} $$ \pause Resultate beim dynamischen Programm: {\footnotesize $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline W:& 1&2&3&4&5&6& 7&8&9& 10&11&12&...\\\hline\hline i=1& 1&1&1&\infty\\\hline i=2& 1&1&1&2&2&3&3&3&\infty\\\hline i=3& 1&1&1&2&2&3&3&3&4&5&\Fb{5}&6\\\hline \end{array}$$ } \pause Lösung: $W=11$ bei der Menge $I=\{2,3\}$\pause Teste Approximation mit $m=3$, also $\Fb{(v'_1,v'_2,v'_3)=(1,1,2)}$\pause {\footnotesize $$\begin{array}{|c|c|c|c|c|c|}\hline V':& 1&2&3&4&...\\\hline\hline i=1& 1&\infty\\\hline i=2& 1&3&\infty\\\hline i=3& 1&3&\Fb{4}&6\\\hline \end{array}$$ } \pause Lösung: $V'=3$ bei $J=\{1,3\}$, \pause d.h. Approximation an $W$ ist $V=9$. \end{cont} \end{frame} \begin{frame}[fragile] \begin{cont}{0/1-Rucksack in FPTAS} zur Performanz $V/W$ der Lösung $J$ (für das Originalproblem):\pause \begin{itemize}\item Da $J$ optimal für $(v'_1,...,v'_n)$ gilt (1) $\sum_{i\in I}v'_i\leq V'$.\pause \item Setze $v_{max}:=\max\{v_1,...,v_n\}$\pause, damit sofort (2) $W\leq n\cdot v_{max}$\pause \item o.B.d.A. stets $g_i\leq G$ \pause(sonst Objekt $i$ uninteressant...)\pause,\\ damit andererseits (3) $v_{max}\leq W$\pause \item Mit Setzung $v'_i:= \lfloor v_i/m\rfloor$ ist $v'_i\geq v_i/m-1$\pause, also \GLA V&= &\sum_{i\in J}v_i \pause\geq \sum_{i\in J}v'_i\cdot m \pause=V'\cdot m\pause\stackrel{(1)}{\geq}\pause \sum_{i\in I}v'_i\cdot m \\ &\pause\geq&\pause \sum_{i\in I}(v_i/m-1)\cdot m \pause\geq \sum_{i\in I}(v_i - m)\pause\geq W-n\cdot m \GLE \item \pause für die Performanz ergibt sich: \GLA\frac{V}{W}\pause\geq \frac{W-nm}{W}\pause\geq 1-\frac{n\cdot m}{W}\pause\stackrel{(3)}{\geq} \pause 1-\frac{n\cdot m}{v_{max}} \GLE \end{itemize} \end{cont} \end{frame} \begin{frame}[fragile] \begin{cont}{0/1-Rucksack in FPTAS} \begin{itemize} \item Für Ziel-Performanz $1-1/k$ \pause wähle $m$ so, dass $\frac{n\cdot m}{v_{max}}\leq 1/k$\pause, z.B. $$m=\frac{v_{max}}{k\cdot n}$$ \pause mit Aufwand $${\cal O}(n\cdot W/m)\pause={\cal O}(k\cdot n^2\cdot W/v_{max})\pause\stackrel{(2)}{=}{\cal O}(k\cdot n^3)$$ \item\pause Die Komplexität ist also polynomial in $n$ und $k$. \end{itemize} \end{cont} \end{frame} \begin{frame} Anmerkungen:\pause \begin{itemize} \item Ein Problem heißt {\em stark NP-vollständig}, \pause wenn es auch noch NP-vollständig ist, wenn alle involvierten Zahlen in unärer Schreibweise (statt binär) eingegeben werden.\pause \item Bei unärer Notation wird die Eingabe wesentlich länger,\pause\\ ein polynomialer Algorithmus darf länger laufen...\pause \item Gibt man bei $0/1$-Rucksack die Schranke $G$ unär an,\\ so gibt es eine polynomiale Lösung.\pause\\ (Bsp: bekanntes dynamisches Programm mit Laufzeit ${\cal O}(n\cdot G)$ )\pause\\ $0/1$-Rucksack ist damit nur `schwach NP-vollständig'!\pause \item Stark NP-vollständig sind z.B. TSP, 3-KNF-SAT, Färbbarkeit,...\pause \item Es gilt sogar: \begin{itemize} \item \bfseries Falls P$\neq$ NP, so liegt kein stark NP-vollständiges Problem in FPTAS! \end{itemize} \end{itemize} \end{frame} \begin{frame} \begin{example}[TSP-Varianten]\pause Wichtige Modifikationen des TSP sind:\pause \begin{itemize} \item Metrisches TSP: \pause Kosten $m_{i,j}$ der Kanten sind symmetrisch \pause und erfüllen die Dreiecksungleichung $m_{i,j}\leq m_{i,k}+m_{k,j}$\pause \item Euklidisches TSP: \pause Punkte liegen auf der Ebene,\pause \\ Entfernungen der Punkte entsprechen dem Euklidischen Abstand\pause \end{itemize} \pause Hier gilt:\pause \begin{itemize} \item Metrisches TSP liegt in {\bfseries APX}, \pause wobei die Performanz $2/3$ beträgt \pause (d.h. die gefundene Route ist 50\% maximal länger als die optimale Route)\pause (Christofides, 1976)\pause \item Metrisches TSP liegt nicht in {\bfseries PTAS}\pause (wenn P$\neq$NP) (Arora, 1992)\pause \item Euklidisches TSP ist NP-vollständig\pause \item Euklidisches TSP liegt in {\bfseries PTAS}\pause (Arora, 1996) \end{itemize} \end{example} \pause Im folgenden: Techniken, die bei Approximationsversuchen angewendet werden \pause (i.d.R. ohne Garantie für Performanz oder polynomiale Zeitkomplexität). \end{frame} \subsubsection{Greedy-Algorithmen} \inhaltb{15} \begin{frame} Greedy-Verfahren: \pause \begin{itemize} \item Ziel: exakte/approximative Lösung von Optimierungsproblemen\pause \item wieder: Lösung durch Erweiterung von Lösungsansätzen...\pause \item dynamisches Programm: jeweils beste Erweiterung ($\leadsto$ Tabelle...)\pause \item Greedy: gute, leicht findbare Erweiterung (ohne Tabelle...)\pause \item Grundidee: \pause\Fb{\em Nimm immer das beste Stück!} \end{itemize} \pause Beispiel: $0/1$-Rucksackproblem, $$ n=3, (v_1,v_2,v_3)=(3,5,6), (g_1,g_2,g_3)=(1,2,3), G=5 $$ \pause Greedy-Heuristik hier: \\ {\em Nimm das Stück mit den höchsten Wert pro Gewichtsanteil!} \pause Reihenfolge für Beispiel: $$\frac{3}{1} \geq \frac{5}{2} \geq \frac{6}{3}$$ \pause also: erst Objekt 1 nehmen, \pause dann Objekt 2, \pause dann ... $G$ überschritten.\pause Resultat: Lösung $\{1,2\}$ \pause mit Wert $3+5$ \pause (nicht optimal...) \end{frame} \begin{frame} \begin{example}[Bruchteil-Rucksackproblem] \pause \begin{itemize} \item Gegeben: $n\in\nz$, $G\in\nz$, Vektoren $(v_1,...,v_n),(g_1,...,g_n)\in \nz^n$ \pause \item Gesucht: Wie groß kann der `Wert' von Objekten werden,\\\pause deren Gewicht $\sum_{i\in I}g_i$ nicht größer als die Schranke $G$?\pause \item Aber: \Fb{Jetzt dürfen Objekte zerteilt werden!}\pause \item als Lösung daher jetzt ein Vektor $(a_1,...,a_n)$ \pause mit $a_i\in\qz$ \pause und $0\leq a_i\leq 1$ \pause (statt einer Menge $I$) \pause \item formal: bestimme $$\max\{ \sum_{i=1}^na_iv_i\pause \mid a_i\in[0,1]\pause \mbox{ mit } \sum_{i=1}^na_ig_i\leq G\}$$ \end{itemize} \pause Greedy-Ansatz: \pause \begin{itemize}\item Sortiere alle Objekte nach Wert $v_i/g_i$, \pause d.h. $\displaystyle\frac{v_1}{g_1}\geq \frac{v_2}{g_2}\geq... \geq\frac{v_n}{g_n} $\pause \item dann nimm soviel von den hochwertigen Objekten, wie möglich... \end{itemize} \end{example} \end{frame} \begin{frame}[fragile] \begin{cont}{Bruchteil-Rucksackproblem} Algorithmische Lösung:\pause \begin{programm} \bfseries\em $k :=0$\pause\\ WHILE $\displaystyle\sum_{i=1}^{k+1} g_i\leq G$ DO $k:=k+1$ ENDWHILE\pause\\ $\displaystyle b:= (G-\sum_{i=1}^{k}g_i)/g_{k+1}$\pause\\ Optimale Lösung ist $(a_1,a_2,...,a_n)=(\underbrace{1,1,...1}_k, b,\underbrace{0,0,...,0}_{n-k-1})$ \end{programm} \pause Grundidee zu Nachweis der Optimalität der Lösung:\pause \begin{itemize} \item Sei $(a'_1,a'_2,...,a'_n)$ eine andere Lösung.\pause \item Betrachte $j:=\min\{i\mid a'_i\neq a_i\}$\pause \item Dann $\sum_{i=1}^{j} g_i < G$, also gibt es $m>j$ mit $a'_m>0$.\pause \item Transferiere dann Gewicht von Objekt $m$ zu Objekt $j$,\pause\\ (d.h. verkleinere $a'_m$ und vergrößere $a'_j$ soweit wie möglich)\pause \item die entstehende Lösung wäre nicht schlechter...,\pause\\ aber `näher' an $(a_1,a_2,...,a_n)$ \end{itemize} \end{cont} \end{frame} \begin{frame} Allgemeine Form der Probleme, bei denen Greedy anwendbar ist:\pause \begin{definition} $E$ sei endliche Menge, \pause${\cal U}$ sei eine Menge von Teilmengen von $E$.\pause Die Struktur $(E,{\cal U})$ heißt \Fb{Teilmengensystem}\pause, wenn \begin{itemize} \item $\emptyset\in {\cal U}$\pause \item $A\subseteq B\pause\wedge B\in {\cal U} \pause\Rightarrow A\in{\cal U}$ \end{itemize} \end{definition} \pause $w:E\to\qz$ sei eine Kostenfunktion, \pause\\ gesucht wird eine in $\cal U$ maximale Menge $T$ (bzgl. $\subseteq$) \pause mit maximalem Gesamtkosten $$w(T)=\sum_{e\in T} w(e)$$\pause \begin{itemize} \item Die Rolle der Gewichtsschranke $G$ übernimmt das Teilmengensystem $\cal U$\pause \item Dabei ist $T\in{\cal U}$ maximal in $\cal U$\pause, wenn kein $T'\in{\cal U}$ mit $T\subset T'$ existiert. \end{itemize} \end{frame} \begin{frame}[fragile] kanonischer Greedy-Algorithmus für Teilmengensysteme:\pause \begin{programm} \bfseries\em Ordne die Elemente in $E=\{e_1,...,e_n\}$,\pause\\ \hspace*{2em} so dass $w(e_1)\geq w(e_2)\geq ...\geq w(e_n)$\pause\\ Setze $T:=\emptyset$\pause\\ FOR $k:=1$ TO n DO\pause\\ \hspace*{2em}IF $T\cup \{e_k\}\in {\cal U}$ THEN $T:=T\cup \{e_k\}$\pause\\ ENDFOR\pause\\ Ausgabe von $T$ als Lösung \end{programm} \pause Charakterisierung der Probleme, die Greedy-Algorithmus optimal löst:\pause \begin{definition} Ein Teilmengensystem $(E,{\cal U})$ heißt \Fb{Matroid}\pause, wenn zusätzlich die Austauscheigenschaft gilt:\pause \begin{itemize} \item $A,B\in{\cal U}\pause\wedge |A|<|B|~~~ \pause\Rightarrow~~~ (\exists x\in B\setminus A)~ A\cup\{x\}\in{\cal U}$ \end{itemize} \end{definition} \pause \begin{itemize} \item `Matroid' verallgemeinert Begriff `(lineare) Unabhängigkeit' \pause \item In Matroiden haben maximale Mengen gleiche Mächtigkeit! \end{itemize} \end{frame} \begin{frame} Beispiel für Matroide: \pause \begin{itemize} \item seien $n,k\in\nz$ gegeben, $k\leq n$\pause \item betrachte $E=\{1,2,...,n\}$\pause \item setze ${\cal U}=\{ A\subseteq E~~:~~ |A|\leq k\}$ \end{itemize}\pause Maximale Menge sind hier die $k$-elementigen Mengen\pause,\\ die Austauscheigenschaft ist offensichtlich erfüllt.\pause Weitere Beispiele für Matroide $(E,{\cal U})$:\pause \begin{itemize} \item $E$: endliche Menge von Vektoren, \pause\\ $\cal U$: linear unabhängige Teilmengen von $E$\pause (z.B.: $E$ besteht aus Spalten einer Matrix, daher auch `Matroid')\pause \item $E$: Kantenmenge eines endlichen Graphen $G$, \pause\\ $\cal U$: kreisfreie Teilmengen von $E$\pause (auch `graphisches Matroid' genannt)\pause Maximale Elemente von $\cal U$ sind aufspannende Wälder von $G$. \end{itemize} \end{frame} \begin{frame} Bedeutung der Austauscheigenschaft: \pause \begin{itemize} \item $A$ und $B$ seien maximale Elemente im Matroid $(E,{\cal U})$\pause \item Damit $|A|=|B|$\pause \item Falls $A\neq B$:\pause \begin{itemize} \item Wähle $a\in A\setminus B$.\pause \item Zu $A\setminus \{a\}$ gibt es $b\in B\setminus A$ \pause mit $A':= A\setminus \{a\}\cup\{b\}\in {\cal U}$\pause \item $A'\setminus B$ ist kleiner als $A\setminus B$\pause, $A'\cap B$ ist größer als $A\cap B$ \end{itemize}\pause \item Also: Man kann $A$ durch Austausch einzelner Elemente schrittweise in $B$ umwandeln, ohne dabei $\cal U$ zu verlassen! \end{itemize} \pause \begin{theorem} Sei $(E,{\cal U})$ ein Teilmengensystem.\pause Der kanonische Greedy-Algorithmus liefert beim Optimierungsproblem \pause genau dann \pause {\bfseries für jede beliebige} Kostenfunktionen $w:E\to \qz$ \pause die optimale Lösung\pause, wenn $(E,{\cal U})$ ein Matroid ist. \end{theorem} \end{frame} \begin{frame} Beweis von "$\Leftarrow$": \pause \begin{itemize} \item gegeben: $(E,{\cal U})$ Matroid, \pause $w:E\to \qz$ Gewichtsfunktion \pause \item O.B.d.A.: bereits Ordnung $w(e_1)\geq w(e_2)...\geq w(e_n)$ vorhanden \pause \item $T=\{e_{i_1},...,e_{i_k}\}$ sei Lösung durch Greedy-Algorithmus. \pause \item Annahme: Greedy-Algorithmus liefert nicht die optimale Lösung. \pause \item $T'=\{e_{j_1},...,e_{j_k}\}$ sei bessere Lösung, \pause d.h. $w(T')> w(T)$ \pause \item O.B.d.A.: $i_1w(e_{i_\mu})$, \pause\\ insbesondere dabei $j_\mu w(e_{i_\mu})$, \pause d.h. Greedy-Algorithmus hätte $e_{j_\sigma}$vor $e_{i_\mu}$ in $T$ aufnehmen müssen. \pause \widerspruch \end{itemize} \end{frame} \begin{frame} Indirekter Beweis von "$\Rightarrow$": \pause \begin{itemize} \item Annahme: Austauscheigenschaft gilt nicht, \pause\\ aber Greedy liefert für jedes $w$ optimale Lösung. \pause \item Also gibt es $A,B\in{\cal U}$ mit $(\forall b\in B{\setminus} A) A\cup \{b\} \not\in{\cal U}$. \pause \item Setze $r:=|B|$ und betrachte folgende Kostenfunktion $w$: \pause $$w(e):=\left \{ \begin{array}{ll} r{+}1,&e\in A\\ \pause r,& \pause e\in B{\setminus} A\\ \pause 0,& \pause \mbox{sonst} \end{array} \right.$$ \item \pause Greedy-Algorithmus: Lösung $T$ mit $A\subseteq T$ \pause und $T\cap(B\setminus A)=\emptyset$. \pause \item Wegen $B\in {\cal U}$ gibt es auch eine Lösung $T'$ mit $B\subseteq T'$ \pause \item Dann jedoch \GLA w(T)&=& (r{+}1)\cdot |A| \pause\leq (r{+}1)\cdot (r{-}1) \pause=r^2 -1\\ \pause w(T')& \pause\geq& \pause r\cdot |B| \pause= r^2\GLE \pause Also $w(T)< w(T')$, d.h. Greedy versagt bei diesem $w$. \pause \widerspruch \end{itemize} \end{frame} \begin{frame} Also: \pause \begin{itemize} \item Teilmengensysteme erlauben die Anwendung von Greedy-Algorithmen \pause \item Matroide führen zu optimaler Lösung \pause \item Oft jedoch: Austauscheigenschaft nicht vollständig erfüllt \pause\\ (z.B.: $\exists$ mehrere maximale Mengen mit untschiedlicher Mächtigkeit) \pause\\ also Greedy-Lösung nicht optimal, sondern nur approximativ \pause \item mögliches anderes Problem: \pause\\ nicht-additive Kostenfunktion, $w(T)\neq \sum _{e\in T} w(e)$ \pause \item aber: Greedy liefert oft gute Heuristik! \end{itemize}\pause Im Folgenden: Beispiele für `gute' Greedy-Heuristiken bei \pause \begin{itemize} \item Färbbarkeit \item TSP \end{itemize} \end{frame} \begin{frame} \begin{example}[Färbbarkeit] \pause \begin{itemize} \item Gegeben Graph $G=(V,E)$ \pause \item Ziel: Färbe Knoten mit möglichst wenigen Farben, \pause\\ d.h. suche `kleines' $k\in\nz$ und Funktion $f:V\to \{0,...,k{-}1\}$, \pause\\ so dass für Kanten $(u,v)\in E$ stets $f(u)\neq f(v)$ . \pause \item Greedy-Heuristik: \pause \begin{itemize} \item Sortiere $V$ nach Grad $\delta(v)$ der Knoten $v\in V$, \pause\\ also o.B.d.A.: $V=\{v_1,...,v_n\}$ mit $\delta(v_i)\geq \delta(v_{i+1})$. \pause \item Wiederhole für $\mu=1,2,...,n$: \pause Setze \GLA f(\mu):=\min(\nz\setminus \{f(i)\mid i<\mu, \pause(v_i,v_\mu)\in E\})\GLE \item \pause Jeder Knoten erhält also, in der Reihenfolge absteigender Grade, \pause die jeweils kleinstmögliche Farbe. \end{itemize}\pause \item Jeder Graph mit maximalem Grad $\Delta$ \pause wird dabei mit höchstens $\Delta+1$ Farben gefärbt! \end{itemize} \end{example} \end{frame} \begin{frame} Aus Übung: \pause 2-färbbare (d.h. bipartite) Graphen sind in Polynomzeit färbbar! \pause Damit: \begin{lemma}\pause Jeder 3-färbbare Graph mit $n$ Knoten und Grad $\Delta$ \pause kann in Polynomzeit \pause mit ${\cal O}(\min(\Delta,\sqrt{n}))$ Farben gefärbt werden. \end{lemma} \pause Beweis dazu: \pause \begin{itemize} \item Ist $G$ 3-färbbar, \pause dann ist bei jedem Knoten $v$ die Menge $N(v)$ seiner Nachbarn 2-färbbar! \pause \item Für jeden Knoten $v\in V$ mit $\delta(v)\geq\sqrt{n}$ \pause ist $\overline{N}(v):=N(v)\cup \{v\}$ \pause also schnell mit 3 (neuen) Farben färbbar. \pause\\ Danach entferne $\overline{N}(v)$ aus dem Graphen. \pause \item Da $|N(v)|\geq \sqrt{n}$: \pause Nach maximal $\sqrt{n}$ Iterationen kein Knoten mehr in $G$ mit $\delta(v)\geq\sqrt{n}$. \pause \item Rest des Graphen dann mit $\leq\sqrt{n}$ weiteren Farben färbbar! \end{itemize}\pause Bestes bekanntes Resultat (Baumann, 2004): \pause Färbung 3-färbbarer Graphen in Polynomzeit mit ${\cal O}(n^{3/14})$ Farben... \end{frame} \begin{frame} \begin{example}[Greedy-Algorithmen für TSP]\pause \begin{itemize} \item Grundidee: Konstruiere sukzessive immer längere Strecken,\pause\\ bis schließlich eine Rundreise entsteht...\pause \item Heuristik `Nearest Neighbor':\pause \begin{itemize} \item Gehe vom aktuellen Tour-Ende \pause immer zur nächstliegenden neuen Stadt \end{itemize} \pause \item Heuristik `Tourerweiterungen':\pause \begin{itemize} \item Starte mit kurzer Tour aus zwei Städten.\pause \item Erweitere Tour iterativ um je einen Knoten; \pause Heuristiken dabei:\pause --- `Random Insertion': \pause Wähle neuen Knoten zufällig\pause --- `Farthest Insertion': \pause Wähle Knoten, dessen Minimalabstand zur aktuellen Route möglichst groß ist\pause \item Gewählter Knoten wird an optimaler Position in die Tour eingefügt. \end{itemize}\pause \item `Nearest Neighbor' ist nur mäßig erfolgreich: \pause\\ Anfangs viele kurze Strecken, \pause aber am Ende kostspieliges Einsammeln übersehener, weit auseinanderliegender Städte\pause (aber mit Nachverbesserungen evtl.\ brauchbar, s. lokale Suche)\pause \item `Farthest Insertion' scheint die bessere Heuristik zu sein: \\\pause Grobstruktur der Route wird relativ schnell festgelegt! \end{itemize} \end{example} \end{frame} \subsubsection{lokale Suche} \inhaltb{15} \begin{frame} `Lokale Suche' zur Verbesserung von gefundenen Lösungen: \begin{itemize} \item Greedy-Algorithmus liefert Startwert für Maximumsuche...\pause \item Ziel: analog zur Austauscheigenschaft \pause (tausche beliebig $a\in A$ gegen $b\in B\setminus A$) teste lokale Änderungen\pause \item z.B.: nach Konstruktion einer Lösung \pause entferne Teile der Lösung \pause und suche eine `Zeitlang' nach Verbesserungen \end{itemize}\pause Grundstruktur: \begin{programm} \bfseries\em Erzeuge eine Anfangslösung $L$.\pause\\ REPEAT\pause\\ \hspace*{3em}Modifiziere $L$ zufällig zu $L'$ \pause\\ \hspace*{3em}IF $L'$ ist besser als $L$ THEN $L=L'$ ENDIF \\ UNTIL längere Zeit keine Verbesserung gefunden\\ AUSGABE von $L$ \end{programm} \pause Prinzipieller Nachteil: \pause \begin{itemize} \item die gefundene Lösung ist ein `lokales Optimum'... \item das globale Optimum kann beliebig weit entfernt sein! \end{itemize} \end{frame} \begin{frame} \begin{example}[2-Opt-Heuristik bei TSP] \pause \begin{itemize} \item Betrachte TSP mit symmetrischen Entfernungen $m_{i,j}=m_{j,i}$ \pause \item Lösungen mit unendlichen Kosten seien erlaubt! \pause \item Beginne mit beliebiger Permutation $\pi$ der Knoten \pause(zulässig!) \pause \item Wähle zufällig zwei Knoten $\pi(i)$, $\pi(j)$ \pause (mit $i \pause m_{\pi(i),\pi(j)}+m_{\pi(i+1),\pi(j+1)}\GLE \pause gilt, dann gibt es eine kürzere Route / bessere Permutation: \pause {\small\GLA & \fbox{\includegraphics[width=0.35\linewidth]{grafik/tsp-2opt-1.pdf}} \Rightarrow\fbox{\includegraphics[width=0.35\linewidth]{grafik/tsp-2opt-2.pdf}}\\ &\leadsto \pause\pi(1)\pi(2)...\pi(i) \pause \pi(j)\pi(j{-}1)...\pi(i{+}2)\pi(i{+}1) \pause\pi(j{+}1)...\pi(n)\GLE} \item \pause Animation: \href{http://www-e.uni-magdeburg.de/mertens/TSP/TSP.html}{www-e.uni-magdeburg.de/mertens/TSP/TSP.html} \pause \item Laufzeit und Güte der Heuristik sind unbekannt! \end{itemize} \end{example} \end{frame} \begin{frame} Weitere Heuristiken: \pause \begin{itemize} \item Grundidee des \Fb{Simulated Annealing} (simulierte Abkühlung): \pause \begin{itemize} \item erlaube bei der lokalen Suche auch Zwischenlösungen, \pause die um $c(t)$ schlechter sind als die aktuelle Lösung \pause \item aber: $c(t)$ geht mit wachsender Rechenzeit gegen $0$, etwa $$c(t)={\cal O}(1/\log t)$$ \end{itemize} \pause \item Grundidee der \Fb{genetischen Algorithmen}: \pause \begin{itemize} \item Speichere mehrere verschiedenartige Lösungen \pause \item Kombiniere jeweils meherere Lösungen und verwende die besseren Resultate \end{itemize} \end{itemize} \end{frame} % \subsubsection{Datenreduktionstechniken} % \begin{frame} % metaheuristische Ideen % \end{frame} \subsection{Randomisierte Verfahren} \subsubsection{Probabilistische Turingmaschinen} \inhaltb{15} \begin{frame} Bisher:\\ Nichtdeterminismus als \Fb{ M\"o{}glichkeit}, eine Eingabe zu akzeptieren.\pause Naheliegend auch:\\ \begin{itemize} \item \Fb{ Wahrscheinlichkeit} der Akzeptanz einer Eingabe \pause bzw. \item \Fb{ Wahrscheinlichkeit} der Erzeugung einer Ausgabe \end{itemize} \pause Annahme hier:\pause \begin{itemize} \item jeder Befehl zufällig ausgewählt, mit \Fb{ gleicher Wahrscheinlichkeit}\pause \item die Einzel-Auswahlen seien \Fb{unabhängig} voneinander. \end{itemize} \end{frame} \begin{frame} \begin{definition} \begin{itemize} \item Eine \Fb{ probabilistische Turingmaschine} $M$ \pause ist zunächst genauso definiert wie eine nichtdeterministische Turingmaschine.\pause \item Die Wahrscheinlichkeit $$\Fb{ Prob(K{\stackrelall{}{\longrightarrow}{M}}K')}$$ \pause mit der bei~$M$ eine Konfiguration $K$ in eine Konfiguration $K'$ \"u{}bergeht, \pause wird definiert als: \GLA &&\Fb{ Prob(K{\stackrelall{}{\longrightarrow}{M}}K')}:=\\&&\pause \left\{\begin{array}{cl} j/i, &\pause \mbox{falls }K\stackrelall{}{\longrightarrow}{M}K' \mbox{ mit }\\ &\pause i:=\mbox{ Anzahl der bei $K$ ausf\"u{}hrbaren Befehle} \\ &\pause j:=\mbox{ Anzahl dieser Befehle, bei denen aus $K$ $K'$ wird} \\ \pause 0, & \pause \mbox{sonst} \end{array}\right. \GLE \end{itemize} \end{definition} \end{frame}\begin{frame} \begin{cont}{} \begin{itemize} \item Die Wahrscheinlichkeit $$\Fb{Prob(K{\stackrelall{t}{\longrightarrow}{M}}K')}$$ \pause mit der bei $M$ nach $t$ Schritten aus der Konfiguration $K$ die Konfiguration $K'$ wird, \pause ergibt sich induktiv als:\pause \[\Fb{ Prob(K{\stackrelall{0}{\longrightarrow}{M}}K')}:= \pause \left\{\begin{array}{ll} 1,& K=K'\\ 0,& K\neq K' \end{array}\right.\]\pause \[\Fb{ Prob(K{\stackrelall{t+1}{\longrightarrow}{M}}K')}:=\pause \sum_{\!\!\!\!\!\!K''\;{\rm Konfiguration}\!\!\!\!\!\!}\pause Prob(K{\stackrelall{t}{\longrightarrow}{M}}K'') \cdot Prob(K''{\stackrelall{}{\longrightarrow}{M}}K') \] \end{itemize} \end{cont} \end{frame} \begin{frame} \begin{cont}{} \begin{itemize} \item Per Definition: Nach Erreichen einer Endkonfiguration bleibt $M$ stehen und rechnet nicht mehr weiter.\pause \item Also ist f\"u{}r Endkonfigurationen $K'$ sinnvoll definiert:\pause $$\Fb{ Prob(K{\stackrelall{*}{\longrightarrow}{M}}K')}$$ \pause mit der bei $M$ nach beliebiger Zahl von Schritten aus $K$ diese Endkonfiguration $K'$ wird:\pause \[\Fb{ Prob(K{\stackrelall{*}{\longrightarrow}{M}}K')}:= \sum_{t= 0}^\infty Prob(K{\stackrelall{t}{\longrightarrow}{M}}K')\] \end{itemize} \end{cont} \end{frame}\begin{frame} \begin{cont}{} \begin{itemize} \item Setze $Acc_M(y):=$ Menge aller Endkonf., die zur Ausgabe $y$ führen\pause \item $I_M(x):=$ Startkonfiguration von $M$ bei Eingabe von $x$\pause \item Wahrscheinlichkeit, mit der aus Eingabe $x$ die Ausgabe $y$ wird:\pause \[ \Fb{ Prob(x{\stackrelall{}{\mapsto}{M}}y)}\pause := \sum_{ K'\in Acc_M(y)} Prob(I_M(x){\stackrelall{*}{\longrightarrow}{M}}K')\] \item \pause Wahrscheinlichkeit, mit der bei $x$ kein Ergebnis geliefert wird:\pause \[\Fb{ div_M(x)}:=\pause 1-\pause \sum_y Prob(x{\stackrelall{}{\mapsto}{M}}y)\] \end{itemize} \end{cont} \end{frame} \begin{frame} Da $M$ mit Erreichen einer Endkonfiguration endet:\pause $$\sum\{Prob(I_M(x){\stackrelall{*}{\longrightarrow}{M}}K')\mid K'\mbox{ Endkonfiguration}\}\leq 1$$ \pause Damit f\"u{}r jedes $x$ $$\sum_{y}Prob(x{\stackrelall{}{\mapsto}{M}}y)\leq 1$$ \pause Beide Werte k\"o{}nnen echt kleiner als 1 sein, da m\"o{}glicherweise nicht bei jeder Berechnung eine Endkonfiguration erreicht wird! \end{frame} \begin{frame} \begin{definition}\begin{itemize} \item Die von einer probabilistischen Turingmaschine $M$ berechnete Funktion $f^{(p)}_M$ wird wie folgt definiert:\pause \[\Fb{ f^{(p)}_M(x)}\pause := \left\{\begin{array}{cl} y,&\pause \mbox{ falls } Prob(x{\stackrelall{}{\mapsto}{M}}y)>1/2\\[1ex] \pause \mbox{undefiniert},& \pause \mbox{ falls $Prob(x{\stackrelall{}{\mapsto}{M}}y)\leq1/2$ f\"u{}r alle $y$} \end{array}\right.\] \item \pause Die von $M$ akzeptierte Sprache $L^{(p)}_M$ wird definiert durch\pause \GLA\Fb{ L^{(p)}_M}:=\{x\mid f^{(p)}_M(x)=0\}\GLE \item\pause Die Fehlerwahrscheinlichkeit, mit der $f^{(p)}_M$ berechnet wird, ist \pause \[\Fb{err_M(x)}:= \pause \left\{\begin{array}{ll} 1-div_M(x)&\\ ~~~-Prob(x{\stackrelall{}{\mapsto}{M}}f^{(p)}_M(x)),& \pause \mbox{ falls $f^{(p)}_M(x)$ definiert ist}\\[1ex] \pause \mbox{undefiniert},& \pause \mbox{ sonst}\end{array}\right.\] \end{itemize}\end{definition} \end{frame} \begin{frame}\begin{example}[Probabilistische Turingmaschine]\label{probTM} Nichtdeterministische (=probabilistische) Maschine $M$: {\small \GLA \begin{array}[b]{@{}c@{}}\includegraphics[width=.35\textwidth]{grafik/probabTM2.pdf}\\[-4ex] \end{array} \pause\begin{array}[b]{c@{\,}l@{}}&\mbox{Beispiele für Konfigurationsfolgen bei $M$:}\\ \pause\mbox{(a)}&\pause s_0\Fb{0}\pause\to 0s_1\Box\pause\to s_3\Fb{0}\Box\\[.3ex] \pause\mbox{(b)}&\pause s_0\Fb{0}\pause\to 1s_1\Box\pause\to s_3\Fb{1}\Box\\[.3ex] \pause\mbox{(c)}&\pause s_0\Fb{0}\pause\to s_20\pause\to 0s_1\Box\pause\to s_3\Fb{0}\Box\\[.3ex] \pause\mbox{(d)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 10s_1\Box\pause\to 1s_3\Fb{0}\Box\\[.3ex] \pause\mbox{(e)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 11s_1\Box\pause\to 1s_3\Fb{1}\Box\\[.3ex] \pause\mbox{(f)}&\pause s_0\Fb{1}\pause\to s_21\pause\to 1s_0\Box\pause\to 1s_2\Box\\ &\pause\mbox{~~~~~~} \to 1\Box s_0\Box\pause\to 1\Box s_2\Box\pause\to 1\Box\Box s_0\Box\pause... \end{array} \GLE} \begin{itemize} \item \pause Hier gilt $Prob(x{\stackrelall{}{\mapsto}{M}}y) = 0$, wenn $y\not\in \{0,1\}$\pause \item $ Prob(1{\stackrelall{}{\mapsto}{M}}0) \pause= Prob(1{\stackrelall{}{\mapsto}{M}}1) \pause= \frac{1}{3}\pause+\frac{1}{3^2}\pause+\frac{1}{3^3}\pause+...\pause={\displaystyle \sum_{i=1}^\infty}(\frac{1}{3})^i\pause=\frac{1}{2}$\\ \pause also $div_M(1)=0$, \pause zudem ist $f_M^{(p)}(1)$ nicht definiert.\pause \\(Achtung: $M$ könnte trotzdem unendlich oft zykeln!) \end{itemize} \end{example} \end{frame} \begin{frame} \begin{cont}{Probabilistische Turingmaschine} \begin{itemize} \item analog für $v=\underbrace{1...1}_{i}$ (bei $i\geq 0$):\pause $$Prob(v{\stackrelall{}{\mapsto}{M}}0) \pause= Prob(v{\stackrelall{}{\mapsto}{M}}1) \pause=\textstyle\frac{1}{2}$$ \pause also $div_M(v)=0$ \pause und $f_M^{(p)}(v)$ ist nicht definiert.\pause \item für $\displaystyle w:=\underbrace{1...1}_{i}0$ ergibt sich jedoch:\pause \GLA Prob(w{\stackrelall{}{\mapsto}{M}}0)=&\pause\displaystyle \sum_{j=1}^{i+1} \frac{1}{3^j}+\pause \frac{1}{3^{i+1}}&\pause= \frac{1}{2}\cdot(1+\frac{1}{3^{i+1}})\\ \pause Prob((w{\stackrelall{}{\mapsto}{M}}1)=&\pause\displaystyle \sum_{j=1}^{i+1} \frac{1}{3^j}&\pause = \frac{1}{2}\cdot(1-\frac{1}{3^{i+1}})\GLE \pause damit: $f^{(p)}_M(w)=0$, \pause$div_M(w)=0$ \pause und $err_M(w)= \frac{1}{2}\cdot(1-\frac{1}{3^{i+1}})$ \end{itemize} \end{cont} \end{frame} \begin{frame} \begin{cont}{Probabilistische Turingmaschine} Betrachte z.B. Spezialfall $w=10$\pause \begin{itemize} \item Zunächst: \GLA Prob((w{\stackrelall{}{\mapsto}{M}}1)&=&\frac{1}{2}\cdot(1-\frac{1}{3^{2}})\pause \approx 0.444...=:\varepsilon\\ \pause Prob(w{\stackrelall{}{\mapsto}{M}}0)&\pause =&\pause \frac{1}{2}\cdot(1+\frac{1}{3^{2}})\pause \approx 0.555...=1-\varepsilon\GLE\pause \item Jetzt: Lasse $M$ $n$-fach laufen, zähle Anzahl positiver/negativer Resultate\\ \pause Dann gibt es $n{+}1$ Möglichkeiten: \begin{tabular}{|cc||c|}\hline Ausgabe $1$ & Ausgabe $0$ &Wahrscheinlichkeit\\\hline \pause $n$-fach &\pause $0$-fach&\pause $\varepsilon^n$\\\hline \pause $n{-}1$-fach & \pause $1$-fach &\pause $n\cdot \varepsilon^{n-1}\cdot (1{-}\varepsilon)$\\\hline \pause ... &&\pause ...\\\hline \pause $1$-fach & \pause $n{-}1$-fach& \pause $n\cdot \varepsilon^1\cdot (1{-}\varepsilon)^{n-1}$\\\hline \pause $0$-fach & \pause $n$-fach&\pause $(1-\varepsilon)^n$\\\hline \end{tabular} \end{itemize} \end{cont} \end{frame} \begin{frame} \begin{cont}{Probabilistische Turingmaschine} \begin{itemize} \item Die Wahrscheinlichkeit $p(n)$, dass mehr als die Hälfte der Ausgaben $1$ sind, fällt exponentiell mit $n$:\pause \GLA p(n)&=&\pause \sum_{i=0}^{\lfloor n/2\rfloor}\textstyle\binom{n}{i}(1{-}\varepsilon)^i\varepsilon^{n-i}\\ &\pause \leq&\pause \sum_{i=0}^{\lfloor n/2\rfloor}{\textstyle\binom{n}{i} (1{-}\varepsilon)^i\varepsilon^{n-i}\pause \left(\frac{1{-}\varepsilon}{\varepsilon}\right)^{n/2-i}}\pause \mbox{ da $\varepsilon<1/2$, $i\leq n/2$} \\ &\pause =&\pause (\varepsilon(1{-}\varepsilon))^{n/2}\cdot \sum_{i=0}^{\lfloor n/2\rfloor}\textstyle\binom{n}{i} \pause \leq(\varepsilon(1{-}\varepsilon))^{n/2}\cdot2^{n}\pause = \delta^n \GLE \pause mit der Setzung von $\delta=2\sqrt{\varepsilon(1{-}\varepsilon)}$ \pause (wobei insbesondere $\delta < 1$).\pause \item Um Fehler $p(n)\leq 10^{-k}$ zu erhalten, \pause reicht also $n\geq k\cdot\frac{1}{-\log_{10}\delta}$\pause \item Im Beispiel: $\varepsilon= 0.444...$, \pause $\delta=0.9938...$, \pause $\frac{1}{-\log_{10}\delta}\approx 370$,\\\pause d.h. nach $n=3700$ Wiederholungen ist $p(n)\leq 10^{-10}$ \end{itemize} \end{cont} \end{frame} \begin{frame} \begin{definition}\pause Sei $M$ probabilistische Turingmaschine, bei der $f^{(p)}_M(x)$ stets existiert.\pause \begin{enumerate} \item $M$ hei\ss{}t \Fb{ Random-Turingmaschine}, wenn f\"u{}r $x\not\in L^{(p)}_M$ gilt:\pause $$Prob(x{\stackrelall{}{\mapsto}{M}}0) = 0$$ \pause ($M$ erkennt $L^{(p)}_M$ mit einseitiger Fehlerwahrscheinlichkeit 0.)\pause \item $M$ hei\ss{}t \Fb{ Monte-Carlo-Turingmaschine}, \pause wenn ein $\varepsilon<1/2$ existiert, \pause so da\ss{} f\"u{}r alle $x$ stets gilt:\pause $$err_M(x){+}div_M(x)<\varepsilon$$ \pause ($M$ berechnet $f^{(p)}_M$ mit beschr\"a{}nkter Fehlerwahrscheinlichkeit.)\pause \item $M$ hei\ss{}t \Fb{ Las-Vegas-Turingmaschine}, \pause wenn f\"u{}r alle $x$ stets gilt:\pause $$err_M(x)=0$$ \pause ($M$ berechnet $f^{(p)}_M$ mit Fehlerwahrscheinlichkeit 0.) \end{enumerate} \end{definition} \end{frame}\begin{frame} Interpretation der Definitionen: \pause \begin{enumerate} \item Ergibt bei einer \Fb{ Random-Turingmaschine} $M$ eine Berechnung die Ausgabe 0, \pause so gilt \Fb{ sicher} $x\in L^{(p)}_M$.\pause \item Bei einer \Fb{ Monte-Carlo-Turingmaschine} $M$ wird das \Fb{ richtige Ergebnis $f^{(p)}_M(x)$ mit signifikant h\"o{}herer Wahrscheinlichkeit ($>1/2$)} ausgegeben als irgendein falsches ($<\varepsilon<1/2$).\pause Dabei ist $\varepsilon$ unabh\"a{}ngig(!) von $x$.\pause \item Eine \Fb{ Las-Vegas-Turingmaschine $M$ `l\"u{}gt' nie}, \pause liefert aber mit Wahrscheinlichkeit $div_M(x)<1/2$ \"u{}berhaupt kein Ergebnis.\pause Jede Las-Vegas-Maschine ist per Definition auch eine Random-Maschine. \end{enumerate} \pause Zeitkomplexit\"a{}t über zwei Vorgehensweisen definierbar:\pause \begin{itemize}\item über den Erwartungswert der Rechenzeit\pause \item über die Zeit, die benötigt wird, um die Ausgabe mit einer gewissen Wahrscheinlichkeit festzulegen. \end{itemize} \end{frame}\begin{frame} \begin{definition} Sei $M$ eine probabilistische Turingmaschine. \pause Die durchschnittliche (oder erwartete) Rechenzeit $\Fb{ T_M^\emptyset(x)}$ \pause von $M$ bei einer Eingabe $x$ ist definiert als\pause \[\Fb{ T_M^\emptyset(x)} :=\pause \left\{\begin{array}{cl} \displaystyle \sum_{t=0}^\infty t\cdot \sum_{K\,{\rm Endkonf.}} Prob(I_M(x)\stackrelall{t}{\longrightarrow}{M}K), &\pause \mbox{ falls $div_M(x)=0$}\\ \\ \pause \infty, \mbox{ sonst} \end{array}\right. \] \pause F\"u{}r $\varepsilon\leq 1/2$ sei $\Fb{ T_M^\varepsilon(x)}$ \pause die Zeit, nach der $f_M^{(p)}(x)$ mit Wahrscheinlichkeit $1{-}\varepsilon$ festliegt:\pause \[\Fb{ T_M^\varepsilon(x)}:= \min\{t\in\nz\mid 1{-}\varepsilon < \sum_{\!\!\!K\in Acc_M(f_M^{(p)}(x)),\;\;t'\leq t\!\!\!} Prob(I_M(x)\stackrelall{t'}{\longrightarrow}{M}K)\;\}\] \end{definition} \end{frame} \begin{frame} \begin{example}[probabilistische Zeitkomplexität] Sei $M$ wie im Beispiel \ref{probTM}\pause \begin{itemize} \item Betrachte zunächst $v=1...1$:\pause \GLA T_M^\emptyset(v)&=&\pause \frac{2}{3}\cdot 2 + \frac{2}{3^2}\cdot 4 + \frac{2}{3^3}\cdot 6 + ...\\ &\pause =&\pause 4\cdot \sum_{t=1}^\infty \frac{t}{3^t}\pause \stackrel{*}{=} 4\cdot (\frac{1/3}{(1-1/3)^2})\pause = 3 \GLE \pause Zu $(*)$: Für $p<1$ gilt $\displaystyle \sum_{i=0}^\infty \frac{i}{p^i}=\frac{p}{(1-p)^2}$\pause \\ (Beweis über $\displaystyle \sum_{i=0}^\infty \frac{1}{p^i}=\frac{1}{1-p}$ \pause und $\displaystyle\frac{\mbox{d}}{\mbox{d}p}\frac{1}{1-p}=\frac{1}{(1-p)^2}$~~)\pause \item Für beliebige $w$ immer $T_M^\emptyset(w)\leq T_M^\emptyset(1...1)$, \pause wenn $|w|=|1...1|$.\pause \item Also: Bei $M$ ist für alle $w$ die erwartete Rechenzeit $T_M^\emptyset(w)\leq 3$. \end{itemize} \end{example} \end{frame} \begin{frame} \begin{cont}{probabilistische Zeitkomplexität} Andererseits:\pause \begin{itemize} \item $T_M^{1/2}(1...1)=\mbox{undef}$, \pause da $f_M^{(p)}$ undefiniert ist\pause \item $T_M^{1/2}(\underbrace{1...1}_i0)=2i+2$\pause \item $T_M^{1/3}(\underbrace{1...1}_i0)=\mbox{undef}$, \pause da $Prob_M(1...10\mapsto 0)\leq 2/3$ \end{itemize} \end{cont} \pause daher:\pause \begin{itemize} \item erwartete Zeit ist im Allgemeinen ungeeignetes Maß...\pause \item f\"u{}r viele Probleme gibt es probabilistische Maschinen mit konstanter erwarteter Rechenzeit\pause \item Ausnahme: Las-Vegas-Maschinen, hier wird die erwartete Zeit verwendet \end{itemize} \end{frame} \begin{frame} \begin{example}[Quicksort als Las-Vegas-Algorithmus]\pause Gegeben Feld $a[1],...,a[n]$, \pause Ziel: rekursive Sortierfunktion $qs$:\pause \begin{itemize} \item $qs(i,j)$ sortiert Teilfeld $a[i]...a[j]$, \pause d.h. Aufruf mit $qs(1,n)$\pause \item $qs(i,j)$ arbeitet wie folgt:\pause \begin{enumerate} \item[(1)] Wähle $k$ mit $i\leq k\leq j$\pause \item[(2)] Modifiziere $a[i]...a[j]$ so, \pause dass $a[k]$ an eine Stelle $m$ kommt mit \pause \GLA (\forall \nu, i\leq \nu\leq m) & a[\nu]\leq a[m]\\ \pause (\forall \nu, m\leq \nu\leq j) & \pause a[m]\leq a[\nu]\GLE \item[(3)]\pause Falls $i< m{-1}$: Rekursiver Aufruf von $qs(i,m{-}1)$\pause \item[(4)] Falls $ m{+1}< n Matrizen multiplizieren. % Verifrzieren, dass das Ergebnis richtig ist, kann man mit einem probabilistischen Algo- % rithmus mit Komplexität O(n2), siehe Abschnitt 9.3. % Ein weiteres Beispiel ist der erweiterte Euklidsche Algorithmus (Abschnitt 9.6). Dieser % Algorithmus berechnet (a, b) »—> (d, az, y), wobei d = ggt(a, b) und d = cm: + by gelten % soll. Die Korrektheit des Ergebnisses kann durch Testen auf d\ a, d\ b und d = am + by % bestätigt werden. % Oft ist es so, dass die Art der Programmierung bereits als ,,Seiteneffekt" eine über- % prüfbare Datenstruktur hinterlässt, anhand der die Korrektheit des errechneten Ergeb- % nisses nachvollzogen werden kann. Bei Algorithmen nach dem Prinzip dynamisches % Programmieren (Kapitel 4) wird am Ende eine vollständig ausgefüllte Tabelle hinter- % lassen, die in aller Detailliertheit ,,nachweist“, dass das Ergebnis korrekt ist (allerdings % wird der Veriiikationsalgorithmus nicht wesentlich effizienter sein als der eigentliche % Algorithmus). % Es ist beispielsweise wünschenswert, dass man bei einem Entscheidungsproblem A in % NP (siehe Abschnitt 1.14), das man ja ganz allgemein über eine polynomial entscheid- % bare Relation R beschreiben kann und welches die Form hat % $A = {cz | es gibt eine Zusatzeingabe y, so dass (0:,3,;) E R}$ % vom Algorithmus nicht nur die Antwort ,,ja" (es gibt eine Zusatzeingabe y mit (ar, y) E % R) oder ,,nein" (es gibt keine) erfährt. Im Falle der Antwort ,,ja" sollte das System % die entsprechende Zusatzeingabe y ebenso bereitstellen (und mit Hilfe der polynomial % entscheidbaren Relation R kann so die Korrektheit der ,,ja" Antwort überprüft wer- % den). Auch die Antwort ,,nein" sollte im Idealfall durch die Ausgabe eines ,,Beweises" % bestätigt werden können. (Im Falle von NP—vollständigen Problemen ist die effiziente % Verifikation der ,,nein" Ausgabe allerdings nicht möglich, da dieses implizieren würde, % dass das betreffende Problem nicht nur in NP sondern auch in co—N P , also in N PO co- % NP, liegt. Hieraus würde folgen NP = co—N P). % \end{frame} % % \begin{frame} % Bei anderen Aufgabenstellungen (die nicht NP-vollständig sind) lässt sich ein Verifika- % tionsmechanismus sowohl für den ,,ja“ als auch für den ,,nein" Fall bereitstellen. Be- % trachten wir beispielsweise die Aufgabe, festzustellen, ob ein gegebener Graph planar % ist. Sollte der Graph planar sein, so kann man vom Programm eine planare Einbettung % des Graphen in die Ebene zeigen lassen. Sollte der Graph nicht planar sein, so kann % man verlangen, dass der im Graphen versteckte K 5 oder K 3,3 gezeigt wird. (Siehe hier- % zu jedes Buch über Graphentheorie; Stichwort: Satz von Kuratowski). % Bei numerischen Verfahren kann sich der Verifikationsmechanimus ausschließlich % auf die Eingrenzung des Rundungsfehlers beziehen. Synchron mit der eigentlichen % Ausführung des numerischen Verfahrens wird bei jeder durchgeführten arithmetischen % Rechenoperation abgeschätzt, wie groß sich hierbei der Rundungsfehler entwickeln % könnte (im worst-case oder im average-case). Am Ende entsteht parallel mit dem ei- % gentlichen Rechenergebnis eine Abschätzung über den mit dem Ergebnis gehafteten % Rundungsfehler. Es kann überprüft werden, ob der Rundungsfehler im Toleranzbereich % liegt, oder ob die Rechnung von Neuem gestartet werden sollte mit einer veränderten % Anzahl von Iterationsschritten und/oder ob mit einer längeren Zahlendarstellung gear- % beitet werden sollte. % Das allgemeine Modell für einen Verifikationsmechanismus ist wie folgt. Der eigentli- % che Algorithmus zur Lösung eines Problems oder Berechnung einer Funktion wird um % eine Veriiikationskomponente ergänzt, die aus der Ein- und Ausgabe, sowie aus Daten, % die während des eigentlichen Algorithmenablaufs erhoben werden, einen veriiizierba- % ren Beweis für die Korrektheit des Ergebnisses berechneti % :6 Algorithmus I y % erifikationsalg. ,,Beweis" % \end{frame} % % \begin{frame} % Interessant ist der Pfeil vom Verifikationsalgorithmus zum eigentlichen Algorithmus. In % manchen Situationen kann nämlich der Veriiikationsprozess so vonstatten gehen, dass % abgesehen von der eigentlichen Berechnung az •—> y der Verifikationsalgorithmus den % Algorithmus als Unterprogramm verwendet und einige weitere Berechnungen w' e-> y' % einfordert. Diese Rechenergebnisse werden verwendet, um deren Konsistenz mit der % eigentlichen Berechnung m i—> y, und damit die Korrektheit von y zu bestätigen. % Bei den zu Beginn dieses Abschnitts aufgeführten Beispielen war es so, dass der Ve- % rifikationsvorgang effizienter durchgeführt werden kann als der eigentliche Berech- % nungsvorgang. Das heißt, für die entsprechenden Komplexitätsfunktionen Tcheck (n) % und Twmpute (ri) gilt Tcheck (ri) = 0(Tc„„,p„„ (n)). Wenn nun aber der Verifikati- % onsalgorithmus den Berechnungsalgorithmus sozusagen als Unterprogramm verwen- % det, so wird man diese Eigenschaft nicht erfüllen können. Aber man sagt, dass ein % Entscheidungsproblem polyriomial verüizierbar (polynomially checkable) ist, wenn % es einen Verifikationsalgorithmus gibt, so dass für die Komplexitätsfunktionen gilt % Tchcck (ri) = p(Tc,„„,,„„ (11)) wobei p ein Polynom ist. (Man beachte, dass Tcompute (ri) % keine polynomial beschränkte Funktion zu sein braucht). % Beispiel: Ein bekanntes Beispiel für ein Problem, das einen polynomialen Verif1kations— % mechanismus zulässt, ist das Graphenisomorphieproblem (vgl. Seite 76). Die Eingabe % besteht aus zwei Graphen G und H. Der ,,eigentliche" Algorithmus liefert lediglich die % Antwort ,,ia" oder ,,nein", je nach dem, ob die beiden Graphen (seiner Meinung nach) % isomorph sind oder nicht. Man beachte, dass bisher kein polynomialer Algorithmen für % das Graphenisomorphieproblem bekannt ist. Es ist aber trotzdem auch unwahrschein- % lich, dass das Problem NP—vollständig ist (insbesondere aufgrund des hier angegebenen % Ergebnisses, das das Graphenisomorphieproblem von den anderen NP—vollständigen % \ Problem unterscheidet). % \end{frame} % % \begin{frame} % E Der hinzu kommende Verifikationsmechanismus ist nun der Folgende: Wenn der ge- % Hjj gebene Algorithmus behauptet, die Graphen seien isomorph, so soll zum Beweis ein % ( Isomorphismus konstruiert werden. Dies kann man mit Hilfe der so genannten Selbst- % J reduktionsstruktur des Graphenisomorphieproblems erreichen. Und zwar kann man an % ff einen Knoten u von G und einen Knoten 11 von H probehalber zwei identische Testgra- % Ä phen über eine zusätzliche Kante anschließen. Diese Testgraphen können zum Beispiel % 1 zwei Cliquen mit n -l- 1 Knoten sein, denn diese können sonst nirgends im eigentlichen % H Graphen als Teilgraph vorkommen. Daher können die Testgraphen von einem potenziellen lsomorphismus nur aufeinander abgebildet werden und ferner muss dann u auf v % abgebildet werden. V % K % i % \end{frame}