% 8. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=16,12cm
\textheight=26,3cm
\hoffset = -19mm
\voffset = -28mm

\setcounter{page}{9}
\begin{document}

\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 8.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Dienstag, 18. J\"anner 2000.
\par \medskip
\end{centering}
\hrule
\medskip

\begin{enumerate}
\setcounter{enumi}{40}


\item (13 Punkte)
Graphenalgorithmen in der k"unstlichen Intelligenz.  % \\
Die folgende Aufgabe findet sich in einer Sammlung von Rechenaufgaben
mit dem Titel \emph{Propositiones ad acuendos juvenes} (Aufgaben 
zur Sch"arfung des Geistes der Jugend),
die wahrscheinlich
um das Jahr 800 am Hof Karls des Gro"sen entstanden ist
und Alkuin von York zugeschrieben wird:

%\begin{quote}
Die Aufgabe vom Wolf, der Ziege und dem Kohlkopf.
Ein Mann musste einen Wolf, eine Ziege und einen
Kohlkopf "uber einen Fluss "ubersetzen;
er konnte aber nur ein Boot auftreiben, das 
gerade zwei von ihnen tragen konnte.
Wie konnte er alles unversehrt hin"uberbringen?%
\footnote{PROPOSITIO DE LUPO ET CAPRA ET FASCICULO CAULI.
Homo quidam debebat ultra fluvium transferre 
lupum et capram et fasciculum cauli, 
et non potuit aliam navem invenire, 
nisi quae duos tantum ex ipsis ferre valebat. 
Praeceptum itaque ei fuerat, ut omnia haec ultra 
omnino illaesa transferret. 
Dicat, qui potest, quomodo eos illaesos ultra transferre potuit.
SOLUTIO.
Simili namque tenore ducerem prius capram et dimitterem 
foris lupum et caulum. 
Tum deinde venirem lupumque ultra transferrem, 
lupoque foras misso rursus capram navi receptam ultra reducerem, 
capraque foras missa caulum transveherem ultra, 
atque iterum remigassem, capramque assumptam ultra duxissem. 
Sicque faciente facta erit remigatio salubris absque voragine lacerationis.
}
%\end{quote}
\begin{enumerate}
\item
Modellieren Sie diese Aufgabe durch einen Graphen.
Die \emph{Knoten} sollen den m"oglichen Zust"anden
des "`Systems"' Mann--Ziege--Wolf--Kohlkopf--Boot--Fluss
entsprechen, und die \emph{Kanten} den erlaubten "Uberg"angen:
Zum Beispiel w"urde der Wolf die Ziege oder die Ziege den Kohlkopf
fressen, wenn sie ohne Aufsichtig gelassen w"urden;
der Mann, der das Boot rudert, kann nur einen Gegenstand oder
ein Tier zus"atzlich mitnehmen.
%
Eine \emph{L"osung} soll einem \emph{Weg} in diesem Graphen entsprechen.
\item
Schreiben Sie ein Programm, das diesen Graphen erstellt.
Wie viele Knoten und wie viele Kanten hat der Graph?
% \item
Schreiben Sie eine Programm, das mit Breitensuche einen Weg in diesem
Graphen findet, der einer L"osung des Problems entspricht.
\item (0 Punkte)
Ist die L"osung eindeutig?
Wie kann man feststellen, ob es in einem Graphen nur einen einzigen Weg von $s$ nach 
$t$ gibt?
\end{enumerate}

\item (0 Punkte)
Das 14-15-Spiel von Sam Loyd besteht aus 15 nummerierten quadratischen
Bl"ocken, die auf einem $4\times4$-Spielfeld beweglich angeordnet sind.
Eines der 16 Felder ist frei.
Ein Zug besteht darin, dass man einen Stein von einem benachbarten Feld
auf das freie Feld verschiebt.
Das Ziel ist, von einer gegebenen Ausgangsposition ausgehend,
die Steine in die sortierte Reihenfolge zu bringen, sodass
das freie Feld am Ende rechts unten ist.\\
\vbox to 73 mm
{\vss\hbox to 0pt{$
\hskip 6mm
\dimen0=0,9cm
\def\large{\font\f=cmss10 scaled \magstep3 \f}
\vcenter{ \offinterlineskip \large
\halign {\vrule #&&\vbox to \dimen0 {\vss
\hbox to \dimen0{\hfil #\hfil}\vss}\vrule\cr
\noalign{\hrule}\cr
&5&3&2&13\cr
\noalign{\hrule}\cr
&7&1&12&15\cr
\noalign{\hrule}\cr
&14& &8&10\cr
\noalign{\hrule}\cr
&4&9&6&14\cr
\noalign{\hrule}\cr
}}
\ \to\
\vcenter{ \offinterlineskip \large
\halign {\vrule #&&\vbox to \dimen0 {\vss
\hbox to \dimen0{\hfil #\hfil}\vss}\vrule\cr
\noalign{\hrule}\cr
&5&3&2&13\cr
\noalign{\hrule}\cr
&7&1&12&15\cr
\noalign{\hrule}\cr
&14&9&8&10\cr
\noalign{\hrule}\cr
&4&&6&14\cr
\noalign{\hrule}\cr
}}
\ \to \ \cdots\ \to\
\vcenter{ \offinterlineskip \large
\halign {\vrule #&&\vbox to \dimen0 {\vss
\hbox to \dimen0{\hfil #\hfil}\vss}\vrule\cr
\noalign{\hrule}\cr
&1&2&3&4\cr
\noalign{\hrule}\cr
&5&6&7&8\cr
\noalign{\hrule}\cr
&9&10&11&12\cr
\noalign{\hrule}\cr
&13&14&15&\cr
\noalign{\hrule}\cr
}}%\qquad
$\hss}\vss}%
% \begin{enumerate}
Diskutieren Sie, wie man dieses
Problem als Wegeproblem in einem Graphen modellieren k"onnte.
Wie viele Knoten und wie viele Kanten h"atte der Graph?
Welche Schwierigkeiten k"onnen bei diesem Problem
auftreten?

\item (0 Punkte)
Konstruieren Sie ein Beispiel eines Graphen mit 
{negativen} Kantenl"angen,
bei dem der Algorithmus von Dijkstra
{nicht} den k"urzesten Weg findet.

\end{enumerate}
\end{document}

