AuK/Durchläufe durch Graphen SS12/Vertiefungsaufgabe

Wiki-Quelltext dieser Seite.

__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: 

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

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