--- header-includes: | \usepackage{booktabs} \newcommand{\graph}{ \begin{tikzpicture} \node[fill=red, circle, minimum size=0.2cm] (ts) {}; \node[above=0.1cm of ts] {Traunstein}; \node[fill=red, circle, minimum size=0.2cm] (ib) at (-2, -1) {}; \node[xshift=-0.3cm, above=0.1cm of ib] {Innsbruck}; \node[fill=red, circle, minimum size=0.2cm] (ms) at (1, -2) {}; \node[right=0.1cm of ms] {Millstadt}; \draw (ts) -- node[fill=yellow!30] {138} (ib); \draw (ts) -- node[fill=yellow!30] {211} (ms); \node[fill=red, circle, minimum size=0.2cm] (ic) at (-1, -2.5) {}; \node[left=0cm of ic, yshift=-0.2cm] {Innichen}; \draw (ib) -- node[fill=yellow!30] {139} (ic); \draw (ms) -- node[fill=yellow!30] {120} (ic); \node[fill=red, circle, minimum size=0.2cm] (vd) at (0, -4) {}; \node[right=0.1cm of vd] {Venedig}; \draw (ic) -- node[fill=yellow!30] {197} (vd); \draw (ms) -- node[fill=yellow!30] {278} (vd); \end{tikzpicture} } --- ## Wdh - Radtour nach Venedig ::: columns :::: {.column width=50%} Für die kommenden Sommerferien plant ihr eine Radtour durch die Alpen nach \boldred{Venedig}. \vspace{1cm} \pause Als Startpunkt habt ihr euch \boldred{Traunstein} ausgesucht. :::: :::: {.column width=50%} \graph :::: ::: ## Radtour nach Venedig ::: columns :::: {.column width=50%} \vspace{2cm} Wie finden wir den kürzesten Weg von Traunstein nach Venedig? :::: :::: {.column width=50%} \graph :::: ::: ## Wdh - Dijkstra Algortihmus Eine Möglichkeit \boldred{effizient} den kürzesten Weg zwischen zwei Punkten zu finden ist der Algorithmus des niederländischen Informatikers Dijkstra. Dazu benötigen wir zu erst eine Tabelle aller Orte mit den vier Spalten: **Ort, kommt von, Distanz zum Start, bearbeitet** ::: columns :::: {.column width=60%} \begin{tabular}{l | l | l | l} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & \\ \hline Innsbruck & & $\infty$ & \\ \hline Innichen & & $\infty$ & \\ \hline Millstatt & & $\infty$ & \\ \hline Venedig & & $\infty$ & \\ \end{tabular} :::: :::: {.column width=40%} \hspace{0.3cm} \scalebox{0.8}{\graph} :::: ::: ## Wdh - Dijkstra Algortihmus Start Zuerst tragen wir alle benachbarten Orte vom Start und ihre Distanzen ein und vermerken den Start als \textbf{bearbeitet}. ::: columns :::: {.column width=60%} \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & \cellcolor{green!20} X \\ \hline \rowcolor{blue!10} Innsbruck & Traunstein & 138 & \\ \hline Innichen & & $\infty$ & \\ \hline \rowcolor{blue!10} Millstatt & Traunstein & 211 & \\ \hline Venedig & & $\infty$ & \\ \end{tabularx} :::: :::: {.column width=40%} \hspace{0.3cm} \scalebox{0.8}{\graph} :::: ::: ## Wdh - Dijkstra Algortihmus Fortsetzung Wir wählen den \boldred{nicht bearbeiteten} Ort mit der \boldred{kürzesten} Distanz zum Start. \only<1>{\phantom{Setzen in auf \textbf{bearbeitet}.}} \only<2->{Setzen in auf \textbf{bearbeitet}.} \only<-2>{\phantom{Von dem gewählten Ort bestimmen wir alle Distanzen zum Start und aktualisieren Einträge für die wir einen kürzeren Weg gefunden haben.}} \only<3->{Von dem gewählten Ort bestimmen wir alle Distanzen zum Start und aktualisieren Einträge für die wir einen kürzeren Weg gefunden haben.} ::: columns :::: {.column width=60%} \only<-5>{ \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & X \\ \hline \rowcolor{red!20} Innsbruck & Traunstein & 138 & \only<2->{\cellcolor{green!20}} \only<2->{X} \only<-2>{\\ \hline} \only<3->{\\ \hline \rowcolor{blue!10}} Innichen & \only<4->{Innsbruck} & \only<-3>{$\infty$}\only<4->{277} & \\ \hline Millstatt & Traunstein & 211 & \\ \hline Venedig & & $\infty$ & \\ \end{tabularx} } \only<6-8>{ \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & X \\ \hline Innsbruck & Traunstein & 138 & X \\ \hline Innichen & Innsbruck & \only<-3>{$\infty$}\only<4->{277} & \\ \hline \rowcolor{red!20} Millstatt & Traunstein & 211 & \only<7->{\cellcolor{green!20}} \only<7->{X} \only<-7>{\\ \hline} \only<8->{\\ \hline \rowcolor{blue!10}} Venedig & \only<8->{Millstadt} & \only<-7>{$\infty$}\only<8>{498} & \\ \end{tabularx} } \only<9-10>{ \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & X \\ \hline Innsbruck & Traunstein & 138 & X \\ \hline \rowcolor{red!20} Innichen & Innsbruck & 277 & \only<7->{\cellcolor{green!20} X} \\ \hline Millstatt & Traunstein & 211 & X \only<-9>{\\ \hline} \only<10->{\\ \hline \rowcolor{blue!10}} Venedig & \only<9->{Innichen} & \only<-9>{498}\only<10>{\textbf{474}} & \\ \end{tabularx} } \only<11->{ \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & X \\ \hline Innsbruck & Traunstein & 138 & X \\ \hline Innichen & Innsbruck & 277 & X \\ \hline Millstatt & Traunstein & 211 & X \\ \hline \rowcolor{red!20} Venedig & Innichen & 474 & \only<11->{\cellcolor{green!20} X}\\ \end{tabularx} } :::: :::: {.column width=40%} \hspace{0.3cm} \scalebox{0.8}{\graph} :::: ::: ## Wdh - Dijkstra Algortihmus Ende Der kürzeste Weg zu einem Ort wurde gefunden sobald dieser als bearbeitet markiert ist. \begin{tabularx}{\textwidth}{X | X | X | X} Ort & kommt von & Distanz zum Start & bearbeitet \\ \toprule Traunstein & & 0 & X \\ \hline Innsbruck & Traunstein & 138 & X \\ \hline Innichen & Innsbruck & 277 & X \\ \hline Millstatt & Traunstein & 211 & X \\ \hline \rowcolor{red!20} Venedig & Innichen & 474 & X\\ \end{tabularx} Der Weg nach Venedig lässt sich aus der Tabelle ablesen: **Venedig < Innichen < Innsbruck < Traunstein** ## \faIcon{pencil-alt} Arbeitsauftrag - Dijkstra ::: columns :::: {.column width=60%} \vspace{0.4\textheight} Ermittle den kürzesten Weg von A nach D mit dem Dijkstra-Algortihmus. :::: :::: {.column width=40%} ```{.graphviz} graph { bgcolor=transparent node [shape=circle] ranksep=0 nodesep=0.5 A [color=orange] { rank=same C B } { rank=same E F } { rank=same G D } A -- C [label="1"] A -- B [label="3"] B -- C [label="1"] B -- E [label="5"] C -- D [label="1"] D -- F [label="2"] F -- E [label="4"] E -- G [label="1"] G [color=blue] } ``` :::: ::: ## \faIcon{desktop}\faIcon{hands-helping} Arbeitsauftrag - Kniffel Öffne das *fast vollständige* Kniffel-Projekt unter **Ablage/11b/vorlagen/kniffel.xml**. * Erkunde das Kniffelprogramm * Erweitert es mit für euch noch fehlender Funktionalität * Möglichkeiten: * *Bequemes* hinzufügen weiterer Spieler * Berechnung der Endpunkte * Berechnung des Bonus * ... * Tauscht euere Verbesserungen/Ergänzungen aus