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>


<language>Java</language>
=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">
<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 (06528)</li></td>
<td><li>Dohna</li></td>
</tr>
<tr>
<td><li>Eisenach (99817)</li></td>
<td><li>Dürrhennersdorf</li></td>
</tr>
<tr>
<td><li>Callenberg (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 (01640)</li></td>
<td><li>Seerhausen</li></td>
</tr>
</table>
</div>

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