Math
Commesso viaggiatore
Un giro che si accorcia mentre guardi - goloso, 2-opt che scrocia spigolo per spigolo, ricottura che scavalca il muro - contro l'ottimo esatto per tredici città e la forza bruta su ogni giro per otto.
Cosa succede
Confrontare la costruzione del vicino più vicino, il miglioramento 2-opt e la ricottura simulata sulle stesse città. L'ottimo locale di A 2-opt non ha miglioramento dello scambio a due bordi; Non deve essere necessariamente il tour più breve al mondo. La ricottura a volte accetta tour più lunghi per sfuggire ai minimi locali, senza garantire l'ottimo in una corsa finita.
L'albero di espansione minimo è un limite inferiore su ogni tour. Per queste distanze euclidee, raddoppiando un albero span e accorciando le visite ripetute si dimostra che il tour ottimale è al massimo il doppio dell'albero span minimo. Questo vincolo riguarda l'ottimizzazione e un'adeguata costruzione ad albero; Non costringe ogni tour avido o intermedio.
La piccola scena esatta utilizza la programmazione dinamica di Held-Karp su sottoinsiemi, con il tempo O(N²·2^N) piuttosto che enumerare ogni permutazione. La scena di otto città può elencare ogni tour distinto. Gli algoritmi esatti non devono ispezionare la maggior parte delle permutazioni, ma nessun algoritmo esatto in tempo polinomiale è conosciuto per il problema generale del venditore ambulante. Confronta i tour euristici misurati con il riferimento esatto, se disponibile.
Equazioni del modulo
Equazioni
città: N punti in [−1, 1]² dal dado condiviso (seme 3); lunghezza del percorso L = Σ |c_k − c_{k+1}| lungo il ciclo; (N − 1)!/2 percorsi distinti: 2520 per 8, 2.4·10^8 per 13, 1.0·10^46 per 40
goloso: dalla città 0, sempre la più vicina non visitata (parità risolte per indice); 12.8105 per quaranta città
2-opt: archi (a, b) e (c, d) con a prima di c sul percorso; Δ = |ac| + |bd| − |ab| − |cd|; la prima coppia in ordine di scansione con Δ < 0 viene sciolta togliendo l'incrocio, invertendo il segmento b … c; si ripete finché non ne restano: 16 incroci tolti, 10.5850 - il muro (un ottimo locale)
ricottura simulata: una coppia casuale (i, j), i < j, j − i ≥ 2; accettata se Δ ≤ 0, altrimenti con probabilità exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T a ogni passo, 20 000 passi; seme 6: migliore 10.4954, 462 accettate, 231 in salita; 2-opt su di essa: 10.2673
limite: MST ≤ L per ogni percorso (un percorso privato di un arco è un albero di copertura), e il percorso di un albero raddoppiato mostra che L_opt ≤ 2·MST; MST = 8.4480 per i quaranta (l'albero di GraphTheory, stesso dado); 10.2673 / 8.4480 = 1.215
Held–Karp: dp[S, k] = cammino più breve da 0 attraverso l'insieme S che termina in k; dp[S + k, k] = min su j in S di dp[S, j] + |jk|; 2^N·N² passi; 13 città, seme 8: ottimo 7.4710, percorso 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-opt da 50 percorsi casuali (Fisher–Yates su semi 100 …): 7 lo raggiungono, il peggiore 1.0789 ×, la media 1.0678 ×
forza bruta: ogni permutazione di 1 … N − 1 in ordine lessicografico, ogni percorso una volta (primo < ultimo); 8 città, seme 3: 2520 percorsi, migliore 5.2175 = Held–Karp, più lungo 11.9462, media 9.1055
