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===

==Intuitiver Algorithmus==
==Lösungsverfahren Branch & Bound==
==Näherungslösung MST-Heuristik==
==Fazit==