421 lines
19 KiB
TeX
421 lines
19 KiB
TeX
\documentclass[a4paper,10pt,ngerman]{scrartcl}
|
|
\usepackage{babel}
|
|
\usepackage[a4paper,margin=2.5cm]{geometry}
|
|
|
|
% automatische Quotes
|
|
\usepackage{csquotes}
|
|
|
|
% Die nächsten drei Felder bitte anpassen:
|
|
\newcommand{\Name}{Arne Keller} % Teamname oder eigenen Namen angeben
|
|
\newcommand{\TeilnahmeId}{50966}
|
|
\newcommand{\Aufgabe}{Aufgabe 1: Lisa rennt}
|
|
|
|
% Kopf- und Fußzeilen
|
|
\usepackage{scrlayer-scrpage, lastpage}
|
|
\setkomafont{pageheadfoot}{\textrm}
|
|
\lohead{\Aufgabe}
|
|
\chead{\thepage{}/\pageref{LastPage}}
|
|
\rohead{\Name/Teilnahme-Id: \TeilnahmeId}
|
|
\cfoot{}
|
|
|
|
% Für mathematische Befehle und Symbole
|
|
\usepackage{textcomp}
|
|
\usepackage{amsmath,amsthm,gensymb}
|
|
|
|
% Für Bilder
|
|
\usepackage{graphicx,subcaption,float}
|
|
% Für Skizzen
|
|
\usepackage{tkz-euclide}
|
|
\usepackage{tkz-graph}
|
|
\usetkzobj{all}
|
|
|
|
% Für Quelltext
|
|
\usepackage{listings}
|
|
\usepackage{color}
|
|
\definecolor{mygreen}{rgb}{0,0.6,0}
|
|
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
|
|
\definecolor{mymauve}{rgb}{0.58,0,0.82}
|
|
\lstset{
|
|
keywordstyle=\color{blue},commentstyle=\color{mygreen},
|
|
stringstyle=\color{mymauve},rulecolor=\color{black},
|
|
basicstyle=\footnotesize\ttfamily,numberstyle=\tiny\color{mygray},
|
|
captionpos=b, % sets the caption-position to bottom
|
|
keepspaces=true, % keeps spaces in text
|
|
numbers=left, numbersep=5pt, showspaces=false,showstringspaces=false,
|
|
showtabs=false, stepnumber=2, tabsize=2, title=\lstname
|
|
}
|
|
\lstdefinelanguage{Rust}{
|
|
keywords={break, match, continue, else, for, fn, if, return, self, let, mut, loop, while, extern, crate, use, static, enum, struct, impl, as, type, derive, mod},
|
|
morecomment=[l]{//},
|
|
morecomment=[s]{/*}{*/},
|
|
morestring=[b]",
|
|
sensitive=true
|
|
}
|
|
|
|
% Diese beiden Pakete müssen als letztes geladen werden
|
|
%\usepackage{hyperref} % Anklickbare Links im Dokument
|
|
%\usepackage{cleveref}
|
|
|
|
% Daten für die Titelseite
|
|
\title{\Aufgabe}
|
|
\author{\Name\\Teilnahme-ID: \TeilnahmeId}
|
|
\date{29. April 2019}
|
|
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
\tableofcontents
|
|
|
|
\section{Lösungsidee}
|
|
Der einfachste Fall ist der, in dem Lisa keine Hindernisse berücksichtigen muss. Würde der Bus zudem die gleiche Geschwindigkeit wie Lisa haben, müsste Lisa die Route vom Bus (die y-Achse) in einem 90\degree-Winkel treffen. So kann sie möglichst spät loslaufen. Generell tritt dieser Fall immer im letzten Abschnitt von Lisas Route auf. Nachdem sie eventuelle Hindernisse passiert hat, läuft sie danach immer direkt zur y-Achse. Wenn sie so am Ende der Route zum Bus läuft, gibt es theoretisch gesehen keinen, einen oder zwei Treffpunkte, bei denen Lisa (ohne zu warten) den Bus erwischt (siehe Abb. \ref{fig:treffpunkte}).
|
|
|
|
\begin{proof}
|
|
Sei Lisa bei $L(x_{L},y_{L})$ und der Bus bei $B(x_{B},y_{B})$. $M(x_{M},y_{M})$ sei der Treffpunkt von Lisa mit dem Bus. $d$ sei der Weg, den Lisa zu diesem Punkt geht.
|
|
\begin{align*}
|
|
d &= \sqrt{(x_{L}-x_{M})^2 + (y_{L}-y_{M})^2} &&\text{(Satz des Pythagoras)} \\
|
|
&= \sqrt{x_{L}^2 + (y_{L}-y_{M})^2} &&\text{($x_{B} = x_{M} = 0$)} \\
|
|
d^2 &= x_{L}^2 + (y_{L}-y_{M})^2 \\
|
|
&= x_{L}^2 + (y_{L}-y_{B}-2d)^2 &&\text{($y_{M} = y_{B} + 2d$)} \\
|
|
&= x_{L}^2 + y_{L}^2 + y_{B}^2 + 4d^2 - 2y_{B}y_{L} - 4dy_{L} + 4dy_{B} \\
|
|
0 &= x_{L}^2 + y_{L}^2 + y_{B}^2 + 3d^2 - 2y_{B}y_{L} - 4dy_{L} + 4dy_{B} \\
|
|
d &= \frac{-b\pm\sqrt{b^2 - 12\cdot{}(x_{L}^2 + y_{L}^2 + y_{B}^2 - 2y_{B}y_{L})}}{6} &&\text{($b = 4\cdot(y_{B}-y_{L})$)}
|
|
\end{align*}
|
|
Für diese Gleichung gibt es maximal zwei nicht-negative Lösungen.\qedhere
|
|
\end{proof}
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.5]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0){B}
|
|
\tkzDefPoint(1.25,3.5){L}
|
|
\tkzDefPoint(0,2.83333){M1}
|
|
\tkzDefPoint(0,6.5){M2}
|
|
|
|
\tkzDrawSegment(L,M1)
|
|
\tkzDrawSegment(L,M2)
|
|
\tkzDrawPoints(B,L,M1,M2)
|
|
|
|
\tkzLabelPoints(B,L,M1,M2)
|
|
\end{tikzpicture}
|
|
\caption{Zwei Treffpunkte}
|
|
\label{abb:fall1}
|
|
\end{subfigure}%
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.5]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0){B}
|
|
\tkzDefPoint(2.020725942,3.5){L}
|
|
\tkzDefPoint(0,4.614){M}
|
|
|
|
\tkzDrawSegment(L,M)
|
|
\tkzDrawPoints(B,L,M)
|
|
|
|
\tkzLabelPoints[yshift=14pt](M)
|
|
\tkzLabelPoints(B,L)
|
|
\end{tikzpicture}
|
|
\caption{Ein Treffpunkt}
|
|
\label{abb:fall2}
|
|
\end{subfigure}%
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.5]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0){B}
|
|
\tkzDefPoint(3,3.5){L}
|
|
|
|
\tkzDrawPoints(B,L)
|
|
|
|
\tkzLabelPoints(B,L)
|
|
\end{tikzpicture}
|
|
\caption{Kein Treffpunkt}
|
|
\label{abb:fall3}
|
|
\end{subfigure}
|
|
\caption{Mögliche Treffpunktanzahlen}
|
|
\label{fig:treffpunkte}
|
|
\end{figure}
|
|
|
|
Wenn zwei Treffpunkte möglich sind, kann die y-Startkoordinate des Busses erhöht werden. Dabei konvergieren die beiden Treffpunkte zu einem Punkt. Um die diesem Punkt entsprechende Position des Busses zu ermitteln, kann man die Wurzel in der letzten Gleichung gleich Null setzen. Löst man nach $y_{B}$ auf, erhält man die Position des Busses, bei dessen Durchquerung Lisa anfangen sollte zu laufen. So kann man für jede Position berechnen, wann Lisa spätestens von dieser loslaufen müsste. Der Winkel, in dem Lisa die y-Achse trifft, ist vom Verhältnis der Geschwindigkeiten von Lisa und dem Bus abhängig: $cos(60\degree) = \frac{15}{30}$. Für andere Winkel müsste Lisa früher loslaufen. In der linken und rechten Abbildung ist der Bus dementsprechend noch weiter unten auf der y-Achse:
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.3]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0.3){B}
|
|
\tkzDefPoint(2,4){L}
|
|
\tkzDefPoint(0,4.36667){M}
|
|
|
|
\tkzMarkAngle[fill=orange,size=0.8cm,opacity=.4](B,M,L)
|
|
\tkzDrawSegment(L,M)
|
|
\tkzDrawSegment(B,M)
|
|
\tkzDrawPoints(B,L,M)
|
|
\tkzLabelAngle[pos=0.5](B,M,L){$\alpha$}
|
|
|
|
\tkzLabelPoints[yshift=14pt](M,B)
|
|
\tkzLabelPoints(L)
|
|
\end{tikzpicture}
|
|
\caption{$\alpha > 60\degree$}
|
|
\label{abb:winkel1}
|
|
\end{subfigure}%
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.3]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0.5359){B}
|
|
\tkzDefPoint(2,4){L}
|
|
\tkzDefPoint(0,5.155){M}
|
|
|
|
\tkzMarkAngle[fill=orange,size=0.8cm,opacity=.4](B,M,L)
|
|
\tkzDrawSegment(L,B)
|
|
\tkzDrawSegment(B,M)
|
|
\tkzDrawSegment(L,M)
|
|
\tkzMarkRightAngle(M,L,B)
|
|
\tkzDrawPoints(B,L,M)
|
|
\tkzLabelAngle[pos=0.5](B,M,L){$\alpha$}
|
|
|
|
\tkzLabelPoints[yshift=14pt](M)
|
|
\tkzLabelPoints(B,L)
|
|
\end{tikzpicture}
|
|
\caption{$\alpha = 60\degree$}
|
|
\label{abb:winkel2}
|
|
\end{subfigure}%
|
|
\begin{subfigure}{.33\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=3.5,ymax=6.3]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoint(0,0.3){B}
|
|
\tkzDefPoint(2,4){L}
|
|
\tkzDefPoint(0,6.1){M}
|
|
|
|
\tkzMarkAngle[fill=orange,size=0.8cm,opacity=.4](B,M,L)
|
|
\tkzDrawSegment(L,M)
|
|
\tkzDrawSegment(B,M)
|
|
\tkzDrawPoints(B,L,M)
|
|
\tkzLabelAngle[pos=0.5](B,M,L){$\alpha$}
|
|
|
|
\tkzLabelPoints[yshift=14pt](M,B)
|
|
\tkzLabelPoints(L)
|
|
\end{tikzpicture}
|
|
\caption{$\alpha < 60\degree$}
|
|
\label{abb:winkel3}
|
|
\end{subfigure}
|
|
\caption{Mögliche Winkel}
|
|
\label{fig:winkel}
|
|
\end{figure}
|
|
|
|
Lisas Haus und die Ecken der Hindernisse kann man als Graph darstellen (siehe Abb. \ref{fig:graph}). Eine Kante zwischen zwei Ecken ist nur dann vorhanden, wenn Lisa geradlinig vom einen zum anderen Punkt laufen kann. Mögliche Wege, die nicht geradlinig sind, sind immer suboptimal, da diese immer einem Hindernis ausweichen würden. Stattdessen ist es besser, zuerst zu einer Ecke des Hindernisses zu gehen und dann weiterzugehen (siehe Abb. \ref{fig:gewicht}). Die Gewichtung der Kanten kann nicht einfach nur der euklidische Abstand der beiden Punkte sein, da Lisa nicht den kürzesten Weg finden will, sondern möglichst lange schlafen will. Daher haben diese ein Gewicht, das proportional zur Zeit ist, die Lisa früher aufstehen müsste, wenn sie zu einem bestimmten Punkt geht, statt direkt zum Bus zu gehen ($x$ in Abb. \ref{fig:gewicht}).
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=5.2,ymax=5.2]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoints{3.8214/2.6286/P0_0,4.357/0.2/P0_1,3.2857/0.2/P0_2,3.8214/2.6286/P0_3}
|
|
\tkzDrawPolygon[fill=black,line width=1pt,opacity=0.5](P0_0,P0_1,P0_2,P0_3)
|
|
\tkzDefPoint(0,0.9017){B0}
|
|
\tkzDefPoint(0,2.4755){B1}
|
|
\tkzDefPoint(4.5214,1.05){R0}
|
|
\tkzDefPoint(3.8214,2.6286){R1}
|
|
\tkzDefPoint(0,4.8348){R2}
|
|
\tkzDrawSegment(R0,R1)
|
|
\tkzDrawSegment(R1,R2)
|
|
\tkzDrawSegment(B0,R2)
|
|
\draw [dashed] (R0) -- (R2);
|
|
\draw [decorate,decoration={brace,mirror,amplitude=10pt,raise=4pt},yshift=0pt]
|
|
(B0) -- (B1) node [black,midway,xshift=0.7cm] {$x$};
|
|
\tkzDrawPoint[fill=yellow,color=black,size=13](B0)
|
|
\tkzDrawPoint[fill=green,color=black,size=13](B1)
|
|
\tkzDrawPoint[fill=red,color=black,size=13](R0)
|
|
\tkzDrawPoint[fill=yellow,color=black,size=13](R1)
|
|
\tkzDrawPoint[fill=red,color=black,size=13](R2)
|
|
\end{tikzpicture}
|
|
\caption{Kantengewicht}
|
|
\label{fig:gewicht}
|
|
\end{figure}
|
|
|
|
Es gibt viele Suchalgorithmen für Graphen, die einen kürzesten Weg bestimmen. Allerdings ist es nicht einfach, eine Heuristik, die z.B. von A* benötigt wird, aufzustellen. Sowohl die Distanz zur y-Achse auch als die Anzahl der Hindernisse auf direktem Weg zum Bus können nicht in das Einheitensystem der Kantengewichte übertragen werden, was von A* benötigt wird. Daher sind Suchalgorithmen ohne solche Heuristikfunktionen besser geeignet. Eine Breiten- oder Tiefensuche wäre allerdings nicht besonders performant, da diese entweder zu langsam vorwärtskommen (Breitensuche) oder sich zuerst auf eine suboptimale Route fokussieren können (Tiefensuche). Da die Kantengewichte immer nicht-negativ sind, kann auch der Dijkstra-Algorithmus verwendet werden.
|
|
|
|
Ein weiteres Problem ist die Bestimmung der Kanten. Um sicher alle möglichen Wege zu finden, müssen $\frac{n*(n-1)}{2}+n$ Überprüfungen durchgeführt werden, wobei $n$ die Anzahl der Wegpunkte ist. Wegpunkte sind Lisas Haus und die Ecken der Hindernisse. Da die Anzahl der benötigten Überprüfungen ca. quadratisch anwächst, sollten diese möglichst schnell durchgeführt werden. Um für jeden Wegabschnitt zu überprüfen, ob er eins der Hindernisse schneidet (nicht nur berührt), kann man für jedes Hindernis ausrechnen, ob die Gerade das entsprechende Polygon schneidet. Allerdings würde die Rechenzeit dann kubisch wachsen.
|
|
|
|
Zudem ist die Anzahl der möglichen Routen sehr groß: ca. $n!$. In einem Suchalgorithmus sollten also zuerst die Routen ausprobiert werden, die wahrscheinlich zu einer guten Lösung führen. Unvollständige Routen, die schlechter als während der Suche gefundene Lösungen sind, können auch verworfen werden.
|
|
|
|
\begin{figure}[H]
|
|
\centering
|
|
\begin{subfigure}{.48\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\tkzInit[xmax=5,ymax=2.5]
|
|
\tkzAxeXY
|
|
\tkzGrid
|
|
\tkzDefPoints{0.75/0.75/P0_0,2.25/0.75/P0_1,1.75/2/P0_2,1.25/2/P0_3}
|
|
\tkzDrawPolygon[fill=black,line width=1pt,opacity=0.5](P0_0,P0_1,P0_2,P0_3)
|
|
\tkzDefPoint(3,1){R0}
|
|
\tkzDrawPoint[fill=red,color=black,size=13](R0)
|
|
\end{tikzpicture}
|
|
\caption{Eingabe}
|
|
\label{abb:eingabe}
|
|
\end{subfigure}%
|
|
\begin{subfigure}{.48\textwidth}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\SetGraphUnit{1.5}
|
|
\GraphInit[vstyle=Normal]
|
|
\SetVertexSimple[Shape=circle,FillColor=green!50]
|
|
\Vertex{L}
|
|
\SetVertexSimple[Shape=rectangle,FillColor=blue!50]
|
|
\WE(L){P0E0}
|
|
\WE(P0E0){P0E1}
|
|
\NO(P0E1){P0E2}
|
|
\EA(P0E2){P0E3}
|
|
\SetVertexSimple[Shape=circle,FillColor=yellow!50]
|
|
\NOWE(P0E2){B}
|
|
\Edge(L)(P0E0)
|
|
\Edge(L)(P0E3)
|
|
\Edge(P0E0)(P0E1)
|
|
\Edge(P0E0)(P0E3)
|
|
\Edge(P0E1)(P0E2)
|
|
\Edge(P0E2)(P0E3)
|
|
\Edge(P0E1)(B)
|
|
\Edge(P0E2)(B)
|
|
\Edge(P0E3)(B)
|
|
\end{tikzpicture}
|
|
\caption{Graph}
|
|
\label{abb:graph-eingabe}
|
|
\end{subfigure}
|
|
\caption{Konvertierung der Eingabe zu einem Graphen}
|
|
\label{fig:graph}
|
|
\end{figure}
|
|
|
|
\section{Bedienung des Programms}
|
|
Das Programm liest die Problemstellung von der Standardeingabe ein. Die grafische Ausgabe wird in die Standardausgabe geschrieben. Wird $-t$ übergeben, kann die Ausgabe in einem \LaTeX-Dokument verwendet werden. Standardmäßig wird ein SVG-Dokument erzeugt. Falls man die Geschwindigkeit von Lisa oder dem Bus verändern will, kann man dies mit $-l$ bzw. $-b$ tun. Für zusätzliche Debug-Ausgaben kann man $-d$ verwenden. Die Standardoptionen $-h$ und $-V$ zeigen die Hilfe und die Version des Programms an.
|
|
\lstinputlisting[caption=Hilfetext des Programmes,frame=single,breaklines=true]{help.txt}
|
|
SVG-Dateien können auch als Eingabe verwendet werden, weil das vorgegebene Eingabeformat mühsam zu schreiben ist. Punkte werden als Startpunkte interpretiert, sonstige Pfade als Hindernisse. Interessanterweise ist die y-Achse in SVGs umgedreht, was vom Programm ausgeglichen wird. So sehen das Original-SVG und die Lösung gleich aus.
|
|
|
|
\section{Umsetzung}
|
|
Das Programm benutzt den Dijkstra-Algorithmus, um die beste Route für Lisa zu finden. Der schon beschriebene Graphen wird aus der Eingabedatei konstruiert, wobei die Kantenbestimmung aus Performanzgründen bei Bedarf erfolgt. Um die Route abzuschließen, probiert das Programm danach immer, auf direktem Weg die y-Achse zu erreichen. Die Route, bei dem Lisa sich am meisten Zeit lassen kann, wird gespeichert und ausgegeben.
|
|
|
|
Der Weg von Lisa und dem Bus wird im SVG-Dokument animiert angezeigt. Zusätzlich zu den unbedingt benötigten Ausgaben wie z.B. der Start- und Zielzeit gibt das Programm auch noch die theoretisch (ohne Hindernisse) beste Startzeit aus. Nützlich sind auch die Debug-Ausgaben, die Statistiken zur Eingabedatei und der Performanz (Zeit pro Iteration, Gesamtzeit) enthalten.
|
|
|
|
\subsection{Laufzeitanalyse}
|
|
Da programmintern der Dijkstra-Algorithmus verwendet wird, entspricht die Laufzeit in etwa diesem. Somit ist die Zeitkomplexität ca. $O(n^2)$, wobei $n$ die Anzahl der Ecken aller Polygone ist. Effektiv können allerdings in jedem Schritt nur eine kleine Anzahl anderer Ecken erreicht werden, was den Algorithmus beschleunigen könnte. Allerdings müssen auch die Kanten bestimmt werden, was im schlechtesten Fall $O(n^3)$ Rechenzeit beanspruchen kann. In Abschnitt \ref{performance} werden diese theoretischen Werte überprüft.
|
|
|
|
\subsection{Optimierungen}
|
|
Das Programm benutzt bestimmte Heuristiken, um die Suche zu beschleunigen. Eine davon ist die maximal mögliche Aufstehzeit für eine bestimmte Route. Um diese schnell zu berechnen, kann man zunächst feststellen, das der Bus mit konstanter Geschwindigkeit fährt. Deshalb ist eine Startposition des Busses mit einer kleineren y-Koordinate äquivalent zu einem früheren Aufstehen von Lisa. Das Programm berechnet daher die höchstmögliche Startposition für eine gegebene Route, weil diese Größe proportional zur gesuchten Größe ist.
|
|
|
|
Um zu überprüfen, ob ein Routenabschnitt die Hindernisse schneidet, wird unter anderem ein R*-Baum benutzt. Ein R*-Baum funktioniert ähnlich wie ein Binärbaum, aber mit geometrischen Objekten statt normal sortierbaren Datenstrukturen. Für jedes Hindernis muss die Rechteckbox bestimmt werden, in die das Polygon genau passt. Aufgebaut wird der Baum dann aus diesen minimal umgebenden Rechtecken, wobei in jedem Indexknoten generell mehrere Unterknoten enthalten sind. Im Indexknoten ist auch das gemeinsame umgebende Rechteck gespeichert. So kann man dann für eine beliebige geometrische Figur (z. B. auch eine Linie) alle Polygone finden, die diese schneiden, indem man ausgehend vom Hauptindexknoten überprüft, welche Unterknoten die Linie schneidet. Dies wird wiederholt, bis die unterste Ebene, die die Polygone enthält, erreicht ist. Danach wird für jedes Hindernis überprüft, ob die Linie dieses nicht nur berührt, sondern auch schneidet. Für ca. 40 Polygone ist diese Methode ca. 5-6x schneller als alle Polygone zu überprüfen. Die Geschwindigkeitsgewinne werden größer, je mehr Polygone vorhanden sind. Zudem wird das Ergebnis in einer Hashtabelle gespeichert, was die insgesamte Performanz ca. 6-10x steigert.
|
|
|
|
Von eher technischer Natur sind bestimmte Compiler-Optionen wie LTO (Link-time optimization) oder das Verwenden einer einzigen Codegen-Einheit, um mehr Optimierungen zu ermöglichen. Auch das Deaktivieren vom sogenannten 'unwinding' nach einem fatalen Fehler ('panic') verbessert die Performanz. Valgrind (ein Profiler) und KCachegrind (Auswertung der Profiling-Daten) waren auch sehr hilfreich, um herauszufinden, welche Programmteile besonders ineffizient sind. Trotzdem sind die im letzten Abschnitt beschriebenen Hindernisüberprüfungen für mehr als 90\% der Laufzeit verantwortlich.
|
|
|
|
\section{Beispiele}
|
|
Alle Beispiele sind im Maßstab 1:70m. Für die folgenden fünf Beispiele benötigt das Programm höchstens 1 ms Rechenzeit.
|
|
\lstinputlisting[caption=Lösung für lisarennt1.txt,frame=single,breaklines=true]{run1.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{run1.tkz}
|
|
\caption{Beispiel 1}
|
|
\label{fig:bsp1}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für lisarennt2.txt,frame=single,breaklines=true]{run2.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{run2.tkz}
|
|
\caption{Beispiel 2}
|
|
\label{fig:bsp2}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für lisarennt3.txt,frame=single,breaklines=true]{run3.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{run3.tkz}
|
|
\caption{Beispiel 3}
|
|
\label{fig:bsp3}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für lisarennt4.txt,frame=single,breaklines=true]{run4.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{run4.tkz}
|
|
\caption{Beispiel 4}
|
|
\label{fig:bsp4}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für lisarennt5.txt,frame=single,breaklines=true]{run5.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{run5.tkz}
|
|
\caption{Beispiel 5}
|
|
\label{fig:bsp5}
|
|
\end{figure}
|
|
\subsection{Eigene Beispiele}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp2} (5 ms Rechenzeit),frame=single,breaklines=true]{runwelt3.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt3.tkz}
|
|
\caption{Heuristikfalle}
|
|
\label{fig:ebsp2}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp3} (30 ms Rechenzeit),frame=single,breaklines=true]{runwelt4.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt4.tkz}
|
|
\caption{Angriff der Dreiecksgrundstücke (aus Aufgabe 2 entflohen)}
|
|
\label{fig:ebsp3}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp4} (250 ms Rechenzeit),frame=single,breaklines=true]{runwelt7b.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt7b.tkz}
|
|
\caption{Text}
|
|
\label{fig:ebsp4}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp5} (4 ms Rechenzeit),frame=single,breaklines=true]{runwelt5.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt5.tkz}
|
|
\caption{Mauern}
|
|
\label{fig:ebsp5}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp6} (3 ms Rechenzeit),frame=single,breaklines=true]{runwelt6.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt6.tkz}
|
|
\caption{Oktagone}
|
|
\label{fig:ebsp6}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp7} (25 ms Rechenzeit),frame=single,breaklines=true]{runwelt8.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt8.tkz}
|
|
\caption{Höhle}
|
|
\label{fig:ebsp7}
|
|
\end{figure}
|
|
\lstinputlisting[caption=Lösung für Abb. \ref{fig:ebsp8} (3 s Rechenzeit),frame=single,breaklines=true]{runwelt9.txt}
|
|
\begin{figure}[H]
|
|
\centering
|
|
\input{welt9.tkz}
|
|
\caption{Irrgarten}
|
|
\label{fig:ebsp8}
|
|
\end{figure}
|
|
\subsection{Performanzmessungen} \label{performance}
|
|
Die Routenberechnung für die Welt aus Abb. \ref{fig:ebsp3} benötigt ca. 30 ms (452 Ecken). Für vier dieser Welten, die in einem Quadrat angeordnet sind (1808 Ecken), benötigt das Programm ca. 900 ms. Die Laufzeit ist daher ungefähr proportional zu $n^{2.5}$, wobei $n$ die Anzahl der Ecken ist. Dies bestätigt auch eine weitere Messung mit einer nochmals so vergrößerten Welt: 7224 Ecken, 29000 ms.
|
|
|
|
\section{Quellcode (Hauptalgorithmus)}
|
|
\lstinputlisting[frame=single,language=Rust,breaklines=true]{src/main.rs}
|
|
|
|
\end{document}
|