Traveling Salesman Solver (TSP)

Traveling Salesman Solver (TSP)

Der Traveling Salesman Solver TSP ist ein praktischer, pädagogischer Rechner für das klassische Problem des Handlungsreisenden (Traveling Salesman Problem - TSP): Gegeben ist eine Menge von Städten und paarweisen Distanzen, gesucht wird die kürzestmögliche Tour, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Dieser Solver akzeptiert entweder planare Koordinaten oder eine benutzerdefinierte Distanzmatrix, wählt automatisch den besten Algorithmus basierend auf der Problemgröße aus und rendert die resultierende Tour als animierte SVG-Karte.

Was ist das Traveling Salesman Problem?

Formal gesehen sucht das TSP bei einem vollständigen gewichteten Graphen G = (V, E) mit der Knotenmenge V = {1, 2, ..., n} und den Kantengewichten d(i, j) nach einer Permutation π der Knoten, die Folgendes minimiert:

Der letzte Term schließt den Kreis. Das TSP ist eines der ältesten und am meisten untersuchten Probleme der kombinatorischen Optimierung — es ist im allgemeinen Fall NP-hart, was bedeutet, dass kein bekannter Algorithmus jede Instanz in polynomieller Zeit löst. Dennoch findet es Anwendung in unzähligen realen Szenarien: Fahrzeug-Routing, Leiterplattenbohren, DNA-Sequenzierung, Kommissionierrouten im Lager, astronomische Beobachtungspläne und sogar ländliche Postzustellung.

Wie dieser Solver funktioniert

Held–Karp Dynamische Programmierung (Exakt)

Für kleine Instanzen (bis zu 12 Städte) berechnet der Solver die nachweislich optimale Tour mit dem Held–Karp-Algorithmus, der 1962 unabhängig von Richard Bellman sowie Michael Held & Richard Karp veröffentlicht wurde. Die zentrale Rekursion, wobei C(S, j) der kürzeste Pfad von Knoten 1 zu Knoten j unter Besuch genau der Teilmenge S ist:

Die optimalen Tourkosten ergeben sich dann aus min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp läuft in O(2ⁿ · n²) Zeit und benötigt O(2ⁿ · n) Speicher — eine gewaltige Verbesserung gegenüber Brute-Force n!, aber dennoch exponentiell. Ab etwa 20 Städten wird der Speicherbedarf unpraktikabel.

Nearest-Neighbor + 2-opt (Heuristik)

Für größere Instanzen nutzt der Solver eine zweistufige Heuristik. Zuerst konstruiert Nearest-Neighbor eine schnelle Tour, indem gierig von jedem Startknoten aus die jeweils nächste unbesuchte Stadt angesteuert wird. Der Solver testet viele Startknoten und behält die beste Tour. Dann verbessert die lokale Suche 2-opt die Tour, indem iterativ zwei Kanten entfernt und die resultierenden Pfade auf die einzig andere mögliche Weise wieder verbunden werden:

Geometrisch gesehen entfernt 2-opt alle "Kreuzungen" in der Tour: Zwei sich kreuzende Segmente können immer "entkreuzt" werden, um eine kürzere Gesamtlänge zu erzielen. Der Algorithmus stoppt bei einem lokalen Optimum, an dem kein einzelner Tausch mehr hilft, einer sogenannten 2-optimalen Tour. Bei realistischen euklidischen Instanzen findet 2-opt typischerweise Touren innerhalb von 2–5 % des wahren Optimums in Millisekunden.

Eingabeformate

Koordinaten-Modus (x, y)

Eine Stadt pro Zeile. Jede Zeile besteht aus Label, x, y — das Label ist optional. Der Solver berechnet euklidische Distanzen automatisch und visualisiert die Städte an ihren tatsächlichen Positionen.

Distanzmatrix-Modus

Eine quadratische n × n Matrix mit nicht-negativen Distanzen, eine Zeile pro Zeile, Werte durch Leerzeichen oder Kommas getrennt. Matrizen können symmetrisch oder asymmetrisch sein — asymmetrische Matrizen modellieren Einbahnstraßen, Flugpreise mit variierender Verfügbarkeit oder windabhängige Reisezeiten. Optional können Labels im Feld Matrix-Beschriftungen angegeben werden.

Algorithmus-Vergleich

So verwenden Sie diesen Solver

1. Eingabemodus wählen. Koordinaten, wenn Ihre Städte aussagekräftige (x, y) Positionen haben; Distanzmatrix, wenn Ihre Kosten nicht euklidisch oder asymmetrisch sind.
2. Daten einfügen oder tippen. Eine Stadt oder Matrixzeile pro Zeile. Klicken Sie auf ein Schnellbeispiel oberhalb des Formulars, um ein gültiges Beispiel vorauszufüllen.
3. Algorithmus wählen. Auf Auto belassen für den richtigen Standard: Held–Karp, wenn die Instanz klein genug für nachweisbare Optimalität ist, sonst NN + 2-opt. Erzwingen Sie einen spezifischen Algorithmus zum Vergleichen.
4. Geschlossen oder offen wählen. Eine geschlossene Tour kehrt zum Start zurück — das klassische TSP. Der Modus „Offener Pfad“ löst das verwandte Problem des Hamiltonpfads, bei dem der Verkäufer in einer anderen Stadt endet.
5. Auf Lösen klicken. Die Ergebnisseite zeigt die Gesamtlänge der Tour, eine animierte SVG der Route (klicken Sie auf „Animation abspielen“, um sie zu wiederholen), die vollständige Städtereihenfolge, eine Aufschlüsselung pro Kante und die Distanzmatrix mit hervorgehobenen Tourkanten.

