Handlungsreisenden-Löser — Finde die Kürzeste Route Durch Jede Stadt
Unser Handlungsreisenden-Löser findet die exakte kostenminimale Tour, die jede Stadt genau einmal besucht und zur Startstadt zurückkehrt, gegeben eine Distanzmatrix zwischen den Städten, mittels des Held-Karp-Bitmask-Dynamik-Programmierungs-Algorithmus — eine exakte Methode, die bewusst auf höchstens 12 Städte beschränkt ist, da das Problem im Allgemeinen NP-schwer ist.
Kurzantwort
Gib eine Distanzmatrix zwischen Städten ein, um sofort die exakte kürzeste Rundreisetour mittels Held-Karp-Dynamik-Programmierung zu finden.
Geben Sie eine Zeile pro Stadt ein, kommagetrennte Distanzen, z. B. 0,10,15,20 dann 10,0,35,25. Bis zu 12 Städte.
So verwenden Sie Handlungsreisenden-Löser — Exakte Held-Karp-DP Online
- 1
Gib eine Distanzmatrix ein, eine Zeile pro Stadt, mit kommagetrennten Distanzen, z. B. 0,10,15,20 dann 10,0,35,25 und so weiter.
- 2
Die Matrix sollte quadratisch sein, wobei jeder Eintrag die Distanz zwischen zwei Städten angibt (Diagonaleinträge sind typischerweise 0).
- 3
Klicke auf 'Berechnen', um die exakte optimale Tour mittels Held-Karp-Dynamik-Programmierung zu finden.
Warum Handlungsreisenden-Löser — Exakte Held-Karp-DP Online verwenden?
Das Problem des Handlungsreisenden fragt nach der kürzestmöglichen Route, die jede Stadt genau einmal besucht und zum Start zurückkehrt — ein klassisches NP-schweres Problem, bei dem die Brute-Force-Überprüfung aller (n−1)!/2 möglichen Touren jenseits einer Handvoll Städte unmöglich wird. Der Held-Karp-Algorithmus verbessert Brute Force dramatisch mittels dynamischer Programmierung über Teilmengen: Er verfolgt für jede Teilmenge besuchter Städte und jede mögliche Endstadt den günstigsten Weg, um diesen Zustand zu erreichen, und baut von kleinen Teilmengen bis zur vollständigen Menge in O(n² · 2ⁿ)-Zeit statt O(n!) auf. Das ist immer noch exponentiell, daher begrenzt dieser Rechner das Problem auf 12 Städte, wo Held-Karp angenehm schnell bleibt und dennoch die exakte, nachweislich optimale Tour findet (nicht nur eine gute Näherung).
Häufig gestellte Fragen
Ähnliche Tools
Hamiltonweg-Prüfer — Jeden Knoten Einmal Besuchen Online
Prüfen Sie, ob ein Graph einen Hamiltonweg hat — einen Weg, der jeden Knoten genau einmal besucht — über Backtracking-Suche. Kostenloser Rechner, beschränkt auf Graphen mit bis zu 10 Knoten.
Minimaler-Spannbaum-Rechner — Kruskal-Algorithmus Online
Finden Sie den minimalen Spannbaum eines gewichteten Graphen mit Kruskals Algorithmus. Kostenloser Rechner mit einfacher Kantenlisteneingabe und Union-Find-Zykluserkennung.
Lineare-Programmierung-Löser — 2-Variablen-Eckpunktmethode Online
Löse ein 2-Variablen-lineares-Programm, indem du jeden Eckpunkt des zulässigen Bereichs findest und auswertest. Kostenloser Rechner, maximieren oder minimieren mit linearen Nebenbedingungen.