Math
Handlungsreisender
Eine Rundreise, die kürzer wird, während man zusieht - gierig, 2-opt entkreuzt Kante für Kante, Ausglühen klettert über die Mauer - gegen das exakte Optimum für dreizehn Städte und rohe Gewalt über jede Tour für acht.
Was passiert
Vergleichen Sie den Bau des nächsten Nachbarn, die 2-opt-Verbesserung und das simulierte Glühen in denselben Städten. A 2-opt lokales Optimum hat keinen verbessernden Zwei-Kanten-Austausch; Es muss nicht die weltweit kürzeste Tour sein. Das Glühen akzeptiert manchmal längere Touren, um lokale Minimum zu entkommen, ohne das Optimum in einem endlichen Lauf zu garantieren.
Der minimale Spannbaum ist eine untere Grenze auf jeder Tour. Für diese euklidischen Distanzen beweist die Verdoppelung eines Spannbaums und die Abkürzung wiederholter Besuche, dass die optimale Tour höchstens doppelt so groß ist wie der minimale Spannbaum. Diese Begrenzung betrifft das Optimum und eine geeignete baumbasierte Konstruktion; Es beschränkt nicht jede gierige oder mittlere Tour.
Die kleine exakte Szene verwendet dynamische Held-Karp-Programmierung über Teilmengen, mit O(N²·2^N)-Zeit, anstatt jede Permutation aufzuzählen. Die Acht-Städte-Szene kann jede einzelne Tour aufzählen. Exakte Algorithmen müssen die meisten Permutationen nicht inspizieren, aber es ist kein polynomialzeitgenauer Algorithmus für das allgemeine Reiseverkäufer-Problem bekannt. Vergleichen Sie die gemessenen heuristischen Touren mit der exakten Referenz, sofern verfügbar.
Gleichungen des Moduls
Gleichungen
Städte: N Punkte in [−1, 1]² aus dem gemeinsamen Würfel (Seed 3); Tourlänge L = Σ |c_k − c_{k+1}| entlang des Zyklus; (N − 1)!/2 verschiedene Touren: 2520 für 8, 2.4·10^8 für 13, 1.0·10^46 für 40
gierig: von Stadt 0 aus immer die nächste unbesuchte (bei Gleichstand nach Index); 12.8105 für vierzig Städte
2-opt: Kanten (a, b) und (c, d) mit a vor c auf der Tour; Δ = |ac| + |bd| − |ab| − |cd|; das erste Paar in Durchlaufreihenfolge mit Δ < 0 wird durch Umkehren des Abschnitts b … c entkreuzt; wiederholen, bis keines mehr übrig ist: 16 Entkreuzungen, 10.5850 - die Wand (ein lokales Optimum)
Simuliertes Abkühlen: ein zufälliges Paar (i, j), i < j, j − i ≥ 2; akzeptiert, wenn Δ ≤ 0, sonst mit Wahrscheinlichkeit exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T in jedem Schritt, 20 000 Schritte; Seed 6: beste 10.4954, 462 akzeptiert, 231 bergauf; 2-opt darauf: 10.2673
Schranke: MST ≤ L für jede Tour (eine Tour ohne eine Kante ist ein aufspannender Baum), und die Tour eines verdoppelten Baums zeigt L_opt ≤ 2·MST; MST = 8.4480 für die vierzig (der Baum von GraphTheory, derselbe Würfelwurf); 10.2673 / 8.4480 = 1.215
Held–Karp: dp[S, k] = kürzester Weg von 0 durch die Menge S, der in k endet; dp[S + k, k] = min über j in S von dp[S, j] + |jk|; 2^N·N² Schritte; 13 Städte, Startwert 8: Optimum 7.4710, Rundreise 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-Opt von 50 zufälligen Rundreisen (Fisher–Yates mit Startwerten 100 …): 7 erreichen es, schlechteste 1.0789 ×, Mittel 1.0678 ×
vollständige Aufzählung: jede Permutation von 1 … N − 1 in lexikografischer Reihenfolge, jede Rundreise einmal (erste < letzte); 8 Städte, Startwert 3: 2520 Rundreisen, beste 5.2175 = Held–Karp, längste 11.9462, Mittel 9.1055
