TSP Löser Online

Pseudocode

Für das Problem des Handlungsreisenden gibt es keinen schnellen exakten Algorithmus, daher ist die praktische Antwort zweistufig: schnell eine brauchbare Rundreise bauen und sie dann lokal verbessern, bis nichts mehr besser wird.

// Stufe 1: nächster Nachbar, baut eine Tour in O(n^2)
tour = [start]
solange eine Stadt unbesucht ist:
    nächste = unbesuchte Stadt am nächsten zu tour.letzte
    tour.anhängen(nächste)
tour.anhängen(start)            // Kreis schließen

// Stufe 2: 2-opt, entfernt Überkreuzungen
wiederhole bis keine Verbesserung mehr:
    für jedes Kantenpaar (a,b) und (c,d) der Tour:
        wenn dist(a,c) + dist(b,d) < dist(a,b) + dist(c,d):
            kehre das Tourstück zwischen b und c um

// Exakt, für kleines n: Held-Karp dynamische Programmierung
dp[S][j] = min über k in S\{j} von dp[S\{j}][k] + dist(k, j)

Der 2-opt-Zug lohnt sich geometrisch zu verstehen. Kreuzen sich zwei Kanten einer Tour, so verkürzt das Vertauschen ihrer Endpunkte samt Umkehren des Zwischenstücks die Tour stets, wegen der Dreiecksungleichung. 2-opt ist also buchstäblich das Herausziehen der Knoten aus einer Schnurschlaufe.

Durchgerechnetes Beispiel, Schritt für Schritt

Wende nächsten Nachbarn und danach 2-opt auf vier Städte an den Ecken eines Rechtecks an, wo die gierige Wahl nachweislich danebengehen kann.

Beispielgraph: Städte A(0,0), B(0,3), C(4,3), D(4,0). Distanzen: A-B 3, B-C 4, C-D 3, A-D 4, und beide Diagonalen A-C und B-D betragen 5.

1. Nächster Nachbar ab A. Die nächstgelegene Stadt zu A ist B mit 3. Weiter nach B.
2. Von B aus. Unbesucht sind C mit 4 und D mit 5. Nimm C.
3. Von C aus. Es bleibt nur D mit 3. Nimm sie und schließe dann mit 4 zurück nach A.
4. Gieriges Ergebnis. Die Tour A nach B nach C nach D nach A kostet 3 + 4 + 3 + 4 = 14. Hier ist sie zufällig optimal, also stören wir sie: angenommen, die Heuristik hätte A nach C nach B nach D nach A geliefert, mit Kosten 5 + 4 + 5 + 4 = 18, eine Tour mit sich kreuzenden Kanten.
5. 2-opt-Reparatur. Betrachte die Kanten A-C und B-D. Zusammen tragen sie derzeit 5 + 5 = 10 bei. Neu verbunden als A-B und C-D ergibt das 3 + 3 = 6, eine Verbesserung um 4, also kehre das Stück zwischen C und B um. Die Tour wird zu A nach B nach C nach D nach A mit Kosten 14, und kein weiterer 2-opt-Zug hilft.

Die optimale Tour ist der Rechteckumfang mit 14, nicht eine der Touren mit gekreuzten Diagonalen mit 18. Das ist die ganze Geschichte der TSP-Heuristiken im Kleinen: ein schneller konstruktiver Durchgang kommt nahe heran, und die lokale Suche entfernt die Überkreuzungen, die die gierige Wahl eingebracht hat.

Komplexität und woher sie kommt

Zeit: O(n^2) heuristisch, O(n^2 · 2^n) exakt · Speicher: O(n^2) heuristisch, O(n · 2^n) exakt

Nächster Nachbar durchsucht in jedem der n Schritte alle verbleibenden Städte, was O(n hoch 2) ergibt. Jeder 2-opt-Durchgang prüft alle O(n hoch 2) Kantenpaare und wiederholt sich, bis nichts mehr besser wird, was in der Praxis schnell ist, aber keine brauchbare Schranke im schlechtesten Fall hat. Held-Karp ist exakt und füllt eine Tabelle, indiziert nach Teilmenge und Endpunkt: es gibt 2 hoch n Teilmengen mal n Endpunkte, und jeder Eintrag kostet O(n), daher O(n hoch 2 mal 2 hoch n) Zeit und O(n mal 2 hoch n) Speicher. Das ist eine harte Grenze um n = 20 bis 25, denn 2 hoch 25 mal 25 übersteigt bereits eine Milliarde Tabelleneinträge. Rohe Gewalt über alle Permutationen ist mit O(n Fakultät) weit schlechter.

