\documentclass{uebungsblatt}
\usepackage{tikz}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Praktikum: Grundlagen der Programmierung}
\blatt{3}
\gruppe{OV6}

\begin{document}

\aufgabe

\teilaufgabe

Mengen:

Nationalitäten: \{ Engländer, Norweger, Spanier, Japaner, Ukrainer \} \\
Haustiere: \{ Zebra, Schnecken, Hund, Fuchs, Pferd \}\\
Zigaretten: \{ Parliaments, Altes-Gold, Lucky Strike, Kools, Chesterfield \}\\
Farben: \{ rot, grün, weiß, gelb, blau \}\\
Getränke: \{ Orangensaft, Tee, Kaffee, Wasser, Milch \}\\
Hausnummern: \{ 1, 2, 3, 4, 5 \}

Prädikate:

$imGleichenHaus(x, y)$: Das Element $x$ ist im selben Haus wie $y$.\\
$direktRechts(x, y)$: Das Element $x$ ist im Haus direkt rechts von dem Haus in dem das Element $y$ ist (also ist die Hausnummer von $x$ gleich der von $y + 1$, aber natürlich darf die Hausnummer von $y$ nicht größer als 4 sein).\\
$direktDaneben(x, y)$: Das Element $x$ ist im Haus neben dem Haus in dem das Element $y$ ist (also ist die Hausnummer von $x$ entweder der von $y + 1$ oder $y - 1$, wobei die Hausnummer von $x$ sich zwischen 1 und 5 befinden muss).\\

\teilaufgabe

$ \forall h \in Hausnummern \exists n \in Nation: imGleichenHaus(h, n) $ \\
$ \forall h \in Hausnummern \exists t \in Haustiere: imGleichenHaus(h, t) $ \\
$ \forall h \in Hausnummern \exists z \in Zigaretten: imGleichenHaus(h, z) $ \\
$ \forall h \in Hausnummern \exists f \in Farben: imGleichenHaus(h, f) $ \\
$ \forall h \in Hausnummern \exists g \in Getränke: imGleichenHaus(h, g) $

$ \forall x,y \in Nation \forall h \in Hausnummern: imGleichenHaus(x, h) \wedge imGleichenHaus(y, h) \Leftrightarrow (x = y)$ \\
$ \forall x,y \in Nation \forall t \in Haustiere: imGleichenHaus(x, t) \wedge imGleichenHaus(y, t) \Leftrightarrow (x = y)$ \\
$ \forall x,y \in Nation \forall z \in Zigaretten: imGleichenHaus(x, z) \wedge imGleichenHaus(y, z) \Leftrightarrow (x = y)$ \\
$ \forall x,y \in Nation \forall f \in Farben: imGleichenHaus(x, f) \wedge imGleichenHaus(y, f) \Leftrightarrow (x = y)$ \\
$ \forall x,y \in Nation \forall g \in Getraenke: imGleichenHaus(x, g) \wedge imGleichenHaus(y, g) \Leftrightarrow (x = y)$ \\

\teilaufgabe

\begin{enumerate}
  \item $imGleichenHaus(Englaender, rot)$
  \item $imGleichenHaus(Spanier, Hund)$
  \item $imGleichenHaus(Kaffe, gruen)$
  \item $imGleichenHaus(Ukrainer, Tee)$
  \item $direktRechts(gruen, weiss)$
  \item $imGleichenHaus(AltesGold, Schnecken)$
  \item $imGleichenHaus(Kools, gelb)$
  \item $imGleichenHaus(Milch, 3)$
  \item $imGleichenHaus(Norweger, 1)$
  \item $direktDaneben(Chesterfields, Fuchs)$
  \item $direktDaneben(Kools, Pferd)$
  \item $imGleichenHaus(LuckyStrike, Orangensaft)$
  \item $imGleichenHaus(Japaner, Perliaments)$
  \item $direktDaneben(Norweger, blau)$
\end{enumerate}

\aufgabe

\teilaufgabe

\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: London -> Athen
  \draw [->] (207bp,163bp) .. controls (169bp,163bp) and (111bp,163bp)  .. (61bp,163bp);
  \draw (134bp,154bp) node {200};
  % Edge: Berlin -> Rom
  \draw [->] (190bp,60bp) .. controls (223bp,52bp) and (278bp,38bp)  .. (324bp,26bp);
  \draw (255bp,33bp) node {50};
  % Edge: Athen -> Berlin
  \draw [->] (50bp,149bp) .. controls (72bp,133bp) and (109bp,105bp)  .. (143bp,81bp);
  \draw (88bp,104bp) node {100};
  % Edge: Paris -> London
  \draw [->] (253bp,282bp) .. controls (250bp,259bp) and (246bp,219bp)  .. (243bp,181bp);
  \draw (239bp,231bp) node {30};
  % Edge: Paris -> Madrid
  \draw [->] (275bp,288bp) .. controls (302bp,271bp) and (352bp,240bp)  .. (393bp,215bp);
  \draw (328bp,241bp) node {70};
  % Edge: Rom -> London
  \draw [->] (337bp,35bp) .. controls (319bp,60bp) and (282bp,108bp)  .. (254bp,146bp);
  \draw (307bp,98bp) node {100};
  % Edge: London -> Madrid
  \draw [->] (273bp,170bp) .. controls (302bp,176bp) and (343bp,185bp)  .. (384bp,194bp);
  \draw (326bp,192bp) node {30};
  % Edge: Madrid -> Rom
  \draw [->] (409bp,183bp) .. controls (397bp,151bp) and (373bp,84bp)  .. (355bp,37bp);
  \draw (373bp,113bp) node {60};
  % Edge: Berlin -> Paris
  \draw [->] (169bp,85bp) .. controls (186bp,125bp) and (225bp,225bp)  .. (248bp,282bp);
  \draw (219bp,179bp) node {30};
  % Edge: Berlin -> London
  \draw [->] (175bp,83bp) .. controls (188bp,98bp) and (207bp,121bp)  .. (227bp,146bp);
  \draw (210bp,107bp) node {70};
  % Node: Rom
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (349bp,19bp) ellipse (27bp and 18bp);
  \draw (349bp,19bp) node {Rom};
