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]]
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==
==Lösungsverfahren Branch & Bound==
==Näherungslösung MST-Heuristik==
==Fazit==