Travelling-Salesman-Problem

Das Travelling-Salesman-Problem (TSP) oder Problem des Handlungs­reisenden besteht darin, dass ein Handlungs­reisender eine Rundreise durch n Städte unternehmen und dabei einen möglichst kurzen Weg zurücklegen soll. Die Entfernungen zwischen den einzelnen Städten sind bekannt. Gefragt ist also nach der Reihenfolge, in der die Städte besucht werden müssen.

In einer graphen­theoretischen Formalisierung entsprechen die Städte den Knoten eines ungerichteten Graphen G = (V, E). Der Graph ist vollständig verbunden, d.h. zwischen je zwei ver­schiedenen Knoten gibt es eine Kante, und er ist mit einer Kanten­gewichtung w : E → ℝ versehen. Die Kanten­gewichte entsprechen den Entfernungen zwischen den betreffenden Städten. Eine Rundreise ist ein Kreis, der alle Knoten des Graphen durchläuft. Die Länge der Rundreise ist gleich der Summe der Kanten­gewichte des Kreises. Gesucht ist eine Rundreise minimaler Länge.

Travelling-Salesman-Problem

Eingabe:

Vollständig verbundener ungerichteter Graph mit Kantengewichtung

Ausgabe:

Rundreise minimaler Länge

Es gibt (n-1)! Möglich­keiten, beginnend bei einer bestimmten Stadt alle anderen n-1 Städte zu besuchen und wieder zur Ausgangs­stadt zurück­zukehren – zu viele, um alle durch­zuprobieren. Ein wesentlich schnelleres Verfahren, das weniger als exponentielle Komplexität hat, ist nicht bekannt und existiert möglicherweise auch nicht, denn TSP ist NP-vollständig.

Dies ist eine neue Situation – die anderen Algorithmen, die auf diesen Webseiten dargestellt sind, haben alle eine Komplexität von höchstens O(n³). Für das Travelling-Salesman-Problem aber gibt es wahr­scheinlich keinen Algorithmus mit einer Komplexität von O(n^k) (polynomielle Komplexität). Dies ist überraschend, denn das Problem sieht harmlos aus und unter­scheidet sich scheinbar kaum etwa vom Kürzeste-Wege-Problem.

Es stellt sich daher die Frage nach Annäherungs­verfahren, die zwar nicht unbedingt die beste Lösung finden, aber dieser sehr nahe kommen. Als erstes wird ein Verfahren mit poly­nomieller Komplexität angegeben, das für das metrische Travelling-Salesman-Problem eine Rundreise berechnet, die höchstens doppelt so lang ist wie die kürzeste Rundreise.

Meistens sind jedoch weitaus bessere Annäherungen an die optimale Lösung möglich. Hierzu werden sogenannte heuristische Verfahren¹) angewendet, wie etwa die Verfahren Simulated Annealing oder selbst­organisierende Karte, die im Anschluss daran dargestellt werden.