Man sollte jetzt aber nicht denken, dieses Problem sei lediglich etwas für Mathematiker und Menschen mit Fernweh. Es gibt eine Vielzahl von Problemen, die sich direkt auf TSP zurückführen lassen:
Viele TSP sind symmetrisch. Ein symmetrisches TSP bedeutet, daß die Kosten der Strecke von Punkt A nach Punkt B identisch mit den Kosten von Punkt B nach Punkt A sind. In diesem Fall ist es also egal, in welcher Richtung die Städte besucht werden. Die Kosten in einer Richtung sind genau dieselben, wie in der anderen Richtung.
Für 2 Städte ist das TSP trivial. Da eine Stadt als Startpunkt festgelegt ist, gibt es nur eine mögliche Lösung. Im symmetrischen Fall ist das TSP auch bei 3 Städten trivial. Vom Startpunkt aus gibt es nur 2 mögliche Touren, die aber beide identische Kosten besitzen. Für ein Problem mit n Städten gibt es im asymmetrischen Fall (n-1)! mögliche Lösungen. Warum das so ist, kann ganz einfach erklärt werden: Man nimmt sich eine Stadt und hat anschließend (n-1) Möglichkeiten für die zweite Stadt, (n-2) Möglichkeiten für die dritte Stadt usw.
Im symmetrischen Fall ergeben sich ((n-1)!)/2 mögliche Lösungen. Ob nun symmetrisch oder asymmetrisch, mit wachsender Anzahl von Städten wird die Anzahl der Lösungen schnell sehr groß.
Wieviele Möglichkeiten ergeben sich im symmetrischen TSP aus den 17
Städten?
Bitte nicht nachrechnen, nur schätzen!
|
|
|
|
|---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996