Wann Handlungsreisender-Problem passt und wann nicht

Die richtige Methode hängt fast vollständig davon ab, wie viele Städte du hast und ob du ein beweisbares Optimum brauchst.

Häufige Fehler

• Eine exakte Antwort im großen Maßstab erwarten. TSP ist NP-schwer. Es ist kein Algorithmus bekannt, der 1.000 Städte in vertretbarer Zeit exakt löst, und einen zu finden würde P gegen NP entscheiden. Behauptet ein Werkzeug, auf einer großen Instanz schnell ein exaktes Optimum zu liefern, gibt es eine heuristische Tour zurück.
• Sich allein auf den nächsten Nachbarn verlassen. Gierige Konstruktion liegt typischerweise 25 Prozent über dem Optimum und kann im schlechtesten Fall beliebig schlecht sein, weil die zuletzt übrigen Städte sehr lange Kanten erzwingen. Lasse stets eine lokale Suche folgen.
• Christofides auf nichtmetrische Distanzen anwenden. Seine Approximationsgarantie von 1,5 hängt an der Dreiecksungleichung. Bei Einbahnstraßen, asymmetrischen Kosten oder gesperrten Routen gilt die Schranke schlicht nicht.
• TSP mit dem Tourenplanungsproblem verwechseln. TSP ist ein Fahrzeug, ohne Kapazität und ohne Zeitfenster. Sobald eine Flotte oder Ladegrenzen hinzukommen, brauchst du VRP- oder CVRP-Methoden; eine in Stücke zerlegte TSP-Tour ist keine gültige VRP-Lösung.
• Übersehen, dass die Startstadt keine Rolle spielt. Eine TSP-Tour ist ein Kreis, Rotieren ändert also nichts. Implementierungen, die den Start als bedeutsam behandeln, verschwenden Arbeit und können für identische Touren verschiedene Kosten melden.

Häufig gestellte Fragen

Was ist das Problem des Handlungsreisenden?

Gegeben eine Menge von Städten und die Distanz zwischen je zwei, fragt TSP nach der kürzesten Route, die jede Stadt genau einmal besucht und zum Start zurückkehrt. Es ist eines der meistuntersuchten Probleme der kombinatorischen Optimierung und NP-schwer, das heißt, es ist kein exakter Polynomialzeitalgorithmus bekannt.

Warum ist TSP so schwer zu lösen?

Die Zahl verschiedener Touren wächst wie (n-1)!/2, sodass 20 Städte bereits etwa 60 Billiarden Touren zulassen. Kein bekannter Algorithmus vermeidet exponentiellen Aufwand im schlechtesten Fall. Die beste exakte Methode, Held-Karp, läuft in O(n hoch 2 mal 2 hoch n) und wird jenseits von rund 25 Städten unpraktikabel.

Welcher Algorithmus ist der beste für TSP?

Das hängt von der Größe ab. Unter etwa 20 Städten liefert Held-Karp ein exaktes Optimum. Für metrische Instanzen garantiert Christofides eine Tour innerhalb des 1,5-fachen des Optimums. Für große reale Instanzen liefern Lin-Kernighan oder nächster Nachbar gefolgt von 2-opt in Sekunden Touren innerhalb weniger Prozent des Optimums.

Was macht 2-opt eigentlich?

Es entfernt wiederholt zwei Kanten aus der Tour und verbindet die beiden entstehenden Wege andersherum, wobei die Änderung erhalten bleibt, wenn die Tour kürzer wird. Geometrisch entfernt es Überkreuzungen: kreuzen sich zwei Kanten einer Tour, ist die kreuzungsfreie Neuverbindung wegen der Dreiecksungleichung kürzer.

Was ist der Unterschied zwischen TSP und dem Tourenplanungsproblem?

TSP führt ein einzelnes Fahrzeug durch alle Städte, ohne weitere Einschränkung als jede einmal zu besuchen. VRP führt eine Flotte von einem Depot aus, meist mit Kapazitätsgrenzen und oft mit Zeitfenstern und Fahrerschichten. TSP ist der Sonderfall des VRP mit einem Fahrzeug und unbegrenzter Kapazität.