Travelling-Salesman-Problem

Travelling-Salesman-Problem

 aufwärts

Das Travelling-Salesman-Problem (TSP) oder Problem des Handlungsreisenden besteht darin, dass ein Handlungsreisender 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 graphentheoretischen Formalisierung entsprechen die Städte den Knoten eines ungerichteten Graphen G = (V, E). Der Graph ist vollständig verbunden, d.h. zwischen je zwei verschiedenen Knoten gibt es eine Kante, und er ist mit einer Kantengewichtung w : E Pfeil nach rechts reelle Zahlen versehen. Die Kantengewichte 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 Kantengewichte 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öglichkeiten, beginnend bei einer bestimmten Stadt alle anderen n-1 Städte zu besuchen und wieder zur Ausgangsstadt zurückzukehren – zu viele, um alle durchzuprobieren. 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(n3). Für das Travelling-Salesman-Problem aber gibt es wahrscheinlich keinen Algorithmus mit einer Komplexität von O(nk) (polynomielle Komplexität). Dies ist überraschend, denn das Problem sieht harmlos aus und unterscheidet sich scheinbar kaum etwa vom Kürzeste-Wege-Problem.

Es stellt sich daher die Frage nach Annäherungsverfahren, die zwar nicht unbedingt die beste Lösung finden, aber dieser sehr nahe kommen. Als erstes wird ein Verfahren mit polynomieller 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 selbstorganisierende Karte, die im Anschluss daran dargestellt werden.


1)  Kennzeichnend 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   Datenschutz   ©   Created: 16.05.2006   Updated: 04.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
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