Das Traveling Salesman Problem (TSP)
Unter dem Problem des Handlungsreisenden versteht man die folgende Aufgabenstellung: Ein Handlungsreisender möchte von seinem Startort aus verschiedene Städte besuchen und am Ende wieder zum Startort zurückkehren. Welche der möglichen Routen ist die kürzeste? Alternativ wird das Problem des Handlungsreisenden dabei auch als Traveling SalesmanProblem bezeichnet.
Von der Reiseroute zum ungerichteten Graphen
Möchte man die Aufgabe ein wenig abstrahieren, um sie mit einem Computer lösen zu können, so betrachtet man am einfachsten einen ungerichteten Graphen, dessen Knoten die verschiedenen Städte symbolisieren, während die Kanten für die Straßenverbindung zwischen den Städten stehen. Außerdem werden noch Kantengewichte eingeführt, welche für die Länge der jeweiligen Straße stehen. Dann ist der Pfad auf diesem Graphen gesucht, der alle Knoten miteinander verbindet, im gewünschten Startort beginnt und endet und die kürzeste Gesamtlänge aufweist. Die Gesamtlänge berechnet sich dabei als Summe der Kantengewichte.
Trotz des relativ leicht zu verstehenden Problems ist diese Frage im Allgemeinen schwer zu beantworten. Man könnte natürlich einfach seinen Computer anhand eines selbstgeschriebenen Programms mithilfe einer Brute-Force-Methode alle möglichen Routen durchprobieren lassen. Ausgewählt wird dann einfach diejenige Route, die die geringste Gesamtlänge aufweist. Dies funktioniert für eine kleine Anzahl an involvierten Städten auch noch recht gut. Sobald allerdings viele Städte besucht werden sollen, wird die Rechenzeit der Brute-Force-Methode quälend lang. Dies liegt daran, dass die Anzahl der möglichen Routen mit der Anzahl der Städte sehr schnell anwächst. Für wenige Städte wirkt dies zunächst harmlos: So gibt es bei zwei Städten (bei festem Startort) offensichtlich nur eine mögliche Route, bei drei Städten sind es erst 2, bei vieren 6 mögliche Reisewege im Traveling Salesman Problem (TSP).
Erschöpfende Verfahren oder Näherungsverfahren?
Aber: Während für 10 Städte “nur” etwa 360.000 mögliche Rundreisen untersucht werden müssen, sind es bei 20 Städten bereits ca. 100 Millionen Milliarden möglicher Rundreisen – unter der Annahme, dass jede Stadt mit jeder anderen durch eine Straße verbunden ist. Da die übrigen Städte (außer dem identischen Start- und Zielort) im Prinzip beliebig zu einer Rundreise kombiniert werden können, in der jede Stadt genau einmal besucht wird, hängt die Anzahl der möglichen Rundreisen von der Fakultät der Anzahl der übrigen Städte ab.
Dies führt dazu, dass man in den meisten Anwendungsfällen des Traveling Salesman Problem (TSP) auf Näherungsverfahren zurückgreift. Diese können allerdings nicht garantieren, dass die optimale Route gefunden wird und finden diese meist auch nicht. Dafür berechnen sie ihre Ergebnisse zum Teil in polynomialer (oder fast-polynomialer) Laufzeit.
Muss es immer perfekt sein? Unterschied zwischen “mathematischer” und “praktischer” Lösbarkeit
Ein möglicher Ansatz zur näherungsweisen Lösung ist, von jeder Stadt in die jeweils nächste Stadt zu fahren. Dies kann allerdings dazu führen, dass man später größere Entfernungen zurücklegen muss, um die noch übriggebliebenen Städte zu erreichen. Warum? Ein einfaches Beispiel, bei dem dieser Algorithmus scheitert, wie man sich leicht überlegt: Die Städte liegen allesamt im gleichen Abstand auf einer kreisförmigen Straße, bis auf eine einzige, die weit abseits westlich liegt. Die Start- und Zielstadt liegt genau im östlichsten Punkt des Kreises.
Ein Nachteil dieses Näherungsverfahrens ist also, dass der Blick auf das “große Ganze” fehlt. Ein anderes Verfahren zur Lösung des Traveling Salesman Problem wurde von Christofides [Christ] ersonnen: Dies bedient sich einer graphentheoretischen Herangehensweise, um eine Rundreise zu berechnen, die höchstens um einen bestimmten Faktor länger als die beste Lösung ist. Dieses Verfahren eignet sich somit besonders, wenn man unbedingt eine “gute” Lösung des TSP braucht.
Ein Vorbild für eine recht interessante Herangehensweise an das Problem des Handlungsreisenden liefert übrigens außerdem die Biologie: In der Biologie ist eine Spezies nicht immer an mathematisch perfekten Lösungen ihrer Probleme (Finden von Nahrung, Verteidigung gegen Feinde, etc.) interessiert, sondern der praktische Nutzen steht im Vordergrund. Daher muss die gefundene Lösung nicht optimal sein, sondern lediglich “gut genug”, damit das Individuum (in unserem Fall der Handlungsreisende) sein Ziel in der Praxis mit vertretbarem Aufwand erreicht. Der Reisende sollte also ankommen, ohne allzu große Umwege auf sich zu nehmen. Diese etwas aufgeweichte Variante des Problems des Handlungsreisenden lässt sich z.B. mit einem genetischen Algorithmus behandeln, wie z.B. in dem schönen Buch [Weick, S. 21-23] von Carsten Weicker dargestellt wird. Hierbei ist die Grundidee, dass eine zufällig ausgewählte Startmenge von möglichen Pfaden betrachtet wird und dann eine Art evolutionärer Auslese gestartet wird: Die kürzeren Pfade erhalten z.B. mit größerer Wahrscheinlichkeit die Möglichkeit, als Vorbilder für weitere Pfade (“Nachkommen”) in der nächsten Generation zu dienen. Auf diese Weise setzen sich mit fortschreitender Rechenzeit ähnlich wie im Laufe der Evolution die kürzeren Pfade durch. Wenn sich die Länge der Pfade über mehrere Generationen nicht mehr wesentlich ändert, wird die beste gefundene Lösung ausgegeben und das Programm abgebrochen. Auf diese Weise lässt sich die Rechenzeit für TSP in der Praxis im Vergleich zur Brute-Force-Methode wesentlich reduzieren. Auch wenn der gefundene Pfad schon allein aufgrund der gewählten Herangehensweise nicht den Anspruch hat, die mathematisch beste Lösung zu sein, so ist er doch häufig erstaunlich gut. Allerdings gibt es keine Garantie dafür, dass jedes TSP von diesem Algorithmus gelöst wird, da es auch hier auf die Startwerte ankommt.
Fazit
Eine Lösung des Traveling Salesman Problems gestaltet sich ohne Näherungsverfahren ab einer gewissen Anzahl von Städten in der Regel als schwierig. Dennoch oder vielleicht auch gerade aus diesem Grund ist es nach wie vor für viele Informatik-Begeisterte in Theorie und Praxis eine der faszinierendsten NP-vollständigen Problemstellungen.
Literatur:
[Weick]: Carsten Weicker (2007). Evolutionäre Algorithmen. Wiesbaden: Teubner Verlag
[Christ]: Nicos Christofides (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388. Pittsburg, USA: Grad. School of Industrial Administration, Carnegie Mellon University.