LaTeX-examples/documents/mathe-handlungsreisender/Handlungsreisender-in-Deutschland.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}