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.