diff options
Diffstat (limited to 'vorlesungen/slides/8/floyd-warshall')
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/burgerking.png | bin | 0 -> 121512 bytes | |||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/fw.tex | 680 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/iteration.tex | 14 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/macdonalds.png | bin | 0 -> 129601 bytes | |||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/problem.tex | 146 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/rekursion.tex | 108 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/starbucks.png | bin | 0 -> 160194 bytes | |||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/wege.tex | 26 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/wegiteration.tex | 13 | ||||
| -rw-r--r-- | vorlesungen/slides/8/floyd-warshall/wegweiser.jpg | bin | 0 -> 431961 bytes |
10 files changed, 987 insertions, 0 deletions
diff --git a/vorlesungen/slides/8/floyd-warshall/burgerking.png b/vorlesungen/slides/8/floyd-warshall/burgerking.png Binary files differnew file mode 100644 index 0000000..cf4211d --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/burgerking.png diff --git a/vorlesungen/slides/8/floyd-warshall/fw.tex b/vorlesungen/slides/8/floyd-warshall/fw.tex new file mode 100644 index 0000000..99929fb --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/fw.tex @@ -0,0 +1,680 @@ +% +% fw.tex -- Durchführung des Floyd-Warshall Algorithmus +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup + +\definecolor{wegelb}{rgb}{1,0.6,0} +\definecolor{weghell}{rgb}{1,0.9,0.6} +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\begin{columns}[t] +\begin{column}{0.44\hsize} +\begin{center} +\begin{tikzpicture}[>=latex] + + +\def\r{2.2} +\coordinate (A) at ({\r*cos(-54+0*72)},{\r*sin(-54+0*72)}); +\coordinate (C) at ({\r*cos(-54+1*72)},{\r*sin(-54+1*72)}); +\coordinate (D) at ({\r*cos(-54+2*72)},{\r*sin(-54+2*72)}); +\coordinate (B) at ({\r*cos(-54+3*72)},{\r*sin(-54+3*72)}); +\coordinate (E) at ({\r*cos(-54+4*72)},{\r*sin(-54+4*72)}); + +\def\knoten#1#2#3{ + \fill[color=#3] #1 circle[radius=0.3]; + \draw[line width=1pt] #1 circle[radius=0.3]; + \node at #1 {$#2$}; +} + +\def\kante#1#2#3{ + \draw[->,line width=1pt,shorten >= 0.3cm,shorten <= 0.3cm] #1 -- #2; + \fill[color=white,opacity=0.7] ($0.5*#1+0.5*#2$) circle[radius=0.22]; + \node at ($0.5*#1+0.5*#2$) {$#3$}; +} + +% Wege über 1 +% 3--1--5 +\only<4>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E); +} + +% Wege über 2 +% 5--2--3 +\only<6>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C); +} +% 5--2--4 +\only<7>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(D); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(D); +} + +% Wege über 3 +% 2--3--1 +\only<9>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A); +} +% 2--3--5 +\only<10>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E); +} +% 4--3--1 +\only<11>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A); +} +% 4--3--5 +\only<12>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E); +} +% 5--3--1 +\only<13>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C)--(A); +} +% 5--3--5 +\only<14>{ + \draw[->,line width=7pt,color=red!50] + (E)--(B)--(C)--(A)--(E); +} + +% Wege über 4 +% 2--4--1 +\only<16>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A); +} +% 2--4--3 +\only<17>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C); +} +% 2--4--5 +\only<18>{ + \draw[->,line width=7pt,color=red!50] + (B)--(D)--(C)--(A)--(E); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A)--(E); +} +% 5--4--1 +\only<19>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C)--(A); +} +% 5--4--3 +\only<20>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C); +} +% 5--4--5 +\only<21>{ + \draw[->,line width=7pt,color=red!50] + (E)--(D)--(C)--(A)--(E); + \draw[->,line width=7pt,color=blue!50,dashed] + (E)--(B)--(C)--(A)--(E); +} +% 1--5--1 +\only<23>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B)--(C)--(A); +} +% 1--5--2 +\only<24>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B); +} +% 1--5--3 +\only<25>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(B)--(C); +} +% 1--5--4 +\only<26>{ + \draw[->,line width=7pt,color=red!50] + (A)--(E)--(D); +} +% 2--5--1 +\only<27>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C)--(A); +} +% 2--5--2 +\only<28>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(B); +} +% 2--5--3 +\only<29>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(C); +} +% 2--5--4 +\only<30>{ + \draw[->,line width=7pt,color=red!50] + (B)--(C)--(A)--(E)--(D); + \draw[->,line width=7pt,color=blue!50,dashed] + (B)--(D); +} +% 3--5--1 +\only<31>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (C)--(A); +} +% 3--5--2 +\only<32>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(B); +} +% 3--5--3 +\only<33>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(B)--(C); +} +% 3--5--4 +\only<34>{ + \draw[->,line width=7pt,color=red!50] + (C)--(A)--(E)--(D); +} +% 4--5--1 +\only<35>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D)--(C)--(A); + \draw[->,line width=7pt,color=blue!50,dashed] + (D)--(C)--(A); +} +% 4--5--2 +\only<36>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(B); +} +% 4--5--3 +\only<37>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D)--(C); + \draw[->,line width=7pt,color=blue!50,dashed] + (D)--(C); +} +% 4--5--4 +\only<38>{ + \draw[->,line width=7pt,color=red!50] + (D)--(C)--(A)--(E)--(D); +} + + +\uncover<40>{ + \draw[->,color=red!50,line width=7pt] + (B)--(C)--(A)--(E)--(D); +} + +\kante{(A)}{(E)}{1} +\kante{(B)}{(C)}{2} +\kante{(B)}{(D)}{13} +\kante{(C)}{(A)}{3} +\kante{(D)}{(C)}{6} +\kante{(E)}{(B)}{5} +\kante{(E)}{(D)}{6} + +\only<1>{ + \knoten{(A)}{}{white} + \knoten{(B)}{}{white} + \knoten{(C)}{}{white} + \knoten{(D)}{}{white} + \knoten{(E)}{}{white} +} + +\only<2->{ + \knoten{(A)}{1}{white} + \knoten{(B)}{2}{white} + \knoten{(C)}{3}{white} + \knoten{(D)}{4}{white} + \knoten{(E)}{5}{white} +} + +\only<4>{ + \knoten{(A)}{1}{darkgreen!50} +} +\only<6-7>{ + \knoten{(B)}{2}{darkgreen!50} +} +\only<9-14>{ + \knoten{(C)}{3}{darkgreen!50} +} +\only<16-21>{ + \knoten{(D)}{4}{darkgreen!50} +} +\only<23-38>{ + \knoten{(E)}{5}{darkgreen!50} +} + +\end{tikzpicture} +\end{center} +\begin{block}{Aufgabe} +Finde den kürzesten Weg von 2 nach 4 +\end{block} +\end{column} +\begin{column}{0.5\hsize} +\begin{center} +\begin{tikzpicture}[>=latex,scale=0.8] + +\def\punkt#1#2{ + ({#2-0.5},{0.5-(#1)}) +} +\def\punktoff#1#2{ + ({#2-0.7},{0.7-(#1)}) +} +\def\feld#1#2#3{ + \ifthenelse{\boolean{wegweiser}}{ + \fill[color=white] + ({#2-1},{1-#1}) rectangle ({#2-0.45},{0.45-#1}); + \node at \punktoff{#1}{#2} {$#3$}; + }{ + \fill[color=white] + ({#2-1},{1-#1}) rectangle ({#2},{-#1}); + \node at \punkt{#1}{#2} {$#3$}; + } +} +\def\verbindung#1#2#3{ + \draw[->,line width=5pt,color=red!20,shorten >= 0.2cm,shorten <= 0.2cm] + \punkt{#1}{#2}--\punkt{#2}{#3}; + \node at (5,-5.5) [left] {$#1\rightsquigarrow #2\rightsquigarrow #3$\strut}; +} +\def\Infty{{}} +\def\wegweiser#1#2#3{ + \ifthenelse{\boolean{wegweiser}}{ + \ifnum #2 = #3 + \fill[color=weghell] + ({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1}); + \else + \fill[color=wegelb] + ({#2-0.45},{0.45-#1}) rectangle ({#2-0.05},{0.05-#1}); + \fi + \node at ({#2-0.25},{0.25-#1}) {\tiny #3}; + }{} +} + +% direkte Wege +\uncover<3->{ + \feld{1}{1}{\Infty} + \feld{1}{2}{\Infty} + \feld{1}{3}{\Infty} + \feld{1}{4}{\Infty} + \feld{1}{5}{1} + \wegweiser{1}{5}{5} + + \feld{2}{1}{\Infty} + \feld{2}{2}{\Infty} + \feld{2}{3}{2} + \wegweiser{2}{3}{3} + \feld{2}{4}{13} + \wegweiser{2}{4}{4} + \feld{2}{5}{\Infty} + + \feld{3}{1}{3} + \wegweiser{3}{1}{1} + \feld{3}{2}{\Infty} + \feld{3}{3}{\Infty} + \feld{3}{4}{\Infty} + \feld{3}{5}{\Infty} + + \feld{4}{1}{\Infty} + \feld{4}{2}{\Infty} + \feld{4}{3}{6} + \wegweiser{4}{3}{3} + \feld{4}{4}{\Infty} + \feld{4}{5}{\Infty} + + \feld{5}{1}{\Infty} + \feld{5}{2}{5} + \wegweiser{5}{2}{2} + \feld{5}{3}{\Infty} + \feld{5}{4}{6} + \wegweiser{5}{4}{4} + \feld{5}{5}{\Infty} +} + +\uncover<3-3>{ + \node at (-0.8,-5.5) [right] {direkte Verbindungen}; +} + +\uncover<4-4>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $1$:\strut}; +} + +% Wege über 1 +% 3-1-5 +\uncover<4>{ + \verbindung{3}{1}{5} + \feld{3}{5}{\color{red}4} + \wegweiser{3}{5}{1} +} +\uncover<5->{ + \feld{3}{5}{4} + \wegweiser{3}{5}{1} +} + +\uncover<6-7>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $2$:\strut}; +} + +% Wege über 2 +% 5-2-3 +\uncover<6>{ + \verbindung{5}{2}{3} + \feld{5}{3}{\color{red}7} + \wegweiser{5}{3}{2} +} +\uncover<7->{ + \feld{5}{3}{7} + \wegweiser{5}{3}{2} +} +% 5-2-4 +\uncover<7>{ + \verbindung{5}{2}{4} + \feld{5}{4}{\color{blue}6} +} + +\uncover<9-14>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $3$:\strut}; +} + +% Wege über 3 +% 2-3-1 +\uncover<9>{ + \verbindung{2}{3}{1} + \feld{2}{1}{\color{red}5} + \wegweiser{2}{1}{3} +} +\uncover<10->{ + \feld{2}{1}{5} + \wegweiser{2}{1}{3} +} +% 2-3-5 +\uncover<10>{ + \verbindung{2}{3}{5} + \feld{2}{5}{\color{red}6} + \wegweiser{2}{5}{3} +} +\uncover<11->{ + \feld{2}{5}{6} + \wegweiser{2}{5}{3} +} +% 4-3-1 +\uncover<11>{ + \verbindung{4}{3}{1} + \feld{4}{1}{\color{red}9} + \wegweiser{4}{1}{3} +} +\uncover<12->{ + \feld{4}{1}{9} + \wegweiser{4}{1}{3} +} +% 4-3-5 +\uncover<12>{ + \verbindung{4}{3}{5} + \feld{4}{5}{\color{red}10} + \wegweiser{4}{5}{3} +} +\uncover<13->{ + \feld{4}{5}{10} + \wegweiser{4}{5}{3} +} +% 5-3-1 +\uncover<13>{ + \verbindung{5}{3}{1} + \feld{5}{1}{\color{red}10} + \wegweiser{5}{1}{2} +} +\uncover<14->{ + \feld{5}{1}{10} + \wegweiser{5}{1}{2} +} +% 5-3-5 +\uncover<14>{ + \verbindung{5}{3}{5} + \feld{5}{5}{\color{red}11} + \wegweiser{5}{5}{2} +} +\uncover<15->{ + \feld{5}{5}{11} + \wegweiser{5}{5}{2} +} + +\uncover<16-21>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $4$:\strut}; +} + +% Wege über 4 +% 2-4-1 +\uncover<16>{ + \verbindung{2}{4}{1} + \feld{2}{1}{\color{blue}5} +} +% 2-4-3 +\uncover<17>{ + \verbindung{2}{4}{3} + \feld{2}{3}{\color{blue}2} +} +% 2-4-5 +\uncover<18>{ + \verbindung{2}{4}{5} + \feld{2}{5}{\color{blue}6} +} +% 5-4-1 +\uncover<19>{ + \verbindung{5}{4}{1} + \feld{5}{1}{\color{blue}10} +} +% 5-4-3 +\uncover<20>{ + \verbindung{5}{4}{3} + \feld{5}{3}{\color{blue}7} +} +% 5-4-5 +\uncover<21>{ + \verbindung{5}{4}{5} + \feld{5}{5}{\color{blue}11} +} + +% Wege über 5 +\uncover<23-38>{ + \node[color=darkgreen] at (-0.8,-5.5) [right] {Wege über $5$:\strut}; +} + +% Wege über 5 +% 1-5-1 +\uncover<23>{ + \verbindung{1}{5}{1} + \feld{1}{1}{\color{red}11} + \wegweiser{1}{1}{5} +} +\uncover<24->{ + \feld{1}{1}{11} + \wegweiser{1}{1}{5} +} +% 1-5-2 +\uncover<24>{ + \verbindung{1}{5}{2} + \feld{1}{2}{\color{red}6} + \wegweiser{1}{2}{5} +} +\uncover<25->{ + \feld{1}{2}{6} + \wegweiser{1}{2}{5} +} +% 1-5-3 +\uncover<25>{ + \verbindung{1}{5}{3} + \feld{1}{3}{\color{red}8} + \wegweiser{1}{3}{5} +} +\uncover<26->{ + \feld{1}{3}{8} + \wegweiser{1}{3}{5} +} +% 1-5-4 +\uncover<26>{ + \verbindung{1}{5}{4} + \feld{1}{4}{\color{red}7} + \wegweiser{1}{4}{5} +} +\uncover<27->{ + \feld{1}{4}{7} + \wegweiser{1}{4}{5} +} +% 2-5-1 +\uncover<27>{ + \verbindung{2}{5}{1} + \feld{2}{1}{\color{blue}5} +} +% 2-5-2 +\uncover<28>{ + \verbindung{2}{5}{2} + \feld{2}{2}{\color{red}11} + \wegweiser{2}{2}{3} +} +\uncover<29->{ + \feld{2}{2}{11} + \wegweiser{2}{2}{3} +} +% 2-5-3 +\uncover<29>{ + \verbindung{2}{5}{3} + \feld{2}{3}{\color{blue}2} +} +% 2-5-4 +\uncover<30>{ + \verbindung{2}{5}{4} + \feld{2}{4}{\color{red}12} + \wegweiser{2}{4}{3} +} +\uncover<31->{ + \feld{2}{4}{12} + \wegweiser{2}{4}{3} +} +% 3-5-1 +\uncover<31>{ + \verbindung{3}{5}{1} + \feld{3}{1}{\color{blue}3} +} +% 3-5-2 +\uncover<32>{ + \verbindung{3}{5}{2} + \feld{3}{2}{\color{red}9} + \wegweiser{3}{2}{1} +} +\uncover<33->{ + \feld{3}{2}{9} + \wegweiser{3}{2}{1} +} +% 3-5-3 +\uncover<33>{ + \verbindung{3}{5}{3} + \feld{3}{3}{\color{red}11} + \wegweiser{3}{3}{1} +} +\uncover<34->{ + \feld{3}{3}{11} + \wegweiser{3}{3}{1} +} +% 3-5-4 +\uncover<34>{ + \verbindung{3}{5}{4} + \feld{3}{4}{\color{red}10} + \wegweiser{3}{4}{1} +} +\uncover<35->{ + \feld{3}{4}{10} + \wegweiser{3}{4}{1} +} +% 4-5-1 +\uncover<35>{ + \verbindung{4}{5}{1} + \feld{4}{1}{\color{blue}9} +} +% 4-5-2 +\uncover<36>{ + \verbindung{4}{5}{2} + \feld{4}{2}{\color{red}15} + \wegweiser{4}{2}{3} +} +\uncover<37->{ + \feld{4}{2}{15} + \wegweiser{4}{2}{3} +} +% 4-5-3 +\uncover<37>{ + \verbindung{4}{5}{3} + \feld{4}{3}{\color{blue}6} +} +% 4-5-4 +\uncover<38>{ + \verbindung{4}{5}{4} + \feld{4}{4}{\color{red}16} + \wegweiser{4}{4}{3} +} +\uncover<39->{ + \feld{4}{4}{16} + \wegweiser{4}{4}{3} +} + + +\uncover<3->{ + + \foreach \x in {0,...,5}{ + \draw[line width=0.7pt] (\x,0.8)--(\x,-5); + } + \foreach \y in {0,...,-5}{ + \draw[line width=0.7pt] (-0.8,\y)--(5,\y); + } + \draw[line width=1.4pt] (0,0)--(5,0)--(5,-5)--(0,-5)--cycle; + + \node at (0.5,0.5) {$1$}; + \node at (1.5,0.5) {$2$}; + \node at (2.5,0.5) {$3$}; + \node at (3.5,0.5) {$4$}; + \node at (4.5,0.5) {$5$}; + + \node at (-0.5,-0.5) {$1$}; + \node at (-0.5,-1.5) {$2$}; + \node at (-0.5,-2.5) {$3$}; + \node at (-0.5,-3.5) {$4$}; + \node at (-0.5,-4.5) {$5$}; +} + +\end{tikzpicture} +\end{center} + +\uncover<40>{ + \vspace{-22pt} + \begin{block}{Lösung} + Der kürzeste Weg von 2 nach 4 ist 2---3---1---5---4 + \end{block} +} + +\end{column} +\end{columns} + +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/iteration.tex b/vorlesungen/slides/8/floyd-warshall/iteration.tex new file mode 100644 index 0000000..d7e782d --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/iteration.tex @@ -0,0 +1,14 @@ +% +% iteration.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup +\newboolean{wegweiser} +\begin{frame}[fragile] +\frametitle{Floyd-Warshall: Iteration} +\setboolean{wegweiser}{false} +\input{../slides/8/floyd-warshall/fw.tex} + +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/macdonalds.png b/vorlesungen/slides/8/floyd-warshall/macdonalds.png Binary files differnew file mode 100644 index 0000000..c442dfb --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/macdonalds.png diff --git a/vorlesungen/slides/8/floyd-warshall/problem.tex b/vorlesungen/slides/8/floyd-warshall/problem.tex new file mode 100644 index 0000000..93f8229 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/problem.tex @@ -0,0 +1,146 @@ +% +% graph.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame}[fragile] +\frametitle{Problem: Kürzeste Wege} +\begin{center} +\begin{tikzpicture}[>=latex] + +\def\blob#1#2#3{ + \fill[color=#3] #1 circle[radius=0.2]; + \draw[line width=0.7pt] #1 circle[radius=0.2]; + \node at #1 {{\tiny #2}}; +} + +\def\kante#1#2{ + \draw[line width=0.7pt,shorten >= 0.2,shorten >= 0.2] #1 -- #2 ; +} + +\def\a{72} +\def\r{1.0} +\def\R{2.0} +\def\RR{3.5} + +\coordinate (A1) at ({\r*cos(0*\a)},{\r*sin(0*\a)}); +\coordinate (B1) at ({\r*cos(1*\a)},{\r*sin(1*\a)}); +\coordinate (C1) at ({\r*cos(2*\a)},{\r*sin(2*\a)}); +\coordinate (D1) at ({\r*cos(3*\a)},{\r*sin(3*\a)}); +\coordinate (E1) at ({\r*cos(4*\a)},{\r*sin(4*\a)}); + +\coordinate (F1) at ({\R*cos(0*\a)},{\R*sin(0*\a)}); +\coordinate (G1) at ({\R*cos(1*\a)},{\R*sin(1*\a)}); +\coordinate (H1) at ({\R*cos(2*\a)},{\R*sin(2*\a)}); +\coordinate (I1) at ({\R*cos(3*\a)},{\R*sin(3*\a)}); +\coordinate (J1) at ({\R*cos(4*\a)},{\R*sin(4*\a)}); + +\coordinate (K1) at ({\RR*cos(0.5*\a)},{\RR*sin(0.5*\a)}); +\coordinate (L1) at ({\RR*cos(1.5*\a)},{\RR*sin(1.5*\a)}); +\coordinate (M1) at ({\RR*cos(2.5*\a)},{\RR*sin(2.5*\a)}); +\coordinate (N1) at ({\RR*cos(3.5*\a)},{\RR*sin(3.5*\a)}); +\coordinate (O1) at ({\RR*cos(4.5*\a)},{\RR*sin(4.5*\a)}); + +\kante{(A1)}{(C1)} +\kante{(C1)}{(E1)} +\kante{(E1)}{(B1)} +\kante{(B1)}{(D1)} +\kante{(D1)}{(A1)} + +\kante{(F1)}{(G1)} +\kante{(G1)}{(H1)} +\kante{(H1)}{(I1)} +\kante{(I1)}{(J1)} +\kante{(J1)}{(F1)} + +\kante{(A1)}{(F1)} +\kante{(B1)}{(G1)} +\kante{(C1)}{(H1)} +\kante{(D1)}{(I1)} +\kante{(E1)}{(J1)} + +\kante{(K1)}{(L1)} +\kante{(L1)}{(M1)} +\kante{(M1)}{(N1)} +\kante{(N1)}{(O1)} +\kante{(O1)}{(K1)} + +\kante{(F1)}{(K1)} +\kante{(G1)}{(L1)} +\kante{(H1)}{(M1)} +\kante{(I1)}{(N1)} +\kante{(J1)}{(O1)} + +\kante{(F1)}{(O1)} +\kante{(G1)}{(K1)} +\kante{(H1)}{(L1)} +\kante{(I1)}{(M1)} +\kante{(J1)}{(N1)} + +\uncover<2>{ + \draw[line width=2pt,color=red] (M1)--(H1)--(G1)--(B1); +} + +\uncover<3>{ + \draw[line width=2pt,color=red] (M1)--(L1)--(G1)--(B1); +} + +\uncover<4>{ + \draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(B1); +} + +\uncover<5>{ + \draw[line width=2pt,color=red] (M1)--(I1)--(D1)--(A1)--(F1); +} + +\uncover<6->{ + \draw[line width=2pt,color=red] (M1)--(I1)--(J1)--(F1); +} + +\uncover<2-4>{ + \blob{(B1)}{1}{red!20} + \blob{(M1)}{12}{red!20} +} +\uncover<5-8>{ + \blob{(M1)}{1}{red!20} + \blob{(F1)}{12}{red!20} +} + +\blob{(A1)}{0}{white} +\uncover<1>{ + \blob{(B1)}{1}{white} +} +\uncover<5-8>{ + \blob{(B1)}{12}{white} +} +\blob{(C1)}{2}{white} +\blob{(D1)}{3}{white} +\blob{(E1)}{4}{white} +\uncover<1-4>{ + \blob{(F1)}{5}{white} +} +\blob{(G1)}{6}{white} +\blob{(H1)}{7}{white} +\blob{(I1)}{8}{white} +\blob{(J1)}{9}{white} +\blob{(K1)}{10}{white} +\blob{(L1)}{11}{white} +\uncover<1>{ + \blob{(M1)}{12}{white} +} +\blob{(N1)}{13}{white} +\blob{(O1)}{14}{white} + +\node at (6,0) {\begin{minipage}{5cm} +\begin{itemize} +\item<3-> Nicht eindeutig +\item<5-> geradeste Wege sind nicht unbedingt die kürzesten +\item<7-> Gewichtung der Kanten +($\text{Schnellstrassen}\ne\text{Feldwege}$) +\item<8-> Orientierung der Kanten? +\end{itemize} +\end{minipage}}; + +\end{tikzpicture} +\end{center} +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/rekursion.tex b/vorlesungen/slides/8/floyd-warshall/rekursion.tex new file mode 100644 index 0000000..c664e41 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/rekursion.tex @@ -0,0 +1,108 @@ +% +% rekursion.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame}[fragile] +\frametitle{Rekursion} +\vspace{-20pt} +\begin{center} +\begin{tikzpicture}[>=latex] + +\def\blob#1#2#3{ + \fill[color=#3] #1 circle[radius=0.3]; + \draw[line width=0.7pt] #1 circle[radius=0.3]; + \node at #1 {{#2}}; +} + +\def\kante#1#2{ + \draw[line width=0.7pt,shorten >= 0.3,shorten >= 0.3] #1 -- #2 ; +} + +\coordinate (A) at (0,0); +\coordinate (B1) at (2,2); +\coordinate (B2) at (2,1); +\coordinate (B3) at (2,0); +\coordinate (B4) at (2,-1); +\coordinate (B5) at (2,-2); + +\draw[line width=1.9pt,color=gray] (A)--(B1); +\draw[line width=1.9pt,color=gray] (A)--(B2); +\draw[line width=1.9pt,color=gray] (A)--(B3); +\draw[line width=1.9pt,color=gray] (A)--(B4); +\draw[line width=1.9pt,color=gray] (A)--(B5); + +\coordinate (Z) at (10,0); + +\begin{scope} +\clip (2,-2.3) rectangle (10,2.3); +\foreach \y in{-10,...,10}{ + \draw[line width=1.9pt,color=gray] + (2,\y)--(10,{\y-8}); + \draw[line width=1.9pt,color=gray] + (2,\y)--(10,{\y+8}); +} +\end{scope} + +\uncover<2>{ +\draw[line width=4pt,color=red] (A)--(B1)--(5,-1)--(8,2)--(Z); +} + +\uncover<3>{ +\draw[line width=4pt,color=red] (A)--(B2)--(3,0)--(4,1)--(5,0)--(6,1)--(8.5,-1.5)--(Z); +} + +\uncover<4>{ +\draw[line width=4pt,color=red] (A)--(B3)--(2.5,0.5)--(3.5,-0.5)--(5,1.0)--(7,-1)--(9,1)--(Z); +} + +\uncover<5>{ +\draw[line width=4pt,color=red] (A)--(B4)--(3,0)--(4,1)--(5,0)--(6,1)--(7,0) + --(6.0,-1.0)--(7,-2)--(7.5,-1.5)--(7,-1)--(7.5,-0.5) + --(8.5,-1.5)--(Z); +} + +\uncover<6->{ + \draw[line width=4pt,color=red] (A)--(B5)--(6,2); +} +\uncover<7->{ + \draw[line width=4pt,color=red] (6,2)--(7,1)--(5,-1); +} +\uncover<8->{ + \draw[line width=4pt,color=red] (5,-1)--(6,-2)--(8,0)--(9,-1); +} +\uncover<9->{ + \draw[line width=4pt,color=red] (9,-1)--(Z); +} + +\blob{(A)}{$A$}{red!20} +\blob{(B1)}{$B_1$}{white} +\blob{(B2)}{$B_2$}{white} +\blob{(B3)}{$B_3$}{white} +\blob{(B4)}{$B_4$}{white} +\blob{(B5)}{$B_5$}{white} + +\blob{(Z)}{$Z$}{red!20} + +\uncover<6->{ + \node at (6,2) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/macdonalds.png}}; +} + +\uncover<7->{ + \node at (5,-1) {\includegraphics[width=1.5cm]{../slides/8/floyd-warshall/starbucks.png}}; +} + +\uncover<8->{ + \node at (9,-1) {\includegraphics[width=2cm]{../slides/8/floyd-warshall/burgerking.png}}; +} + +\end{tikzpicture} +\end{center} + +\begin{block}{Abstieg} +Für den kürzesten Weg von $A$ nach $Z$ suche denjenigen Nachbarn $B_i$ +von $A$, der den kürzesten Weg von $B_i$ nach $Z$ hat. +\uncover<7->{$\Rightarrow$ wir brauchen {\color{red}alle} kürzesten Wege!} +\end{block} + +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/starbucks.png b/vorlesungen/slides/8/floyd-warshall/starbucks.png Binary files differnew file mode 100644 index 0000000..a28dbf7 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/starbucks.png diff --git a/vorlesungen/slides/8/floyd-warshall/wege.tex b/vorlesungen/slides/8/floyd-warshall/wege.tex new file mode 100644 index 0000000..7ff62a1 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wege.tex @@ -0,0 +1,26 @@ +% +% wege.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\begin{frame} +\frametitle{Wege statt Weglänge?} +\begin{columns}[t] +\begin{column}{0.48\hsize} +\begin{block}{Wege speichern?} +\uncover<3->{Es reicht, einen Wegweiser zum nächsten Knoten zu speichern} +\end{block} +\begin{center} +\begin{tikzpicture}[>=latex] + +\end{tikzpicture} +\end{center} +\end{column} +\begin{column}{0.48\hsize} +\uncover<2->{% +\begin{center} +\includegraphics[width=\hsize]{../slides/8/floyd-warshall/wegweiser.jpg} +\end{center}}% +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/floyd-warshall/wegiteration.tex b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex new file mode 100644 index 0000000..84ec679 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wegiteration.tex @@ -0,0 +1,13 @@ +% +% wegiteration.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup +\newboolean{wegweiser} +\begin{frame}[fragile] +\frametitle{Floyd-Warshall: Wegweiser} +\setboolean{wegweiser}{true} +\input{../slides/8/floyd-warshall/fw.tex} +\end{frame} +\egroup diff --git a/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg Binary files differnew file mode 100644 index 0000000..33aebe3 --- /dev/null +++ b/vorlesungen/slides/8/floyd-warshall/wegweiser.jpg |
