Travelling-Salesman-Problem

Travelling-Salesman-Problem

 aufwärts

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 Pfeil nach rechts reelle Zahlen 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öglicher­weise 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(n3). Für das Travelling-Salesman-Problem aber gibt es wahr­scheinlich keinen Algorithmus mit einer Komplexität von O(nk) (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 Verfahren1) angewendet, wie etwa die Verfahren Simulated Annealing oder selbst­organisierende Karte, die im Anschluss daran dargestellt werden.


1)  Kenn­zeichnend für diese Verfahren ist, dass sie ziemlich schnell ziemlich gute Lösungen finden, wobei jedoch "ziemlich" nicht genau quantifizierbar ist.

 

Weiter:  [Faktor-2-Annäherung]   oder up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 16.05.2006   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik