- Tour
- Kürzeste gefundene
- Start
| Methode | Länge | Über der kürzesten | Schritte |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Problem des Handlungsreisenden
Ein Handlungsreisender muss jede Stadt einmal besuchen und nach Hause zurückkehren. In welcher Reihenfolge wird die Reise am kürzesten? Die Frage ist leicht gestellt, doch mit wachsender Zahl der Städte ist es hoffnungslos, sie durch Ausprobieren aller Reihenfolgen zu beantworten: Schon 30 Städte erlauben etwa 4,4 × 10³⁰ Rundreisen. Verteilen Sie Städte auf einer Karte oder klicken Sie eigene hinein und sehen Sie dann zu, wie schnelle Faustregeln, geschickte Verbesserungen und eine exakte Methode ihre Touren Schritt für Schritt aufbauen und wie nah die schnellen herankommen. Wählen Sie, wie die Städte angeordnet sind und wie viele es gibt, wählen Sie eine Methode und drücken Sie Lösen, um zuzusehen, wie sie Schritt für Schritt eine Rundreise aufbaut, oder Schritt, um jeweils einen Zug weiterzugehen. Klicken Sie auf die Karte, um eine Stadt hinzuzufügen, oder auf eine Stadt, um sie zu entfernen. Alle vergleichen lässt jede Methode auf denselben Städten laufen und zeigt, wie weit jede von der kürzesten gefundenen Tour entfernt ist. Die rote Stadt ist der Startpunkt der Reise.
Wie es funktioniert
- Wählen Sie eine Anordnung und die Anzahl der Städte, oder klicken Sie auf die Karte, um eigene zu setzen, und auf eine Stadt, um sie zu entfernen.
- Wählen Sie eine Methode und drücken Sie Lösen, um ihr Schritt für Schritt zuzusehen, oder Schritt, um jeweils einen Zug weiterzugehen.
- Drücken Sie Alle vergleichen, um jede Methode auf denselben Städten laufen zu lassen, und lesen Sie ab, wie weit jede Tour über der kürzesten gefundenen liegt.
Warum es schwer ist
Bei n Städten gibt es (n − 1)! / 2 verschiedene Rundreisen, denn es spielt keine Rolle, wo man beginnt oder in welcher Richtung man fährt. Das sind 12 bei 5 Städten, 181.440 bei 10 und etwa 6 × 10¹⁶ bei 20. Man kennt keine Methode, die für jede Karte die kürzeste Reise in einer Zeit findet, die nur wie eine Potenz von n wächst; das Problem ist NP-schwer. Die beste exakte Methode in dieser App, die dynamische Programmierung nach Held–Karp von 1962, braucht immer noch etwa n² · 2ⁿ Schritte und ist hier daher auf 12 Städte begrenzt.
Schnell zu guten Touren
In der Praxis findet man fast kürzeste Touren schnell. Der nächste Nachbar fährt immer zur nächstgelegenen unbesuchten Stadt und endet typischerweise etwa 25 % über der besten Tour. Die billigste Einfügung lässt eine Schleife wachsen und fügt jeweils die Stadt hinzu, die sie am wenigsten verlängert. 2-opt nimmt eine beliebige Tour und ersetzt immer wieder zwei Kanten durch zwei kürzere; das beseitigt jede Kreuzung und kommt meist bis auf etwa 5 % heran. Die simulierte Abkühlung macht zufällige 2-opt-Züge und akzeptiert, solange sie noch „heiß“ ist, auch einige, die die Tour verlängern, sodass sie aus Sackgassen herausklettern kann, bevor sie zur Ruhe kommt.
Häufig gestellte Fragen
Gibt es eine Formel für die kürzeste Route?
Nein. Die kürzeste Tour hängt von den genauen Positionen aller Städte ab, und keine bekannte Methode findet sie für jede Karte ohne einen Aufwand, der im schlimmsten Fall exponentiell wächst. Für einige hundert oder tausend Städte beweisen spezialisierte exakte Löser wie Concorde dennoch optimale Touren, indem sie lineare Optimierung mit geschicktem Beschneiden des Suchraums kombinieren; die größte bisher exakt gelöste Instanz hat 85.900 Punkte.
Warum beseitigt 2-opt jede Kreuzung?
Wenn sich zwei Kanten einer Tour kreuzen, bilden die vier Städte, die sie verbinden, ein Viereck, dessen Diagonalen die beiden Kanten sind. Sie durch zwei gegenüberliegende Seiten des Vierecks zu ersetzen, ist nach der Dreiecksungleichung immer kürzer und kehrt das Stück der Tour dazwischen um. 2-opt führt solche Tausche so lange durch, bis keiner mehr hilft, daher kreuzt sich seine fertige Tour nie selbst.
Was ist die Temperatur bei der simulierten Abkühlung?
Sie steuert, wie bereitwillig die Methode einen Zug akzeptiert, der die Tour verlängert. Ein Zug, der die Länge um d vergrößert, wird mit der Wahrscheinlichkeit e^(−d/T) akzeptiert. Bei hoher Temperatur T ist fast alles erlaubt, sodass die Tour einer schlechten Anordnung entkommen kann; sinkt T, wird die Methode gierig und kommt zur Ruhe. Der Name kommt vom langsamen Abkühlen von Metall, damit seine Atome eine energiearme Anordnung finden.
Warum ist die exakte Methode auf 12 Städte begrenzt?
Held–Karp speichert den kürzesten Weg für jede Teilmenge von Städten und jede mögliche letzte Stadt, also etwa n · 2ⁿ Zahlen, und berechnet jede mit n Vergleichen. Bei 12 Städten sind das einige hunderttausend Schritte, bei 25 Städten wären es Milliarden. Das ist immer noch enorm viel schneller, als alle (n − 1)! / 2 Touren auszuprobieren: Bei 12 Städten wären das fast 20 Millionen.
Wird etwas an einen Server gesendet?
Nein. Die Städte und alle fünf Methoden laufen in Ihrem Browser. Die Städte, die Sie hineinklicken, bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor