Travelling Salesman: Algorithmen im Wettstreit
NP-schwer in der Praxis — drei Heuristiken im direkten Vergleich
Was ist das Travelling-Salesman-Problem?
Stell dir einen Paketboten vor, der morgens 20 Adressen abklappern und abends wieder am Depot stehen muss. Welche Reihenfolge spart am meisten Sprit?
Klingt simpel — ist es aber nicht. Schon bei einer Handvoll Stopps gibt es mehr mögliche Routen, als ein Mensch je durchprobieren könnte. Genau diese Frage stellt das Travelling-Salesman-Problem (TSP).
Analogie:
Stell dir einen Paketboten vor, der morgens 20 Adressen abklappern und abends wieder am Depot stehen muss. Welche Reihenfolge spart am meisten Sprit?
Klingt simpel — ist es aber nicht. Schon bei einer Handvoll Stopps gibt es mehr mögliche Routen, als ein Mensch je durchprobieren könnte. Genau diese Frage stellt das Travelling-Salesman-Problem (TSP).
Definition:
Formal: Finde die kürzeste geschlossene Rundreise, die jede von n Städten genau einmal besucht und zum Start zurückkehrt. TSP ist NP-schwer — es ist kein Verfahren bekannt, das für beliebig große Instanzen in vertretbarer Zeit garantiert die optimale Lösung findet.
Die Zahl möglicher Touren wächst mit (n-1)!/2. Deshalb setzt man in der Praxis auf Heuristiken: Verfahren, die schnell sehr gute — wenn auch nicht beweisbar perfekte — Lösungen liefern.
Warum ist das so schwer?
Der Trick beim TSP ist nicht das Rechnen einer Tour-Länge — das geht blitzschnell. Das Problem ist die kombinatorische Explosion: Die Anzahl möglicher Touren wächst schneller als alles, was unsere Intuition erfassen kann.
| Städte | Mögliche Touren | Brute-Force-Zeit |
|---|---|---|
| 5 | 12 | den Bruchteil einer Sekunde |
| 10 | 181.440 | den Bruchteil einer Sekunde |
| 15 | 4.4 × 10^10 | 44 Sekunden |
| 20 | 6.1 × 10^16 | 2 Jahre |
| 25 | 3.1 × 10^23 | 9.8 × 10^6 Jahre |
Genau hier setzen Heuristiken an: Statt alles durchzuprobieren, suchen sie clever — und finden in Sekunden Routen, die fast optimal sind.
Die drei Strategien
Drei sehr unterschiedliche Denkweisen treten gegeneinander an. Beobachte im Demo, wie sie sich verhalten:
Nimmt immer den nächstgelegenen, noch nicht besuchten Ort. Blitzschnell und oft brauchbar — läuft sich aber leicht in eine Sackgasse, weil es nie zurückschaut. Eine reine One-Shot-Lösung.
Simulated Annealing imitiert das langsame Abkühlen von Metall: Solange es heiß ist, akzeptiert es auch mal eine schlechtere Route, um aus lokalen Tälern zu entkommen. Je kühler, desto wählerischer wird es.
Der Genetische Algorithmus hält eine ganze Population von Routen. Die besten werden gekreuzt und mutiert — wie in der Evolution setzen sich über Generationen die kürzesten Touren durch.
Interaktive Demo
Was die Karte zeigt
Punkte auf einer Karte, verbunden zu einer Rundreise. Aus einem wirren Zickzack wird Schritt für Schritt eine kurze, glatte Schleife um alle Punkte.
- Was du siehst
- Eine Karte mit gestreuten Punkten — die Orte. Ein blasses Netz deutet an, dass jeder Ort mit jedem verbunden werden könnte. Darüber liegt die aktuelle Rundreise als farbige Linie, die alle Punkte zu einer geschlossenen Schleife verbindet.
- Was passiert
- Anfangs schlägt die Linie kreuz und quer über die Karte und überkreuzt sich oft. Während der Optimierung lösen sich die Überkreuzungen, die Route wird glatter und legt sich fast rund um alle Punkte. Mehrere Verfahren treten gleichzeitig an und zeichnen jeweils ihre eigene farbige Route.
- Was du tun kannst
- Wähle eine Region oder setze eigene Punkte auf die Karte. Starte die Verfahren, gehe Schritt für Schritt weiter oder pausiere. Zeichne mit Klicks deine eigene Rundreise und tritt gegen die Verfahren an. Über die Auswahl blendest du einzelne Verfahren ein oder aus, per Zoom und Ziehen bewegst du die Karte.
- Worauf du achtest
- Es gibt unfassbar viele mögliche Rundreisen — viel zu viele, um alle durchzuprobieren. Achte darauf, wie die Verfahren trotzdem geschickt eine kurze Route finden: Jede verschwindende Überkreuzung ist ein Stück gesparter Weg.
Steuerung
Klicke Städte an, um auch deine eigene Route einzuzeichnen und gegen die Algorithmen anzutreten. Klick auf leere Fläche setzt eine neue Stadt.
Was hat das mit KI zu tun?
TSP ist der Prototyp der kombinatorischen Optimierung — und genau diese Klasse von Problemen taucht in der KI überall auf, wo aus astronomisch vielen Möglichkeiten die beste ausgewählt werden muss.
Die Kernidee bleibt gleich: Wenn vollständiges Durchsuchen unmöglich ist, suchen wir clever. Simulated Annealing und Genetische Algorithmen sind universelle Werkzeuge weit über das TSP hinaus.
Traveling Salesman Problem — der Algorithmus
Das berühmteste Tourenproblem
Ein Handlungsreisender soll jede Stadt genau einmal besuchen und zum Start zurückkehren — auf der kürzesten Rundtour. Das klingt harmlos, ist aber eines der meistuntersuchten Probleme der Informatik. Dieselbe Struktur steckt in Paketrouten, im Bohren von Leiterplatten, in der Steuerung von Teleskopen und sogar in der Genom-Sequenzierung.
Warum es so schwer ist
Bei n Städten gibt es (n−1)!/2 verschiedene Rundtouren. Bei 10 Städten sind das 181.440 — machbar. Bei 20 Städten schon rund 6 × 10^16, mehr als jeder Rechner sinnvoll durchprobieren kann. Formal präzise: Die Entscheidungsvariante des TSP (gibt es eine Tour kürzer als L?) ist NP-vollständig, die Optimierungsvariante (finde die kürzeste Tour) ist NP-schwer. Ein Algorithmus, der jede Instanz in Polynomialzeit exakt löst, ist nicht bekannt — und existiert genau dann, wenn P = NP gilt.
Drei Strategien im Rennen
Die Demo lässt drei grundverschiedene Heuristiken gegeneinander antreten:
- Nearest Neighbor (gierig): Geh immer zur nächstgelegenen unbesuchten Stadt. Blitzschnell fertig, aber die letzten Verbindungen werden oft teuer — typisch 10 bis 25 Prozent über dem Optimum.
- Simulated Annealing: Startet mit einer Zufallstour und verändert sie lokal (2-opt: ein Teilstück umdrehen). Verschlechterungen werden bei hoher Temperatur manchmal akzeptiert — so entkommt die Suche lokalen Minima. Mit sinkender Temperatur friert die Tour ein.
- Genetischer Algorithmus: Eine ganze Population von Touren entwickelt sich über Generationen weiter — Turnier-Auswahl, Order-Crossover, Mutation. Die beste Tour überlebt garantiert (Elitismus).
- Held-Karp (Referenz): Exaktes Optimum per dynamischer Programmierung in O(2^n · n²) — in der Demo nur bis 12 Städte berechenbar. Genau deshalb kannst du dort sehen, wie nah die Heuristiken wirklich herankommen.
Keine Garantie — und trotzdem nützlich
Alle drei Verfahren sind Heuristiken: Sie liefern meist gute, aber keine garantiert optimale Lösung. Simulated Annealing und der Genetische Algorithmus sind zudem stochastisch — zwei Läufe können unterschiedlich enden. Für das metrische TSP gibt es Approximationsalgorithmen mit beweisbarer Schranke (Christofides 1976: höchstens das 1,5-Fache des Optimums), doch in der Praxis schlagen gute Heuristiken diese Garantie deutlich.
Spiele mit der Demo! Zieh den Städte-Regler hoch und sieh der Zahl der Touren beim Explodieren zu. Lass die Verfahren auf einer Karte mit höchstens 12 Städten rennen — dann kennt die Demo das exakte Optimum als Ziellinie. Dreh die Abkühlrate hoch oder die Mutationsrate runter und beobachte, wer gewinnt.
1832: Ein Handbuch für Handlungsreisende
Ein deutsches Büchlein mit dem Titel Der Handlungsreisende — wie er sein soll und was er zu thun hat beschreibt das Problem schon praktisch: Wer Kunden in vielen Städten besucht, sollte seine Route klug planen. Eine mathematische Behandlung gab es damals noch nicht.
1930er: Das Problem bekommt einen Namen
Der Wiener Mathematiker Karl Menger formulierte um 1930 das verwandte Botenproblem und bemerkte bereits, dass stures Durchprobieren aller Routen praktisch unmöglich ist — und dass die naheliegende Nächster-Nachbar-Regel nicht immer die kürzeste Tour liefert. An der Princeton University verbreitete sich in dieser Zeit der Name Traveling Salesman Problem, unter anderem durch Hassler Whitney.
1954: Dantzig, Fulkerson und Johnson
George Dantzig, Ray Fulkerson und Selmer Johnson lösten eine Instanz mit 49 US-Städten beweisbar optimal — mit linearer Programmierung und geschickt gewählten Schnittebenen. Ihre Methode ist bis heute die Grundlage aller exakten TSP-Löser.
1962–1976: Theorie wird scharf
1962 zeigten Michael Held und Richard Karp (und unabhängig Richard Bellman) den Held-Karp-Algorithmus: exaktes Optimum per dynamischer Programmierung in O(2^n · n²) — besser als brutales (n−1)!/2-Durchprobieren, aber immer noch exponentiell. 1972 bewies Karp die NP-Vollständigkeit des Hamiltonkreis-Problems, womit auch die TSP-Entscheidungsvariante NP-vollständig ist. 1976 lieferte Nicos Christofides den berühmten Approximationsalgorithmus mit Faktor 1,5 für das metrische TSP.
Heute: Concorde und Millionen Städte
Der Löser Concorde hat 2006 eine Instanz mit 85.900 Punkten (ein Chip-Layout) beweisbar optimal gelöst. Für Millionen-Städte-Instanzen liefern Heuristiken wie Lin-Kernighan Touren, die nachweislich nur Bruchteile eines Prozents über der bekannten unteren Schranke liegen. Das TSP bleibt der Prüfstand, an dem neue Optimierungsideen gemessen werden.
1
# Traveling Salesman Problem — drei Strategien im Wettrennen
2
# Gesucht: kürzeste Rundtour durch alle Städte, zurück zum Start
3
# Vorsicht: (n-1)!/2 mögliche Touren — bei 20 Städten ~ 6 × 10^16
4
5
funktion tsp_wettrennen(staedte):
6
# ---- Strategie 1: Nearest Neighbor (gierig) ----
7
tour = [startstadt]
8
solange es unbesuchte Städte gibt:
9
letzte = letzte Stadt der tour
10
naechste = unbesuchte Stadt mit kleinster distanz(letzte, stadt)
11
hänge naechste an tour an
12
greedy_beste = laenge(tour) # blitzschnell — aber selten optimal
13
14
# ---- Strategie 2: Simulated Annealing ----
15
aktuell = zufällige Tour; T = 100 # Starttemperatur
16
wiederhole solange T > 0.001:
17
# Nachbar-Tour: Teilstück umdrehen (2-opt) oder zwei Städte tauschen
18
kandidat = zwei_opt(aktuell)
19
delta = laenge(kandidat) - laenge(aktuell)
20
# Verbesserung immer nehmen — Verschlechterung nur mit Glück
21
wenn delta < 0 oder zufall() < exp(-delta / T):
22
aktuell = kandidat
23
wenn laenge(aktuell) < sa_beste:
24
sa_beste = laenge(aktuell) # beste Tour immer merken
25
T = T * 0.995 # langsam abkühlen und einfrieren
26
27
# ---- Strategie 3: Genetischer Algorithmus ----
28
population = 50 zufällige Touren
29
wiederhole pro generation:
30
# Elitismus: die beste Tour überlebt garantiert
31
neue_population = [beste Tour der population]
32
solange neue_population nicht voll ist:
33
eltern1 = turnier_auswahl(population)
34
eltern2 = turnier_auswahl(population)
35
kind = mutiere(kreuze(eltern1, eltern2)) # Order-Crossover
36
füge kind zu neue_population hinzu
37
population = neue_population
38
wenn kürzeste Tour der population < ga_beste:
39
ga_beste = kürzeste Tour der population
40
41
# ---- Referenz: exaktes Optimum (nur für kleine n) ----
42
wenn anzahl(staedte) <= 12:
43
optimum = held_karp(staedte) # dynamische Programmierung, O(2^n · n²)
44
# bei großen n ist das exakte Optimum praktisch unerreichbar
45
46
return beste gefundene Tour
47
# Achtung: Heuristiken garantieren KEIN Optimum — nur gute Näherungen
🧨 Die kombinatorische Explosion
Bei n Städten gibt es (n−1)!/2 verschiedene Rundtouren. Zehn Städte: 181.440 Touren — noch durchprobierbar. Zwanzig Städte: rund 6 × 10^16 — selbst ein Rechner mit einer Milliarde Touren pro Sekunde bräuchte fast zwei Jahre. Alle Touren zu testen scheidet aus; wir brauchen klügere Strategien.
# Traveling Salesman Problem — drei Strategien im Wettrennen
# Gesucht: kürzeste Rundtour durch alle Städte, zurück zum Start
# Vorsicht: (n-1)!/2 mögliche Touren — bei 20 Städten ~ 6 × 10^16
🗺️ Städte und Tour-Raum
n Städte mit Distanzen — und (n−1)!/2 mögliche Rundtouren. Vollständiges Durchprobieren scheidet schon bei mittleren n aus.
🏃 Gieriger Start
Nearest Neighbor baut sofort eine erste Tour: immer zur nächsten unbesuchten Stadt. Schnell, aber selten optimal.
🌡️ Abkühlen und verbessern
Simulated Annealing verformt die Tour per 2-opt. Rückschritte sind anfangs erlaubt, mit sinkender Temperatur friert die Tour ein.
🧬 Population evolvieren
Der Genetische Algorithmus kombiniert gute Touren per Auswahl, Kreuzung und Mutation über viele Generationen.
🏁 Beste Tour
Die kürzeste gefundene Tour gewinnt das Rennen. Bis 12 Städte zeigt Held-Karp das exakte Optimum als Referenz — eine Garantie liefern die Heuristiken nicht.
Das Wichtigste in Kürze
- NP-schwer: Schon bei 20 Städten gibt es über 10^17 mögliche Touren — vollständiges Durchprobieren ist selbst für Supercomputer chancenlos.
- Heuristiken statt Optimum: Greedy, Simulated Annealing und Genetische Algorithmen finden in Sekunden sehr gute Routen — ohne zu garantieren, dass es die kürzeste ist.
- Jede Strategie tickt anders: Greedy nimmt gierig den nächsten Punkt, Simulated Annealing akzeptiert anfangs auch Umwege, der Genetische Algorithmus züchtet eine ganze Population von Routen.
- Überall in der KI: Dieselbe kombinatorische Optimierung steckt in Logistik, Chip-Design, Genom-Sequenzierung und der Hyperparameter-Suche neuronaler Netze.
Teste dein Wissen
Warum kann man das TSP für viele Städte nicht einfach durch Ausprobieren aller Touren lösen?
1. Warum kann man das TSP für viele Städte nicht einfach durch Ausprobieren aller Touren lösen?
- ☐ A) Weil die Anzahl möglicher Touren mit (n-1)!/2 explodiert
- ☐ B) Weil Computer keine Entfernungen berechnen können
- ☐ C) Weil die kürzeste Route immer mehrdeutig ist
- ☐ D) Weil es kein eindeutiges Startfeld gibt
2. Was macht Simulated Annealing, solange die Temperatur hoch ist?
- ☐ A) Es akzeptiert auch schlechtere Routen, um lokale Optima zu verlassen
- ☐ B) Es nimmt nur Verbesserungen an
- ☐ C) Es hält eine Population von Lösungen
- ☐ D) Es wählt immer den nächsten Nachbarn
3. Was ist der typische Schwachpunkt der Greedy-Strategie (nächster Nachbar)?
- ☐ A) Sie schaut nie zurück und landet leicht in einer Sackgasse
- ☐ B) Sie ist viel zu langsam
- ☐ C) Sie braucht eine große Population
- ☐ D) Sie funktioniert nur bei Städten im Kreis
4. Garantieren diese Heuristiken die optimale Lösung?
- ☐ A) Nein — sie finden schnell sehr gute, aber nicht beweisbar optimale Touren
- ☐ B) Ja, immer das mathematische Optimum
- ☐ C) Nur Greedy garantiert das Optimum
- ☐ D) Nur bei weniger als 100 Städten
Verwandte Inhalte
Artikel
Der Weg ins Tal: Gradientenabstieg
Wie Gradientenabstieg in einer Landschaft mit Millionen Hügeln den Tiefpunkt findet — meistens.
Suche im Graphen — Die Anfänge
Graphsuche: das erste, was KI tatsächlich konnte — und immer noch nützlich ist.
Heuristiken & Pfadsuche: Von Dijkstra zu A*
Wie A* funktioniert — und warum Dijkstra ohne Heuristik schnell langweilig wird.
MinMax & Pruning
MinMax in der Praxis: rückwärts denken, vom schlimmsten Gegner ausgehen, abkürzen wo möglich.
Was ist ein Algorithmus?
Was Euklid, IKEA-Anleitungen und Google-Suche gemeinsam haben — alle drei sind Algorithmen.
Demo
Schwarmintelligenz (Boids)
Erlebe, wie aus drei simplen lokalen Regeln das komplexe Verhalten eines Vogelschwarms entsteht.
Evolution (Optimierung)
Interaktive Demonstration evolutionärer Optimierung mit Mutation, Selektion und Crossover-Operatoren
Gradient Descent
Interaktive Demo zum Verständnis von Gradient Descent: klicke einen Startpunkt auf die Verlustlandschaft, beobachte wie der Algorithmus ins Tal rollt, und experimentiere mit Lernrate und Optimierern.
MinMax (Spieltheorie)
Erlebe Spieltheorie hautnah: Spiele gegen eine KI und beobachte, wie sie den optimalen Zug berechnet.
Neuroevolution
Interaktive Demonstration von Neuroevolution: Neuronale Netze lernen durch evolutionäre Optimierung das Fahren auf einer Rennstrecke
Pathfinding (Graphsuche)
Interaktive Visualisierung von Wegfindungsalgorithmen wie A*, Dijkstra und mehr