AuK/Durchläufe durch Graphen SS12/Vertiefungsaufgabe

Wiki-Quelltext dieser Seite.

<language>Java</language>
__NOTOC__
<div style="border-style:solid; border-width:1px; background-color:#EEE;max-width:40%;padding-left:10px">
Robert Riedel: [mailto:s3roried@stud.hszg.de s3roried@stud.hszg.de]<br>
Bettina Sprenger: [mailto:s3bespre@stud.hszg.de s3bespre@stud.hszg.de]
</div>



=Lösung des Rundreiseproblems (TSP)=

==Aufgabenstellung==
Eine PKW-Rundreise soll durch die folgenden Städte führen und dabei jeden dieser 16 Orte genau einmal besuchen: 

<div>
<table border="0" width="50%">
<tr>
<td width="50%">
<ul>
<li>Dresden</li>
<li>Berlin</li>
<li>Spröda</li>
<li>Lüneburg</li>
<li>Löbau</li>
<li>Limbach-Oberfrohna</li>
<li>Blankenheim (06528)</li>
<li>Dohna</li>
</ul>
</td>
<td>
<ul>
<li>Eisenach (99817)</li>
<li>Dürrhennersdorf</li>
<li>Callenberg (09337)</li>
<li>Eisenhüttenstadt</li>
<li>Pirna</li>
<li>Riesa</li>
<li>Coswig (01640)</li>
<li>Seerhausen</li>
</ul></td>
</tr>
</table>
</div>

'''Ausnahme:''' Die Stadt, in der die Rundreise beginnt und endet, ist die einzige zweimal besuchte Stadt.

'''Gesucht ist die kürzeste Rundreise.'''

===Entfernungsmatrix===
Unser TSP umfasst also 16 Städte und 120 Entfernungen. Der daraus konstruierte Graph besitzt demnach Knotenanzahl $|V| = 16$ und Kantenanzahl $|E| = 120$.
Daraus resultiert folgende symmetrische Entfernungsmatrix.

[[Bild:Croxeldyffic_Adjmatrix.jpg|800px|center]]

===Ermittelte Rundreise===

[[Bild:Croxeldyffic_Map03.jpg|right|thumb|200px|mit Optimap ermittelte Tour]]
Im Internet existieren zahlreichen Dienste und Programme, die für einen Graphen auf Basis einer Karte mit Entfernungsdaten (Quelle ist meistens Google Maps) die optimale Rundreise ermitteln.
So berechnet auch der ''Roundtrip Solver'' Optimap von GEBWEG für unser TSP eine optimale Tour von 1443 km Länge.

