Math
Voyageur de commerce
Une tournée qui raccourcit sous tes yeux - gloutonne, 2-opt décroisant arête par arête, recuit escaladant le mur - contre l'optimum exact pour treize villes et la force brute sur chaque tournée pour huit.
Ce qui se passe
Comparer la construction voisine, l'amélioration 2-opt et le recuit simulé sur les mêmes villes. L'optimum local A 2-opt n'a pas d'amélioration de l'échange à deux bords; Ce n'est pas nécessairement le circuit le plus court au monde. Le recuit accepte parfois des tours plus longs pour échapper aux minima locaux, sans garantir l'optimum dans un cycle fini.
L'arbre d'extension minimum est une limite inférieure sur chaque tour. Pour ces distances euclidiennes, le doublement d'un arbre couvrant et le raccourcissement des visites répétées prouve que le tour optimal est au plus deux fois l'arbre couvrant minimum. Cette limite concerne l'optimum et une construction arborescente appropriée; Il ne contraint pas chaque tour gourmand ou intermédiaire.
La petite scène exacte utilise la programmation dynamique de Held-Karp sur des sous-ensembles, avec le temps O(N²·2^N) plutôt que d'énumérer chaque permutation. La scène de huit villes peut énumérer chaque tour distinct. Les algorithmes exacts n'ont pas besoin d'inspecter la plupart des permutations, mais aucun algorithme polynomial exact n'est connu pour le problème général du vendeur itinérant. Comparez les tours heuristiques mesurés avec la référence exacte si disponible.
Équations du module
Équations
villes : N points dans [−1, 1]² tirés avec le dé commun (graine 3) ; longueur de la tournée L = Σ |c_k − c_{k+1}| le long du cycle ; (N − 1)!/2 tournées distinctes : 2520 pour 8, 2.4·10^8 pour 13, 1.0·10^46 pour 40
glouton : à partir de la ville 0, toujours la plus proche non visitée (égalités départagées par l'indice) ; 12.8105 pour quarante villes
2-opt : arêtes (a, b) et (c, d) avec a avant c dans la tournée ; Δ = |ac| + |bd| − |ab| − |cd| ; la première paire dans l'ordre du balayage avec Δ < 0 est décroisée en inversant le segment b … c ; recommencer jusqu'à ce qu'il n'y en ait plus : 16 décroisements, 10.5850 - le mur (la tournée a atteint un optimum local)
recuit simulé : une paire aléatoire (i, j), i < j, j − i ≥ 2 ; acceptée si Δ ≤ 0, sinon avec la probabilité exp(−Δ/T) ; T₀ = 0.3, T ← 0.9997 T à chaque pas, 20 000 pas ; graine 6 : meilleur 10.4954, 462 acceptés, 231 en montée ; 2-opt dessus : 10.2673
borne : MST ≤ L pour toute tournée (une tournée privée d'une arête est un arbre couvrant), et la tournée tirée d'un arbre doublé montre que L_opt ≤ 2·MST ; MST = 8.4480 pour les quarante (l'arbre de GraphTheory, même dé) ; 10.2673 / 8.4480 = 1.215
Held–Karp : dp[S, k] = plus court chemin issu de 0 passant par l'ensemble S et finissant en k ; dp[S + k, k] = min sur j dans S de dp[S, j] + |jk| ; 2^N·N² pas ; 13 villes, graine 8 : optimum 7.4710, tournée 0 7 1 3 12 6 8 10 5 4 11 2 9 ; 2-opt à partir de 50 tournées aléatoires (Fisher–Yates sur les graines 100 …) : 7 l'atteignent, pire cas 1.0789 ×, moyenne 1.0678 ×
force brute : toutes les permutations de 1 … N − 1 dans l'ordre lexicographique, chaque tournée une seule fois (premier < dernier) ; 8 villes, graine 3 : 2520 tournées, meilleure 5.2175 = Held–Karp, plus longue 11.9462, moyenne 9.1055
