Home > Informatik > Optimierungsprobleme

TSP, Brut force-Methode

Eine brutale Methode, die aber den kürzsten Weg findet.

Solange die Zahl der Städte klein ist, führt die dirkte Methode zum kürzesten Weg: Man probiert systematisch alle möglichen Touren aus und wählt dann die kürzeste.

Hier eine Demonstration für N = 5, also für fünf Städte:

Hier sehen wir vier verschiedene Touren für N=5, und im nächsten Bild noch vier weitere:

Es gibt noch eine ganze Reihe weiterer möglicher Touren, am besten stellt man alle Touren in Form eines Baums dar:

Systematisierung

Die Anzahl der möglichen Touren steigt mit der Zahl der Städte N an.

Hier sehen wir die Touren bzw. die zu berechnenden Strecken für N = 2, N = 3 und N = 4. Wenn man die "Richtung" der Touren berücksichtigt, kommt man bei 4 Städten auf 6 Touren. Der TSP-Algorithmus muss jedoch nur 3 Strecken berechnen, da sich je zwei Touren nur durch die "Richtung" der Rundreise unterscheiden.

Die folgende Tabelle zeigt die Anzahl der zu berechnenden Strecken S in Abhängigkeit von der Zahl der Städte:

N S
3 1
4 3
5 12
6 60
7 360
8 2.520
9 20.160
10 181.440

Man sieht dann, dass hier folgender Zusammenhang zwischen S und N gilt:

S = (N-1)! / 2

extrem hohe Rechenzeit

Angenommen, ein schneller Rechner kann 1 Million Berechnungen pro Sekunde anstellen, wenn er die kürzeste Rundreise berechnet. Das Problem mit 10 Städten hat er dann in 0,18 Sekunden gelöst. Für 11 Städte braucht er dann 10 mal so lange (N - 1 mal), also knapp 2 Sekunden. Für 12 Städte benötigt der Rechner dann schon 11 mal so lange, also 22 Sekunden, für 13 Städte 4,4 Minuten, für 14 Städte knapp eine Stunde, für 15 Städte 13 Stunden und für 16 Städte mehr als 8 Tage.

Sie sehen, wohin das führt? Die Rechenzeit steigt mit N nicht nur exponentiell, was schon schlimm wäre, sondern fakultativ. Selbst wenn der Rechner, von dem wir eben geredet haben, 100 mal so schnell wäre, so brächte er für 17 Städte immer noch 1,3 Tage, und für 18 Städte 22 Tage, wäre also im Grund nicht viel effektiver als der 100 mal so langsame Rechner.

Die Brute force-Methode, die alle möglichen Strecken berechnet und dann die kürzeste davon wählt, funktioniert also nur bei sehr kleinen Städtezahlen.

Daher hat man Algorithmen entwickelt, die nicht unbedingt die absolut kürzeste Strecke ermitteln, sondern eine "vernünftig" kurze Strecke, deren Rechenzeit dafür aber nicht so extrem fakultativ mit der Anzahl der Städte anwächst.

Das Traveling Salesman Problem ist eines der bekanntesten Optimierungsprobleme der Informatik. Algorithmen, die das TSP auf vernünftige Weise lösen, lassen sich auch für die Lösung vieler anderer ähnlicher Probleme einsetzen, zum Beispiel bei der Herstellung von Leiterplatten.