[http://gebweb.net/optimap/ Link zur Optimap-Webseite]

Starten wir beispielsweise in Dresden, so führt uns diese Rundreise folgenden Weg entlang, bis wir wieder an unserem Startpunkt ankommen:


<p style="margin-left:50px;margin-right:50px">Dresden, Dohna, Pirna, Dürrhennersdorf, Löbau, Eisenhüttenstadt, Berlin, Lüneburg,  Eisenach, Blankenheim, Spröda,  Callenberg, Limbach-Oberfrohna, Seerhausen, Riesa, Coswig, Dresden.
</p>

==Intuitiver Algorithmus==
Um das Rundreiseproblem mit Sicherheit lösen zu können, benötigt man das Minimum aller möglichen Touren. 
Die Anzahl aller dieser Touren wächst jedoch exponentiell mit der Knotenanzahl $n$, d.h. es müssen zunächst $(n-1)!/2$ Rundreisen bestimmt werden. Auf unser konkretes Beispiel mit 16 Städten bezogen sind das über 600 Milliarden Touren.

[[Bild:Croxeldyffic_Map-kreis.jpg|right|200px|thumb|eine zufällig gewählte Tour]]

Wir suchen also nach effizienteren Lösungsverfahren für dieses schwierige Problem.

Als erster Lösungversuch bietet sich daher eine zufällige ''gültige'' Tour an. Da wir mit einer Karte arbeiten, wählen wir am besten einen Kreis, um den Überblick über alle Städte zu behalten.

Die so ermittelte Tour besitzt ebenfalls eine Länge von 1443 km, wir haben also auf diese Weise die optimale Tour gefunden. Normalerweise ergibt jedoch ein derart zufälliges Verfahren eine beliebig schlechte Tour.

Da wir zu unserer Route bei jedem Schritt einen neuen Knoten hinzufügen, d.h. dass wir bei jedem Schritt eine neue Stadt besuchen, terminiert der Zufallsalgorithmus nach $\mathcal{O}(|V|)$ und liefert eine mögliche Lösung des TSP.

Zwar besitzen wir jetzt eine in Linearzeit ermittelte Lösung, jedoch können wir keine Aussage über deren Güte treffen, wenn wir die optimale Tour nicht kennen.

==Lösungsverfahren Branch & Bound==
==Näherungslösung MST-Heuristik==
Nun soll für einen weiteren Lösungsversuch des TSP die bekannte MST-Heuristik verwendet werden, ein Näherungsalgorithmus, der auf der Konstruktion eines minimalen Spannbaumes (MST) und Eulertouren beruht.

Der Zusammenhang zwischen einem TSP-Graphen und seinem minimalen Spannbaum besteht darin, dass eine Rundreise durch Wegfallen einer beliebigen Kante einen Hamiltonpfad ergibt, der gleichzeitig einen speziellen Spannbaum darstellt. Es gilt demnach $w(MST) \leq w(TSP)$ mit $w$ als Gewichtsfunktion. Die Konstruktion eines MST wird daher benutzt, um eine untere Schranke (Relaxation) für die optimale Tour angeben zu können.

Der Algorithmus (''tree algorithm'') lässt sich nun wie folgt formulieren:
<ol>
<li>Bestimme einen minimalen Spannbaum $T$ des TSP-Graphen $G$.</li>
<li>Verdopple alle Kanten in $T$ und erzeuge einen Multigraphen $T_m$.</li>
<li>Bestimme einen Eulerkreis $K$ von $T_m$.</li>
<li>Wähle eine in $K$ enthaltene Tour.</li>
</ol>

Wenden wir nun diesen Algorithmus auf das gegebene TSP mit Knotenanzahl $|V| = 16$ und Kantenanzahl $|E| = 120$ an.

Die Konstruktion des MST kann mit dem Algorithmus von Prim in $\mathcal{O}(|V|^2)$ Schritten durchgeführt werden und liefert den unten dargestellten Baum mit dem Gewicht $w(MST) = 1058,7$ km. Die optimale Tour ist demnach mindestens 1058,7 km lang.
[[Bild:Croxeldyffic_Mst.png|center|600px]]

Nach der Verdopplung aller Kanten des entstandenen Graphen kann nun ein Eulerkreis mit dem Algorithmus von Hierholzer in $\mathcal{O}(|E|)$ konstruiert werden. 
[[Bild:Croxeldyffic_Mst-double.png|center|600px]]

[[Bild:Croxeldyffic_Map-mst.jpg|right|200px|thumb|mit MST-Heuristik ermittelte Rundreise]]

Ein möglicher Eulerkreis ist zum Beispiel:
<p style="margin-left:50px;margin-right:50px">
Dresden, Dohna, Pirna, Dürrhennersdorf, Löbau, Eisenhüttenstadt, Berlin, Eisenhüttenstadt, Löbau, Dürrhennersdorf, Pirna, Dohna, Dresden, Coswig, Seerhausen, Riesa, Seerhausen, Limbach, Callenberg, Limbach, Seerhausen, Spröda, Blankenheim, Lüneburg, Blankenheim, Eisenach, Blankenheim, Spröda, Seerhausen, Coswig, Dresden
</p>

Aus diesem Eulerschen Kreis ergibt sich eine mögliche Rundreise, wenn alle im Kreis doppelt auftretenden Städte mit Ausnahme des Zielpunktes gestrichen werden. So erhalten wir aus obigem Eulerkreis folgende Tour:
<p style="margin-left:50px;margin-right:50px">
Dresden, Dohna, Pirna, Dürrhennersdorf, Löbau, Eisenhüttenstadt, Berlin, Coswig, Seerhausen, Riesa, Limbach, Callenberg, Spröda, Blankenheim, Lüneburg, Eisenach, Dresden
</p>
Diese Rundreise hat die Länge 1753,7 km. Da man diese aus dem Eulerkreis beliebig wählen kann, lässt sich auch mit dieser Heuristik lediglich mit Sicherheit sagen, dass die ermittelte Rundreise höchstens doppelt so groß ist, wie der minimale Spannbaum.


Die Verdopplung aller Kanten im Spannbaum, die Bestimmung eines Eulerkreises in diesem Multigraphen und die Auswahl einer darin enthaltenen Tour besitzen jeweils die Komplexität $\mathcal{O}(|E|)$. Ausschlaggebend für die asymptotische Aufwandsordnung der MST-Heuristik ist die Erzeugung eines minimalen Spannbaumes mit dem Algorithmus von Prim in $\mathcal{O}(|V|^2)$ Schritten. 

Die MST-Heuristik besitzt also ebenfalls die Komplexität $\mathcal{O}(|V|^2)$.

==Fazit==

An dieser Stelle sollen die obigen Lösungsverfahren zusammengefasst und gegenübergestellt werden.

<div>
<table align="center" width="50%" border="1" cellpadding="1" cellspacing="3">
<tr style="background-color:#EEE;text-align:center">
<td></td>
<td>Zufallsroute</td>
<td>Branch & Bound </td>
<td>MST-Heuristik</td>
</tr>
<tr>
<td>Laufzeit</td>
<td>$\mathcal{O}(|V|)$</td>
<td>$\mathcal{O}()$</td>
<td>$\mathcal{O}(|V|^2)$</td>
</tr>
<tr>
<td>exakte Lösung?</td>
<td>nein</td>
<td>ja</td>
<td>nein</td>
</tr>
<tr>
<td>Vorteile</td>
<td><ul>
    <li>intuitiv</li>
    <li>schnell</li>
    </ul></td>
<td><ul>
    <li>übersichtlich</li>
    <li>exakt</li>
    <li>effizient</li>
    </ul></td>
<td><ul>
    <li>einfach</li>
    <li>schnell</li>
    </ul></td>
</tr>
</table>
</div>