%% -*- mode: latex; TeX-master: "informatik.tex"; -*-

\begin{slide}{Suchprobleme}

\kopf{$ $Id: expo.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp $ $}

Viele Aufgaben lassen sich als Such-Probleme formulieren.

Beispiel 1 (COL): gegeben sind ein Netzplan (ein Graph, bestehend
aus Knoten und Kanten) sowie eine Zahl $c$ von Farben.
gesucht ist eine Färbung der Knoten,
so daß keine Kante zwischen gleichfarbigen Knoten verläuft.

\end{slide}

\begin{slide}{Suchprobleme: Lunar Lockout}
Beispiel 2 (
\url{http://www.thinkfun.com/buy/games/lunarLockout.html}):
\begin{minipage}{0.6\textwidth}
Die Großbuchstaben bezeichnen die Roboter.
Die Aufgabe ist, $A$ auf die (anfangs leere)
Position $a$ zu bewegen.

Roboter fahren geradlinig, ohne Bremse, 
bis zu Hindernis ($=$ anderer Roboter).

Rand ist \emph{kein} Hindernis
\end{minipage}
\hspace*{10pt}
\begin{minipage}{0.3\textwidth}
\begin{small}
\begin{verbatim}
B . . . E . . . A
. D . . . . . C .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . a . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
G . . . . . . . F
\end{verbatim}
\end{small}
\end{minipage}

Ähnliches Spiel: Ricochet Robot (Rasende Roboter) von Alex Randolph,
\url{http://sunsite.informatik.rwth-aachen.de/keirat/txt/R/Rasenrob.html}

\end{slide}

\begin{slide}{Suchprobleme (2)}

Bei COL ist der Suchraum beschränkt:
es gibt nur ${|\textrm{Farben}|}^{|\textrm{Knoten}|}$ verschiedene Färbungen.

Für jede Färbung kann man \emph{schnell} (polynomiell) prüfen, 
ob sie Konflikte enthält.

\dots es gibt aber \emph{exponentiell viele} Färbungen.

\bigskip

COL gehört zur Komplexitätsklasse NP.

Bedeutung des Namens:
\begin{itemize}
\item
  N: es ist ein Suchproblem
\item
  P: der Suchbaum ist nur polynomiell tief \dots
\end{itemize}
\dots aber exponentiell breit.

Aufgabe: wie komplex ist 2COL (2 Farben)?

\end{slide}

\begin{slide}{Suchprobleme}

Bei \emph{Lunar Lockout} ist eine \emph{Folge} von Zügen gesucht.

Nach jeder Folge entsteht eine bestimmte Konfiguration.

Für ein Spielfeld mit $f$ Feldern (z. B. $f=9 \cdot 10=90$)
und $r$ Robotern (z. B. $r=7$) gibt es $\le (f+1)^r$ Konfigurationen.

In \emph{kürzesten Lösungen}
gibt es keine Wiederholungen von Konfigurationen.

Falls eine Konfiguration \emph{überhaupt} lösbar ist,
dann hat sie auch eine Lösung mit $\le (f+1)^r$ Zügen.

\newpage

In jeder Konfiguration gibt es $\le 4 \cdot r$ Züge.

Der Suchraum ist ein Baum der Tiefe $\le (f+1)^r$.

Jeder Knoten hat $\le 4 \cdot r$ direkte Nachfolger.

Der Baum hat insgesamt $\le (4 \cdot r)^{(f+1)^r}$ Knoten.

Das ist eine (große, aber) endliche Zahl.

$\Rightarrow$
Das Problem 
\begin{itemize}
\item
  Eingabe: eine Lunar-Lockout-Konfiguration
\item
  Frage: gibt es eine Zugfolge, die $A$ nach $a$ bewegt?
\end{itemize}
ist \emph{entscheidbar}. 

(D. h.: es gibt einen Algorithmus,
der für jede Eingabe in endlicher Zeit die richtige Antwort ausgibt.)

\end{slide}

\begin{slide}{Suchprobleme (3)}

Beispiel 3 (PCP, Postsches Korrespondenz-Problem,
Emil Post): 

Gegeben ist eine Liste von Wort-Paaren.
Gesucht ist eine Folge (von Kopien dieser Paare),
bei der die Verkettung alle linken Seiten
das gleiche Wort ergibt wie die Verkettung aller rechten Seiten.

Beispiele: 
\( 
\begin{array}{c|c|c}
  bba & a & b \\ \hline
  b & b & ab
\end{array}
\quad
\begin{array}{c|c|c}
  aab & a & b \\ \hline
  a & b & aab
\end{array}
\)

Das linke hat kürzeste Lösung $[1,1,3,2,3,3,2,3]$.

Aufgabe: finde Lösung für das rechte (es gibt eine).

\newpage

Jetzt ist der Suchraum (alle Folgen) gar nicht beschränkt
(die Folgen können beliebig lang sein).

Tatsächlich ist PCP \emph{nicht entscheidbar}!

(Es gibt \emph{keinen} Algorithmus, der für \emph{jede} Liste von Paaren
in endlicher Zeit korrekt entscheidet, 
ob es eine Lösungsfolge gibt.)

\end{slide}
