Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Rundreiseproblem 
(nach Breier, N.: Grenzen des Computereinsatzes. Teil 1. In LogIn 10 (1990) Heft 3 und Herms, A.: Genetische Algorithmen. Teil 3: Das Rundreiseproblem. In LogIn Nr. 127 (2004), S. 58ff)


Grundproblem und Beispiel
(Einführung: http://elib.zib.de/pub/UserHome/Groetschel/Spektrum/index2.html)

Ein Handlungsreisender soll, ausgehend von einer Stadt, weitere Städte (n-1-Stück) genau einmal durchreisen und am Ende wieder in die Ausgangsstadt zurückkehren. Gesucht ist die Reihenfolge, in der der Handlungsreisende die n Städte besuchen muss, damit die Kosten der Reise (z. B. gefahrene Strecke) minimal ist.

In Analogie zum Tanzpaarungsproblem werden zunächst die Kosten für die Reise von einer Stadt zu einer anderen Stadt in Form einer Matrix erfasst.

Beispiele: In den Beispielen wurde jeweils die zufahrenden Straßenkilometer eingetragen. Beispiel 2 zeigt, dass die Matrix nicht symmetrisch sein muss, da es z. B. durch Einbahnstraßen unterschiedliche Weglängen zwischen A und B gegeben kann. 

Beispiel 1   Astadt Bstadt Cstadt DStadt EStadt             Beispiel 2   Astadt Bstadt Cstadt DStadt EStadt
  Astatd 0 145 41 79 65     Astadt 7 4 5 3
  Bstadt 145 0 170 221 144     Bstadt 4 7 9 4
  Cstadt 41 170 0 52 47     Cstadt 6 3 4 7
Dstadt 79 221 52 0 96 Dstadt 2 6 4 12
Estadt 65 144 47 96 0 EStatst 8 5 5 3

Im Beispiel 1sind mögliche Routen, wenn stets in Astadt begonnen wird: 
- Astadt Dstadt Estadt Bstadt Cstadt Astadt (Kosten: 530) 
- Astadt Cstadt Dstadt Estadt Bstadt Astadt (Kosten: 478)

Im Beispiel 2 ist die günstigste Route, wenn in Astadt begonnen wird:
- Astadt CStadt Bstadt Estadt Dstadt Astadt (Kosten: 16)

exakte Lösung

Wie schon beim Tanzpaarungsproblem besteht die offensichtlich einfachste Lösung in der Erzeugung aller möglichen  Rundreisen, wobei am Ende die kostengünstigste gewählt wird. Da stets die erste Stadt konstant bleibt, beträgt die Anzahl der Permutationen bei n Städten gerade (n-1)!

Beispielimplementation in Java (Quelltext)

Laufzeitanalyse und Ordnung des Algorithmus:

Die Erzeugung aller möglichen Rundreisen benötigt eine Zeitordnung von O(n!). Mit anderen Worten: dieser Algorithmus ist für größere n ungeeignet!

Ein polynomialer Algorithmus

Wenn hier ein polynomialer Algorithmus für das TSP stehen würde, so könnte ich mich auf die faule Haut legen und eine Menge Geld verdienen. Es gibt bis zum heutigen Tage keinen solchen Algorithmus. Man sagt auch: das TSP ist NP-vollständig und meint damit, dass es zu den schwierigsten Problemen der Informatik gehört (siehe Kapitel P-NP-Problem)

Näherungslösungen 

Da man nicht unendlich viel Zeit hat und TSP durchaus praxisrelevant sind, müssen Algorithmen entwickelt werden, die das Problem näherungsweise lösen können.

Eine mögliche Variante werden mit dem Tool GraphBench vorgestellt und visualisiert.



zur Startseite
© Tino Hempel 1997 - 2005 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.