TSP-Metaheuristiken live
Über diese App
Bis zu 500 Städte in der Ebene, im Raum oder auf dem Globus mit echten Weltstädten: neun Startverfahren vom Nächsten Nachbarn bis zur Hilbertkurve, 2-opt, Or-opt und 3-opt bis ins lokale Optimum, dann Simulated Annealing, Tabusuche, genetischer Algorithmus, Ameisenkolonie, iterierte lokale Suche, Zerstören & Reparieren und elastisches Netz. Jeder Zug ist sichtbar, der Verlauf misst die Tour an der Held-Karp-Schranke. Eigene Städte setzen und löschen.
Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.
Worum es geht
Beim Rundreiseproblem (Traveling Salesman Problem, TSP) sucht man die kürzeste Tour, die jede Stadt genau einmal besucht und zurückkehrt. Bei n Städten gibt es (n − 1)!/2 Touren, alle durchzuprobieren ist schon bei wenigen Dutzend Städten unmöglich. In der Praxis baut man darum zuerst schnell eine Startlösung und verbessert sie mit lokalen Zügen wie 2-opt, bis kein Zug mehr hilft. Dieses lokale Optimum ist meist nicht das globale. Metaheuristiken wie Simulated Annealing, Tabusuche, genetische Algorithmen oder Ameisenkolonien kommen aus solchen Tälern wieder heraus.
Was die App zeigt
Bis zu 500 Städte auf einer Karte, frei im Raum oder auf einem Globus mit echten Weltstädten, wo die Kanten Großkreisbögen sind. Neun Startverfahren, vom Nächsten Nachbarn über Einfügeverfahren und den Spannbaum bis zur Hilbertkurve, bauen ihre Tour sichtbar Schritt für Schritt. 2-opt, Or-opt und 3-opt zeigen jeden Zug: entfernte Kanten gestrichelt, neue farbig. Sieben Metaheuristiken laufen live: Temperatur beim Annealing, verbotene Kanten bei der Tabusuche, die Population beim genetischen Algorithmus, Pheromonspuren der Ameisen, Kicks der iterierten lokalen Suche, Zerstören & Reparieren und ein elastisches Netz. Der Verlauf misst jede Tour an der unteren Schranke nach Held und Karp.
Selbst ausprobieren
Lass 2-opt bis zum Ende laufen: Die Tour hat dann keine Kreuzung mehr und liegt trotzdem einige Prozent über der Schranke. Starte danach Simulated Annealing und beobachte, wie die Länge erst steigt und beim Abkühlen tiefer fällt als vorher. Setze in der Ebene eigene Städte oder lösche welche, die laufende Tour passt sich sofort an. Mit dem Tempo-Regler geht es Zug für Zug oder zehntausende Schritte pro Sekunde. Die Lupe erklärt jedes Teil der Szene.
Häufige Fragen
- Was ist 2-opt beim Rundreiseproblem?
- 2-opt ist ein lokaler Verbesserungszug: Zwei Kanten der Tour werden entfernt und über Kreuz neu verbunden, das Teilstück dazwischen wird dabei in umgekehrter Richtung durchlaufen. Der Zug wird nur ausgeführt, wenn er die Tour verkürzt. 2-opt endet, wenn kein solcher Zug mehr existiert; die Tour hat dann in der Ebene keine Kreuzungen mehr, ist aber im Allgemeinen nicht optimal.
- Wie entkommt Simulated Annealing einem lokalen Optimum?
- Simulated Annealing nimmt auch Züge an, die die Tour verlängern, und zwar mit der Wahrscheinlichkeit e hoch minus Verschlechterung durch Temperatur. Zu Beginn ist die Temperatur hoch und viele Verschlechterungen werden angenommen; sie sinkt langsam, bis fast nur noch Verbesserungen durchgehen. So kann die Suche Täler verlassen, bevor sie sich festlegt.
- Woran misst man die Güte einer TSP-Lösung ohne das Optimum?
- An einer unteren Schranke. Die Held-Karp-Schranke berechnet 1-Bäume (minimaler Spannbaum plus zwei Kanten an einer Stadt) und hebt sie mit Gewichten an den Städten an. Keine Tour kann kürzer sein; liegt eine Tour 3 % darüber, ist sie höchstens 3 % schlechter als das Optimum.
- Kann ich in der App eigene Städte setzen?
- Ja, in der Ebene: Städte lassen sich verschieben, hinzufügen und löschen. Eine neue Stadt wird an der billigsten Stelle in die laufende Tour eingefügt, ein laufendes Verfahren macht mit der geänderten Karte weiter.
Fach: Operations Research: DP & Heuristiken
Mehr aus Operations Research: DP & Heuristiken
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps