Das Problem des Handlungsreisenden erklärt
Geben Sie einem Handlungsreisenden eine Liste von Städten und fragen Sie nach der kürzesten Reise, die jede davon einmal besucht und nach Hause zurückführt. Jeder kann eine vorgeschlagene Route prüfen, und jeder kann eine schlechte nach Augenmaß verbessern, doch niemand kennt eine schnelle Methode, die immer die beste findet. Das Problem des Handlungsreisenden ist zum Standardbeispiel eines schweren Problems geworden, und die Methoden, die man dafür erfunden hat, planen heute Auslieferungen, bohren Leiterplatten und setzen Genome zusammen.
Das Problem
Eine Tour besucht jede Stadt genau einmal und endet dort, wo sie begonnen hat; ihre Länge ist die Summe der Entfernungen auf dem Weg. Die Aufgabe besteht darin, die kürzeste Tour zu finden. In der Version hier sind die Entfernungen gerade Linien auf einer Karte, der Weg von A nach C ist also nie länger als der Weg über B: Das ist das metrische Problem des Handlungsreisenden. Das Rätsel wurde um 1930 vom Mathematiker Karl Menger diskutiert, und der Name setzte sich in den folgenden Jahrzehnten durch, als sich Mathematiker der RAND Corporation damit beschäftigten.
Die Explosion der Routen
Legen Sie die Startstadt fest. Für die nächste Stadt gibt es n − 1 Möglichkeiten, für die darauf folgende n − 2 und so weiter, und jede Tour kann in zwei Richtungen gefahren werden, also gibt es (n − 1)! / 2 Touren. Bei 10 Städten sind das 181.440, für einen Computer ein Leichtes. Bei 20 sind es etwa 6 × 10¹⁶, und bei 70 übersteigt die Zahl die der Atome im beobachtbaren Universum. Schnellere Computer helfen wenig: Jede zusätzliche Stadt vervielfacht den Aufwand etwa um den Faktor n.
NP-schwer
1972 zeigte Richard Karp, dass die Frage, ob ein Graph eine Rundreise durch alle Knoten besitzt, einen Hamiltonkreis, zu einer Familie NP-vollständiger Probleme gehört, die alle gleich schwer sind. Das Problem des Handlungsreisenden enthält diese Frage, also ist es NP-schwer. Eine schnelle Methode dafür würde schnelle Methoden für Tausende andere Probleme in Terminplanung, Logistik und Kryptographie liefern. Ob es eine solche Methode gibt, ist die Frage P gegen NP, eines der Millennium-Probleme.
Eine exakte Methode: Held–Karp
1962 nutzten Michael Held und Richard Karp, und unabhängig von ihnen Richard Bellman, die dynamische Programmierung. Für jede Menge S von Städten und jede Stadt j in S berechnet man den kürzesten Weg, der in der Heimatstadt beginnt, genau die Städte von S besucht und in j endet. Jeder Wert ergibt sich aus den Werten für S ohne j, sodass die Tabelle von kleinen zu großen Mengen gefüllt wird und am Ende die kürzeste Tour herauskommt. Das braucht etwa n² · 2ⁿ Schritte statt n!, was bei 30 Städten den Unterschied zwischen Minuten und dem Alter des Universums ausmacht, wächst aber immer noch exponentiell.
Schnelle Konstruktionsregeln
Der nächste Nachbar fährt immer zur nächstgelegenen noch nicht besuchten Stadt. Das ist einfach und schnell, lässt aber oft einige Städte zurück, die am Ende mit langen Umwegen eingesammelt werden müssen, sodass seine Touren typischerweise etwa 25 % länger als die beste sind. Einfügeverfahren halten stattdessen eine geschlossene Schleife und fügen die übrigen Städte einzeln dort ein, wo sie am wenigsten kosten. 1976 fand Nicos Christofides eine Konstruktion, die auf jeder metrischen Karte garantiert höchstens das 1,5-Fache des Optimums ergibt, eine Schranke, die über vierzig Jahre lang nahezu ungeschlagen blieb.
Eine Tour verbessern: 2-opt
Die lokale Suche beginnt mit einer beliebigen Tour und nimmt immer wieder kleine Änderungen vor, die sie verkürzen. Der klassische Zug, 2-opt, entfernt zwei Kanten und verbindet die beiden Teile andersherum neu, was das Stück dazwischen umkehrt. Wann immer sich zwei Kanten kreuzen, löst dieser Zug die Kreuzung auf und spart Länge, sodass eine Tour, die 2-opt nicht verbessern kann, sich nie selbst kreuzt. Auf zufälligen Karten liegen 2-opt-Touren typischerweise etwa 5 % über dem Optimum. Stärkere Züge, die drei Kanten tauschen, oder das Verfahren mit variabler Tiefe von Lin und Kernighan aus dem Jahr 1973 kommen noch näher heran.
Simulierte Abkühlung
Die lokale Suche kann in einer Tour stecken bleiben, in der jeder einzelne Zug sie verschlechtert, obwohl es eine viel bessere Tour gibt. Die simulierte Abkühlung, 1983 von Scott Kirkpatrick, Daniel Gelatt und Mario Vecchi auf dieses Problem angewandt, borgt aus der Metallurgie: Sie akzeptiert einen schlechteren Zug mit einer Wahrscheinlichkeit, die von einer Temperatur abhängt, die anfangs hoch ist und langsam gesenkt wird. Anfangs wandert die Tour frei umher; am Ende werden nur noch Verbesserungen akzeptiert. Bei ausreichend langsamer Abkühlung findet sie zuverlässig sehr gute Touren.
Selbst ausprobieren
Öffnen Sie die Demo zum Problem des Handlungsreisenden, um bis zu 200 Städte zufällig, auf einem Kreis, in Gruppen, auf einem Gitter oder dort zu setzen, wo Sie klicken. Sehen Sie zu, wie der nächste Nachbar seine letzten Städte zurücklässt, wie 2-opt jede Kreuzung entwirrt, verfolgen Sie die Temperatur der simulierten Abkühlung beim Abkühlen, und lassen Sie Held–Karp die kürzeste Tour für bis zu 12 Städte beweisen. Alle vergleichen lässt jede Methode auf derselben Karte laufen und zeigt, wie weit jede Tour über der kürzesten gefundenen liegt.
Häufig gestellte Fragen
Wo wird das Problem des Handlungsreisenden eingesetzt?
Überall dort, wo etwas viele Orte in einer effizienten Reihenfolge anfahren muss: Liefer- und Abholrouten, der Weg eines Bohrers oder Lasers über eine Leiterplatte, die Reihenfolge, in der ein Teleskop Sterne beobachtet, Kommissionierreihenfolgen in einem Lager und, mit anderen Entfernungen, die Reihenfolge der Fragmente beim Zusammensetzen einer DNA-Sequenz.
Was ist das größte jemals exakt gelöste Problem?
1954 bewiesen George Dantzig, Ray Fulkerson und Selmer Johnson die kürzeste Tour durch 49 Städte in den Vereinigten Staaten. 2006 bewies der Löser Concorde von David Applegate, Robert Bixby, Vašek Chvátal und William Cook nach Jahren an Rechenzeit die optimale Tour durch 85.900 Punkte aus einem Chipdesign.
Ist die kürzeste Tour immer frei von Kreuzungen?
Ja, auf einer ebenen Karte mit Luftlinienentfernungen. Würden sich zwei Kanten kreuzen, würde ihr Tausch gegen zwei Seiten des Vierecks, das sie bilden, die Tour verkürzen; eine Tour mit Kreuzung kann also nicht die kürzeste sein.
Liefern die Heuristiken jedes Mal dieselbe Tour?
Nächster Nachbar, billigste Einfügung und 2-opt sind, wie sie hier verwendet werden, deterministisch: Auf denselben Städten liefern sie dieselbe Tour. Die simulierte Abkühlung beginnt mit einer zufälligen Tour und macht zufällige Züge, daher können zwei Durchläufe mit verschiedenen Touren enden, meist von fast derselben Länge.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Die Demo zum Problem des Handlungsreisenden öffnen