Vertiefungsaufgabe
Robert Riedel: s3roried@stud.hszg.de
Bettina Sprenger: s3bespre@stud.hszg.de
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:
|
|
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.
Ermittelte Rundreise
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.
Starten wir beispielsweise in Dresden, so führt uns diese Rundreise folgenden Weg entlang, bis wir wieder an unserem Startpunkt ankommen:
Dresden, Dohna, Pirna, Dürrhennersdorf, Löbau, Eisenhüttenstadt, Berlin, Lüneburg, Eisenach, Blankenheim, Spröda, Callenberg, Limbach-Oberfrohna, Seerhausen, Riesa, Coswig, Dresden.
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.
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.