\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}