Rundreiseproblem des Handlungsreisenden
Finden Sie eine genaue Mindestkosten-Tour, die jeden Knoten einmal besucht und zurück zu Knoten Null in einer kleinen gerichteten Kostenmatrix.
IHRE BERECHNUNG
Ergebnis
—
Rechenschritte
Gehen Sie die Schritte einzeln durch oder zeigen Sie die gesamte Berechnung an. Die Schritte verwenden Ihre aktuellen Eingaben.
Berechnungsmethode
Verwenden Sie Held-Karp-Untersatz dynamische Programmierung, so dass asymmetrisch eingegebene Kosten bei der Festsetzung der Startknoten auf Null.
DP[visited,last]=min(DP[visited without last,previous]+cost(previous,last)); close tour to node 0
Rechenbeispiel
Die vier Knoten Standard symmetrische Matrix hat minimale Tourkosten 80, zum Beispiel 0→1→3→2→0.
Annahmen und Hinweise zu den Eingaben
Vollständige Matrix der nichtnegativen Kosten, 2–14 Knoten. Keine fehlenden Kanten, Straßendaten, Verkehr, Zeitfenster oder Fahrzeugbeschränkungen; Kosten sind konsistente numerische Einheiten. Eine optimale Tour wird angezeigt, wenn mehrere Krawatte. Exponentielle Exponential-Size-Suche ist für die Browser-Nutzung begrenzt.
Hinweise zum Rechner
Kann ich eigene Werte eingeben?
Ja. Ersetzen Sie die Beispielwerte durch Ihre eigenen Eingaben. Ergebnis, Rechenschritte, Tabellen und gegebenenfalls Diagramme werden entsprechend aktualisiert. Bei leeren oder ungültigen Eingaben wird das Ergebnis gelöscht. Fehlende Angaben werden niemals unbemerkt durch Beispielwerte ersetzt.
Sind die Ergebnisse exakt?
Die Ergebnisse beruhen auf Gleitkommaarithmetik und werden für die Anzeige gerundet. Beachten Sie die Formel, die Annahmen und die gegebenenfalls angegebene Datengenauigkeit.
Werden meine Eingaben hochgeladen?
Die Berechnung erfolgt in Ihrem Browser. Ein Benutzerkonto, Datei-Uploads oder ein externer KI-Dienst sind nicht erforderlich. Beim Neuladen der Seite werden die Eingaben zurückgesetzt.
Finden Sie eine kostengünstigste Route durch einen kleinen gerichteten oder nicht gerichteten Randdiagramm mit nicht negativen Kosten.
Planen Sie eine Abfolge eingegebener Entfernungen, Durchschnittsgeschwindigkeiten und Brüche mit datierten Ankunftszeiten.
Berechnen Sie früheste und späteste Aufgabenzeiten, totale Slack- und kritische Aufgaben in einem Abhängigkeitsnetzwerk.
Reservierter Werbeplatz.