Beispielrechnung

Betrachten Sie fünf Städte — ein Rechteck plus eine Spitze: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Der Solver liefert:

• Tour: A → D → E → C → B → A
• Länge: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Optimal? Ja — Held–Karp beweist, dass keine kürzere Tour existiert.
• Warum diese Reihenfolge? Die Route folgt der konvexen Hülle der fünf Punkte (A → D → E → C → B → A). Eine klassische Eigenschaft des euklidischen TSP ist, dass eine optimale Tour die Punkte auf der konvexen Hülle in ihrer zyklischen Reihenfolge besucht; Punkte im Inneren ordnen sich zwischen benachbarten Hüllennachbarn ein. Jede Tour, die ihren eigenen Pfad kreuzt, wie A → C → B → D → E → A (Länge ≈ 21.8), kann durch 2-opt immer zu einem kürzeren Ergebnis entkreuzt werden.

Reale Anwendungen

• Logistik & Zustellung — Optimierung der Tagesroute eines Fahrers mit 15 Stopps zur Minimierung von Kraftstoff und Zeit.
• Fertigung — Reihenfolge der Bohrungen, die ein CNC-Bohrer auf einer Leiterplatte vornehmen muss, um die Kopfbewegung zu minimieren.
• Genom-Assemblierung — Sortieren von DNA-Fragmenten nach Überlappungsähnlichkeit, kodiert als Distanzmatrix.
• Astronomie — Planung der Teleskopbewegungen zwischen Zielsternen zur Maximierung der Beobachtungszeit.
• Lagerkommissionierung — Abfolge der Gangbesuche zur Erfüllung eines Auftrags in möglichst wenigen Schritten.
• Tourismusplanung — Planung einer Reise durch mehrere Städte zur Minimierung der Reisezeit und Fahrtkosten.

Häufig gestellte Fragen (FAQ)

Was ist das Traveling Salesman Problem?

Das Traveling Salesman Problem (TSP) sucht nach der kürzestmöglichen Tour, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Es ist eines der bekanntesten Probleme der kombinatorischen Optimierung und im allgemeinen Fall NP-hart.

Was ist der Held–Karp-Algorithmus?

Held–Karp ist ein dynamischer Programmieralgorithmus, der das TSP exakt löst. Da er exponentielle Laufzeit und Speicher benötigt, wird er in der Praxis meist nur für bis zu 20 Städte genutzt. Dieser Solver nutzt ihn für n ≤ 12.

Was ist 2-opt und warum wird es verwendet?

2-opt ist eine lokale Suchheuristik, die Kantenpaare tauscht, um Kreuzungen zu entfernen. Es ist sehr schnell und liefert für größere Instanzen Lösungen, die nah am Optimum liegen.

Wann sollte ich Koordinaten gegenüber einer Distanzmatrix verwenden?

Koordinaten eignen sich für Punkte in einer Ebene (Karten, Leiterplatten). Eine Distanzmatrix ist nötig, wenn Wege nicht direkt sind (Einbahnstraßen) oder Kosten asymmetrisch ausfallen (Flugpreise, Wind).

Ist die 2-opt-Lösung optimal?

Nein, sie ist "2-optimal", also ein lokales Optimum. In der Praxis liegt sie oft nur wenige Prozent über dem globalen Bestwert, bietet aber keine Garantie für absolute Optimalität.

Unterstützt dieses Tool asymmetrische Distanzmatrizen?

Ja. Im Matrix-Modus können Sie asymmetrische Werte eingeben (z. B. Hinweg teurer als Rückweg). Beide Algorithmen verarbeiten dies korrekt.

Weiterführende Literatur

• Problem des Handlungsreisenden — Wikipedia
• Held–Karp algorithm — Wikipedia (Englisch)
• 2-opt — Wikipedia
• Nearest-Neighbor-Heuristik — Wikipedia

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator
• Mengenlehre-Rechner
• Venn-Diagramm-Generator (3 Mengen)
• Chinesischer Restsatz Rechner
• Euler Totient Funktion Rechner
• Erweiterter Euklidischer Algorithmus Rechner
• Modularer Multiplikativer Inverser Rechner
• Kettenbruch-Rechner Empfohlen
• Dijkstra Kürzester Weg Rechner
• Minimaler Spannbaum Rechner
• Graph Gradfolgen-Validator
• Derangement Subfaktorielle Rechner
• Stirling-Zahlen-Rechner
• Schubfachprinzip-Rechner
• Markov-Ketten Stationäre Verteilung Rechner
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu