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 direkte 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:

Fünf verschiedene Touren für fünf Städte
Autor: Ulrich Helmich, Lizenz: siehe Seitenende

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

Noch weitere vier verschiedene Touren für fünf Städte
Autor: Ulrich Helmich, Lizenz: siehe Seitenende

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

Darstellung aller möglichen Touren bei fünf Städten
Autor: Ulrich Helmich, Lizenz: siehe Seitenende

Systematisierung

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

Je mehr Städte, desto mehr mögliche Touren, Teil 1
Autor: Ulrich Helmich, Lizenz: siehe Seitenende

Je mehr Städte, desto mehr mögliche Touren, Teil 2
Autor: Ulrich Helmich, Lizenz: siehe Seitenende

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 nicht 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:

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.

Eine der bekanntesten und am leichtesten zu implementierende Methode, um eine "vernünftig kurze" Rundreise zu berechnen, ist die "Nearest neighbour"-Methode, die auf der nächsten Seite erläutert wird.