Math
Viajante de comercio
Un recorrido que se acorta mientras miras - voraz, 2-opt descruzando arista a arista, recocido trepando el muro - frente al óptimo exacto para trece ciudades y la fuerza bruta sobre cada recorrido para ocho.
Qué ocurre
Compare la construcción del vecino más cercano, la mejora 2-opt y el recocido simulado en las mismas ciudades. El óptimo local A 2-opt no mejora el intercambio de dos bordes; No tiene por qué ser el tour más corto del mundo. El recocido a veces acepta recorridos más largos para escapar de los mínimos locales, sin garantizar el óptimo en una carrera finita.
El árbol de expansión mínimo es un límite inferior en cada recorrido. Para estas distancias euclidianas, doblar un árbol de expansión y acortar las visitas repetidas demuestra que el recorrido óptimo es como máximo dos veces el árbol de expansión mínimo. Este límite se refiere a la construcción óptima y adecuada basada en árboles; No limita a cada viajero codicioso o intermedio.
La pequeña escena exacta utiliza la programación dinámica de Held-Karp sobre subconjuntos, con tiempo O(N²·2^N) en lugar de enumerar cada permutación. La escena de ocho ciudades puede enumerar cada recorrido distinto. Los algoritmos exactos no necesitan inspeccionar la mayoría de las permutaciones, pero no se conoce ningún algoritmo exacto en tiempo polinomial para el problema general del vendedor ambulante. Compare los tours heurísticos medidos con la referencia exacta cuando esté disponible.
Ecuaciones del módulo
Ecuaciones
ciudades: N puntos en [−1, 1]² del dado compartido (semilla 3); longitud del recorrido L = Σ |c_k − c_{k+1}| a lo largo del ciclo; (N − 1)!/2 recorridos distintos: 2520 para 8, 2.4·10^8 para 13, 1.0·10^46 para 40
voraz: desde la ciudad 0, siempre la no visitada más cercana (los empates se deciden por índice); 12.8105 para cuarenta ciudades
2-opt: aristas (a, b) y (c, d) con a antes de c en el recorrido; Δ = |ac| + |bd| − |ab| − |cd|; el primer par en orden de barrido con Δ < 0 se descruza invirtiendo el segmento b … c; se repite hasta que no quede ninguno: 16 descruces, 10.5850 - el muro (se llega a un óptimo local)
recocido: un par aleatorio (i, j), i < j, j − i ≥ 2; se acepta si Δ ≤ 0, y si no con probabilidad exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T en cada paso, 20 000 pasos; semilla 6: mejor 10.4954, 462 aceptados, 231 cuesta arriba; 2-opt sobre él: 10.2673
cota: MST ≤ L para todo recorrido (un recorrido menos una arista es un árbol generador), y el recorrido de un árbol duplicado muestra que L_opt ≤ 2·MST; MST = 8.4480 para los cuarenta (el árbol de GraphTheory, el mismo dado); 10.2673 / 8.4480 = 1.215
Held–Karp: dp[S, k] = camino más corto desde 0 pasando por el conjunto S y terminando en k; dp[S + k, k] = min sobre j en S de dp[S, j] + |jk|; 2^N·N² pasos; 13 ciudades, semilla 8: óptimo 7.4710, recorrido 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-opt desde 50 recorridos aleatorios (Fisher–Yates con semillas 100 …): 7 lo alcanzan, peor 1.0789 ×, media 1.0678 ×
fuerza bruta: todas las permutaciones de 1 … N − 1 en orden lexicográfico, cada recorrido una vez (primera < última); 8 ciudades, semilla 3: 2520 recorridos, el mejor 5.2175 = Held–Karp, el más largo 11.9462, media 9.1055