\end{scope}
  % Node: Paris
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (255bp,300bp) ellipse (27bp and 18bp);
  \draw (255bp,300bp) node {Paris};
\end{scope}
  % Node: Madrid
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (415bp,201bp) ellipse (33bp and 18bp);
  \draw (415bp,201bp) node {Madrid};
\end{scope}
  % Node: Athen
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (31bp,163bp) ellipse (30bp and 18bp);
  \draw (31bp,163bp) node {Athen};
\end{scope}
  % Node: Berlin
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (162bp,67bp) ellipse (29bp and 18bp);
  \draw (162bp,67bp) node {Berlin};
\end{scope}
  % Node: London
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (241bp,163bp) ellipse (34bp and 18bp);
  \draw (241bp,163bp) node {London};
\end{scope}
%
\end{tikzpicture}

\teilaufgabe

Man geht von der Ursprungsposition aus, in diesem Beispiel ist das Paris.  Dort
prüft man welche Kanten im Graphen vom Ursprungsknoten ausgehen, in diesem Fall
wäre das Madrid und London. Nun kann man den Vorgang des Kantenprüfens auf den
gefundenen Knoten nochmals ausführen (quasi rekursiv weiterverfolgen), was zu
einer Kaskadenförmigen Rekursion führen kann, bis man irgendwann auf die
Ziel-Stadt/Ziel-Knoten trifft. Da dieser Graph Zyklen hat, wäre es möglich in
``Schleifen'' hin- und herzufliegen (die Rekursion würde Schleifen bilden und
würde nie terminieren), muss man verhindern, dass Kanten geprüft werden, die in
einer höheren Stelle im Zweig des Rekursionsbaums (der durch die
Kaskadenförmige Rekursion beschrieben wird) schon einmal geprüft worden sind.
Somit terminiert die Rekursion wenn die Zweige am Ziel angekommen sind oder
wenn es keine weiteren Kanten gibt die man verfolgen könnte. Die Zweige die zum
Ziel führen, sind die möglichen Flugrouten.

Mögliche Flugrouten wären:
\begin{itemize}
  \item Paris $\rightarrow$ Madrid $\rightarrow$ Rom
  \item Paris $\rightarrow$ London $\rightarrow$ Madrid $\rightarrow$ Rom
  \item Paris $\rightarrow$ London $\rightarrow$ Athen $\rightarrow$ Berlin $\rightarrow$ Rom (eher ungewöhnlich, da recht umständlich)
\end{itemize}

\teilaufgabe

Das Verfahren von oben lässt sich durchaus wiederholen, indem man alle Routen
durchläuft und dann die Preise auf den Kanten zusammenzählt und dort dann die
billigste heraussucht. Man kann es sich auch vereinfachen, indem man den
aktuell niedrigsten Preis abspeichert, die Zweige absucht und immer die Beträge
auf den Kanten zum aktuellen preis aufaddiert. Wenn der aktuelle Preis größer
ist als der niedrigste, bereits gefundene Preis ist, kann man abbrechen,
ansonsten verfolgt man den Graphen rekursiv weiter bis man dann den Endpunkt
erreicht (in diesem Fall setzt man den kleinsten möglichen Preis auf den
aktuellen Betrag).

\teilaufgabe

London $\rightarrow$ Athen $\rightarrow$ Berlin $\rightarrow$ Paris
$\rightarrow$ Madrid $\rightarrow$ Rom $\rightarrow$ London

Vorgehen: am Startpunkt London begonnen, von dort die möglichen Alternativen
Madrid oder Athen geprüft. Den Weg über Madrid verworfen da es von dort nur
nach Rom und dann nach London gehen würde, also den Weg nach Athen
eingeschlagen. Dort geht es zwangsläufig nach Berlin weiter. In Berlin hat man
die Möglichkeiten London und Paris, wobei aber London direkt verworfen werden
kann, da noch nicht alle Städte besucht worden sind, also weiter nach Paris.
Dort kann man London auch direkt wieder ausschließen, so dass man weiter nach
Madrid fliegt. In Madrid hat man nur noch eine Möglichkeit, Rom und von Rom aus
geht es auch nur noch nach London weiter.

Prinzipiell ist der Algorithmus sehr ähnlich zu den vorherigen (mit der
Ausnahme dass London der Startkpunkt und das Ziel ist und somit zweimal besucht
werden darf), jedoch müssen dann die gefundenen Routen darauf geprüft werden,
ob jede Stadt einmal angeflogen wurde.

\end{document}
