billycalc

Untere Schranke TSP

Berechnen Sie Untere Schranke TSP kostenlos online mit der exakten Formel und einem Beispiel. Ohne Anmeldung.

Untere Schranke TSP

Gewicht des minimalen Spannbaums W(MST)
Länge der gefundenen Tour (Heuristik), 0 = keine
Untere Schranke der optimalen Tourlänge
100
OPT ≥ W(MST): Ohne eine Kante wird die Tour zu einem aufspannenden Pfad, der nicht leichter ist als der minimale Spannbaum (nichtnegative Gewichte)Bei Dreiecksungleichung liefert das Ablaufen des Baums eine Tour ≤ 2·W(MST), der Christofides-Algorithmus ≤ 1,5·OPT; eine schärfere untere Schranke liefern die 1-Bäume nach Held–KarpBerechnen Sie Untere Schranke TSP kostenlos online mit der exakten Formel und einem Beispiel. Ohne Anmeldung.
Obere Schranke (Baumdurchlauf, bei Dreiecksungleichung)
200
Die gefundene Tour ist höchstens so viel schlechter als das Optimum
30%

Mehr über: Untere Schranke TSP

Was er berechnet

Der Rechner „Untere Schranke TSP“ berechnet Untere Schranke der optimalen Tourlänge aus 2 Parametern: gewicht des minimalen spannbaums w(mst), länge der gefundenen tour (heuristik), 0 = keine.

Standard-IT-Berechnungen für Entwickler und Administratoren.

Beispielrechnung

Mit den Parametern Gewicht des minimalen Spannbaums W(MST) = 100, Länge der gefundenen Tour (Heuristik), 0 = keine = 130 ergibt sich 100 (OPT ≥ W(MST): Ohne eine Kante wird die Tour zu einem aufspannenden Pfad, der nicht leichter ist als der minimale Spannbaum (nichtnegative Gewichte)).

So funktioniert's

  1. Geben Sie gewicht des minimalen spannbaums w(mst) und länge der gefundenen tour (heuristik), 0 = keine ein — jedes Feld oben lässt sich mit einem Schieberegler anpassen.
  2. Untere Schranke der optimalen Tourlänge wird automatisch berechnet, während Sie tippen.
  3. Sehen Sie sich das Beispiel unten an, um die Formel an echten Zahlen zu sehen.
  4. Kopieren Sie das Ergebnis oder setzen Sie ein Lesezeichen für diesen Rechner.

Verwandte Rechner

Häufige Fragen

Wie wird Untere Schranke TSP berechnet?
Der Untere Schranke TSP-Rechner berechnet Untere Schranke der optimalen Tourlänge aus gewicht des minimalen spannbaums w(mst), länge der gefundenen tour (heuristik), 0 = keine. Geben Sie oben Ihre Werte ein und die exakte Formel wird sofort angewendet; ein durchgerechnetes Beispiel mit echten Zahlen steht unten.
Ist der Untere Schranke TSP-Rechner kostenlos?
Ja. Er ist völlig kostenlos, ohne Anmeldung, läuft vollständig in Ihrem Browser und sendet keine Daten an einen Server.

Weitere Rechner in dieser Kategorie

Entdecken Sie weitere kostenlose Tools

GraphdurchmesserKürzester Weg (Dijkstra)LCS-LängeHamming-DistanzPageRankEigenvektor-ZentralitätK-Means-Cluster (k)EllbogenmethodeRandom-Forest-BäumeSchichten des neuronalen NetzesZeitplan der LernrateMAC-Adresse ↔ IPv6