Algorithmen & Komplexität
Das Traveling Salesman Problem
Lernziele dieser Lektion
- Das Traveling Salesman Problem (TSP) beschreiben können
- Verstehen, warum die Anzahl möglicher Routen mit der Städtezahl explodiert
- Die Nearest-Neighbor-Heuristik als Lösungsansatz erklären können
- Den Unterschied zwischen einer optimalen und einer heuristischen Lösung verstehen
Was ist das Traveling Salesman Problem?
Das Traveling Salesman Problem (TSP, deutsch: Problem des Handlungsreisenden) ist eines der bekanntesten Optimierungsprobleme der Informatik – und ein perfektes Beispiel, um Komplexität und Heuristik zu veranschaulichen.
Die Aufgabe
Gegeben: Eine Liste von Städten und die Entfernung zwischen jedem Städte-Paar.
Frage: Wie kann man die kürzeste Strecke finden, die jede Stadt genau einmal besucht und zum Startpunkt zurückkehrt?
Bedingung: Jede Stadt darf dabei nur einmal besucht werden.
Warum ist das so schwer?
Das Problem klingt einfach, aber die Anzahl der möglichen Routen wächst explosionsartig mit der Zahl der Städte:
Beispiel mit 3 Städten (Wien, Graz, Salzburg)
Bei 3 Städten mit Start und Ziel in Wien gibt es nur 2 mögliche Reiserouten:
- Wien → Graz → Salzburg → Wien
- Wien → Salzburg → Graz → Wien
Das ist noch leicht per Hand lösbar.
Beispiel mit 4 Städten (Wien, Graz, Salzburg, Linz)
Bei 4 Städten steigt die Zahl bereits auf 6 mögliche Routen. Immer noch überschaubar.
Das exponentielle Wachstum
Aber die Zahlen explodieren schnell:
| Anzahl Städte | Mögliche Routen |
|---|---|
| 3 | 2 |
| 4 | 6 |
| 6 | 120 |
| 10 | über 300.000 |
| 20 | über 60 Billiarden |
| 50 | Mehr als Atome im Universum! |
Die Formel lautet: (n-1)! / 2 mögliche Routen, wobei n die Anzahl der Städte ist. Dieses explosive Wachstum macht es unmöglich, alle Möglichkeiten durchzuprobieren (Brute Force) – selbst für die schnellsten Computer der Welt.
Dies ist nur ein kurzer Auszug. Die vollständige Lektion mit interaktiven Übungen und Lernfortschritts-Tracking gibt es nach Einlösung eines Einschreibeschlüssels.