mirror of
https://github.com/MartinThoma/LaTeX-examples.git
synced 2025-04-19 11:38:05 +02:00
7740f0147f
The commands
find . -type f -name '*.md' -exec sed --in-place 's/[[:space:]]\+$//' {} \+
and
find . -type f -name '*.tex' -exec sed --in-place 's/[[:space:]]\+$//' {} \+
were used to do so.
202 lines
9.8 KiB
TeX
202 lines
9.8 KiB
TeX
\documentclass[a4paper,9pt]{scrartcl}
|
|
\usepackage[ngerman]{babel}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amssymb,amsmath}
|
|
\usepackage{geometry}
|
|
\usepackage{graphicx}
|
|
\usepackage{hyperref}
|
|
\usepackage{listings}
|
|
\usepackage{color}
|
|
|
|
\usepackage{slashbox}
|
|
|
|
\definecolor{gray}{gray}{0.5}
|
|
|
|
\lstset{
|
|
language=Python, % the language of the code
|
|
basicstyle=\footnotesize, % the size of the fonts that are used for the code
|
|
keywordstyle=\color{blue},
|
|
stringstyle=\color{red},
|
|
commentstyle=\color{gray}\slshape,
|
|
emph={class, pass, in, for, while, if, is, elif, else, not, and, or, def, print, exec, break, continue, return},
|
|
emphstyle=\color{black}\bfseries,
|
|
emph={[2]True, False, None, self},
|
|
emph={[3]from, import, as},
|
|
emphstyle=[3]\color{blue},
|
|
morecomment=[s]{"""}{"""},
|
|
rulesepcolor=\color{blue},
|
|
otherkeywords={1, 2, 3, 4, 5, 6, 7, 8 ,9 , 0, -, =, +, [, ], (, ), \{, \}, :, *, !},
|
|
numbers=left, % where to put the line-numbers
|
|
numberstyle=\footnotesize, % the size of the fonts that are used for the line-numbers
|
|
stepnumber=1, % the step between two line-numbers. If it's 1, each line
|
|
% will be numbered
|
|
numbersep=5pt, % how far the line-numbers are from the code
|
|
showspaces=false, % show spaces adding particular underscores
|
|
showstringspaces=false, % underline spaces within strings
|
|
showtabs=false, % show tabs within strings adding particular underscores
|
|
tabsize=2, % sets default tabsize to 2 spaces
|
|
captionpos=b, % sets the caption-position to bottom
|
|
breaklines=true, % sets automatic line breaking
|
|
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
|
|
title=\lstname, % show the filename of files included with \lstinputlisting;
|
|
% also try caption instead of title
|
|
escapeinside={\%*}{*)}, % if you want to add a comment within your code
|
|
morekeywords={*,...}, % if you want to add more keywords to the set
|
|
literate=%
|
|
{Ö}{{\"O}}1
|
|
{Ä}{{\"A}}1
|
|
{Ü}{{\"U}}1
|
|
{ß}{{\ss}}2
|
|
{ü}{{\"u}}1
|
|
{ä}{{\"a}}1
|
|
{ö}{{\"o}}1
|
|
}
|
|
|
|
\geometry{a4paper,left=18mm,right=18mm, top=1cm, bottom=2cm}
|
|
|
|
\setcounter{secnumdepth}{2}
|
|
\setcounter{tocdepth}{2}
|
|
|
|
\shorthandon{"}
|
|
\hypersetup{
|
|
pdftitle={Handlungsreisender in Deutschland},
|
|
pdfsubject={Aufgabe},
|
|
pdfauthor={Martin Thoma},
|
|
pdfkeywords={Aufgabe, Mathematik, Lösung}}
|
|
\shorthandoff{"}
|
|
|
|
\begin{document}
|
|
\title{Handlungsreisender in Deutschland}
|
|
\author{Martin Thoma}
|
|
|
|
|
|
\setcounter{section}{1}
|
|
\section*{Aufgabenstellung}
|
|
Ein Handlungsreisender will seine Produkte in den zehn größten Städten
|
|
Deutschlands verkaufen. Er startet in Berlin und will seine Reise dort
|
|
beenden.
|
|
|
|
Die zehn einwohnerreichsten Städte Deutschlands sind Berlin, Hamburg,
|
|
München, Köln, Frankfurt am Main, Stuttgart, Düsseldorf, Dortmund, Essen
|
|
und Bremen. \\
|
|
Folgende Tabelle gibt die Entfernung zwischen den Städten für eine Autoreise
|
|
wieder\footnote{Mit maps.google.com ermittelte Werte. Es wurde immer auf ganze Kilometer gerundet.}:
|
|
|
|
\begin{tabular}[hc]{|l|c|c|c|c|c|c|c|c|c|c|}
|
|
\hline
|
|
\backslashbox{von}{nach} & \rotatebox{90}{Berlin} & \rotatebox{90}{Hamburg} & \rotatebox{90}{München} & \rotatebox{90}{Köln} & \rotatebox{90}{Frankfurt am Main} & \rotatebox{90}{Stuttgart} & \rotatebox{90}{Düsseldorf} & \rotatebox{90}{Dortmund} & \rotatebox{90}{Essen} & \rotatebox{90}{Bremen} \\
|
|
\hline\hline
|
|
Berlin & 0 & 288 & 585 & 575 & 547 & 633 & 559 & 494 & 531 & 392 \\
|
|
Hamburg & 289 & 0 & 775 & 426 & 493 & 655 & 400 & 344 & 365 & 122 \\
|
|
München & 589 & 775 & 0 & 577 & 398 & 220 & 612 & 604 & 634 & 748 \\
|
|
Köln & 579 & 426 & 576 & 0 & 193 & 369 & 42 & 95 & 73 & 320 \\
|
|
Frankfurt a. M. & 552 & 492 & 393 & 193 & 0 & 210 & 229 & 219 & 251 & 445 \\
|
|
Stuttgart & 637 & 667 & 231 & 369 & 203 & 0 & 404 & 417 & 426 & 642 \\
|
|
Düsseldorf& 563 & 408 & 611 & 38 & 228 & 404 & 0 & 71 & 37 & 302 \\
|
|
Dortmund & 498 & 346 & 605 & 95 & 221 & 418 & 69 & 0 & 36 & 240 \\
|
|
Essen & 536 & 374 & 634 & 74 & 252 & 427 & 35 & 37 & 0 & 267 \\
|
|
Bremen & 397 & 123 & 748 & 315 & 441 & 638 & 289 & 233 & 254 & 0 \\
|
|
\hline
|
|
\end{tabular}\\
|
|
\\
|
|
Welche Route sollte er wählen?
|
|
|
|
\subsection{Größenordnung des Problems}
|
|
Es gibt $9! = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 362.880$ mögliche Routen,
|
|
da der Handlungsreisende in Berlin startet und 9 Möglichkeiten für die erste
|
|
Stadt hat, 8 für die zweite, usw.\\
|
|
Allgemein kann man sagen, dass bei $n$ Städten insgesamt $(n-1)!$ mögliche
|
|
Routen bestehen, da die Wahl des Startpunktes egal ist. \\
|
|
Falls das Problem symmetrisch wäre, also die Strecke von Berlin nach
|
|
München genauso lang wie die von München nach Berlin wäre, könnte man die
|
|
Anzahl der Routen auf $\frac{(n-1)!}{2}$ reduzieren. Allerdings ist das
|
|
Problem offensichtlich asymmetrisch (siehe München $\rightarrow$ Berlin und
|
|
München $\leftarrow$ Berlin)
|
|
|
|
Die Tabelle \ref{tab:functionGrowth} macht deutlich, wie schnell so etwas
|
|
wächst.
|
|
\begin{table}[hc]
|
|
\centering
|
|
\begin{tabular}[hc]{|l|r|r|r|r|r|r|}
|
|
\hline
|
|
n & $1$ & $log(n)$ & $n \cdot log(n)$ & $n^2$ & $n^3$ & $n!$ \\
|
|
\hline\hline
|
|
1 & 1 & 0 & 0 & 1 & 1 & 1 \\
|
|
2 & 1 & 0,30 & 0,60 & 4 & 8 & 2 \\
|
|
3 & 1 & 0,48 & 1,43 & 9 & 27 & 6 \\
|
|
4 & 1 & 0,60 & 2,41 & 16 & 64 & 24 \\
|
|
5 & 1 & 0,70 & 3,49 & 25 & 125 & 120 \\
|
|
6 & 1 & 0,78 & 4,67 & 36 & 216 & 720 \\
|
|
7 & 1 & 0,85 & 5,92 & 49 & 343 & 5.040 \\
|
|
8 & 1 & 0,90 & 8,13 & 64 & 512 & 40.320\\
|
|
9 & 1 & 0,95 & 8,59 & 81 & 729 & 362.880\\
|
|
10 & 1 & 1,00 & 10,00 & 100 & 1.000 & 3.628.800\\
|
|
20 & 1 & 1,30 & 26,02 & 400 & 8.000 & $2,42 \cdot 10^{18}$ \\
|
|
\hline
|
|
\end{tabular}
|
|
\caption{Wachstum verschiedener Funktionen}
|
|
\label{tab:functionGrowth}
|
|
\end{table}
|
|
\newpage
|
|
\subsection{Intuitive Lösung}
|
|
Wenn man die Städte so auf der Karte sieht sollte man einfach mal die Route
|
|
suchen, von der man denkt sie wäre gut. \\
|
|
\begin{center}
|
|
%\includegraphics{Germany_location_map.png}
|
|
\end{center}
|
|
Ich habe mir folgende ausgesucht:\\
|
|
\begin{center}
|
|
%\includegraphics{Germany_location_map-intuitiv.png}
|
|
\end{center}
|
|
Das ist die Route Berlin $\rightarrow$ München $\rightarrow$ Stuttgart
|
|
$\rightarrow$ Frankfurt a. M. $\rightarrow$ Köln $\rightarrow$ Düsseldorf
|
|
$\rightarrow$ Essen $\rightarrow$ Dortmund $\rightarrow$ Bremen
|
|
$\rightarrow$ Hamburg $\rightarrow$ Berlin.
|
|
Diese Route ist 1969 km lang.
|
|
|
|
\newpage
|
|
\subsection{Optimale Lösung}
|
|
\subsubsection{Alle Routen durchgehen}
|
|
Die primitivste und langsamste Methode zum Finden der optimalen Lösung ist
|
|
einfach alle möglichen Routen durch zu gehen. Dieser Algorithmus ist, was
|
|
die Ausführungszeit angeht, in $\mathcal{O}(n!)$. Wie schnell diese wächst
|
|
sollte mit Tabelle \ref{tab:functionGrowth} klar geworden sein.\\
|
|
Dieser Ansatz ist also nur für sehr kleine Instanzen des Problems geeignet.\\
|
|
\\
|
|
Eine Auswertung aller Stecken hat folgende Ergebnisse geliefert: \\
|
|
1969 km bzw. die von mir intuitiv gefundene Strecke ist eine von 10 optimalen Lösungen.\\
|
|
Die längste Route ist 4.913 km lang.\\
|
|
Es gibt 3.628.800 Routen, jedoch nur 2.597 verschiedene Streckenlängen. Die
|
|
durchschnittliche Streckenlänge beträgt 3.838 km und wurde rot eingezeichnet,
|
|
die maximale 4.913 km.\\
|
|
Die Verteilung der Streckenlängen sieht wie folgt aus:\\
|
|
%\includegraphics{Kurve.png}
|
|
\\
|
|
Würde man eine maximale Abweichung von $5\%$ akzeptieren, wären nur $0,002\%$
|
|
aller Routen akzeptabel. Durch eine zufällig gewählte Strecke wird man also
|
|
kaum ein gutes Ergebnis erziehlen
|
|
\subsection{Heuristiken}
|
|
Eine Heuristik ist in diesem Zusammenhang ein vereinfachtes Verfahren, das
|
|
keine optimale Lösung liefert, aber eine akzeptable Näherung daran. Dafür
|
|
ist die Heuristik deutlich schneller.\\
|
|
\subsubsection{Nächster Nachbar}
|
|
Eine mögliche Heurisik ist das auswählen der Stadt, die am nächsten zur
|
|
aktuellen Stadt liegt. Mit diesem Verfahren erhält man bei der gegebenen
|
|
Städtekonstellation eine Route der Länge 2.162 km. Das sind 193 km oder
|
|
$9,8\%$ mehr als die optimale Lösung benötigt.
|
|
|
|
\subsubsection{Nächster Nachbar - Dynamisch Einfügen}
|
|
Die Methode des nächsten Nachbars kann verbessert werden, indem der Nachbar
|
|
nicht einfach am Ende in die Route eingefügt wird, sondern an die Stelle, an
|
|
der die resultierende Route am kleinsten wäre. Damit erhält man bei der
|
|
gegebenen Städtekonstellation eine optimale Route.
|
|
|
|
\newpage
|
|
\lstinputlisting[language=Python]{Handlungsreisender-in-Deutschland-Alle-Routen.py}
|
|
\newpage
|
|
\lstinputlisting[language=Python]{Handlungsreisender-in-Deutschland-analyse.py}
|
|
\newpage
|
|
\lstinputlisting[language=Python]{Handlungsreisender-in-Deutschland-Nearest-Neighbour.py}
|
|
\newpage
|
|
\lstinputlisting[language=Python]{Handlungsreisender-in-Deutschland-Nearest-Insertion.py}
|
|
\end{document}
|