EDP Sciences logo
Authentification abonné
Rechercher
Menu
Numéro
J. Phys. I France
Volume 7, Numéro 1, January 1997
Page(s) 117 - 136
DOI https://doi.org/10.1051/jp1:1997129
DOI: 10.1051/jp1:1997129
J. Phys. I France 7 (1997) 117-136

The Random Link Approximation for the Euclidean Traveling Salesman Problem

N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus

Division de Physique Théorique, Unité de Recherche des Universités Paris XI et Paris VI associée au CNRS, Institut de Physique Nucléaire, Université Paris-Sud, 91406 Orsay Cedex, France



(Received 22 Avril 1996, revised 28 June 1996, accepted 23 September 1996)

Abstract
The traveling salesman problem (TSP) consists of finding the length of the shortest closed tour visiting N "cities". We consider the Euclidean TSP where the cities are distributed randomly and independently in a d-dimensional unit hypercube. Working with periodic boundary conditions and inspired by a remarkable universality in the kth nearest neighbor distribution, we find for the average optimum tour length $\langle L_{\rm E}\rangle =\beta_{\rm E}(d)N^{1-1/d}[1+O(1/N)] $ with $\beta_{\rm E}=0.7120\pm 0.0002$ and $\beta_{\rm E}(3)=0.6979\pm 0.0002$. We then derive analytical predictions for these quantities using the random link approximation, where the lengths between cities are taken as independent random variables. From the "cavity" equations developed by Krauth, Mézard and Parisi, we calculate the associated random link values $\beta_{\rm RL}(d)$. For d=1, 2, 3, numerical results show that the random link approximation is a good one, with a discrepancy of less than 2.1% between $\beta_{\rm E}(d)$ and $\beta_{\rm RL}(d)$. For large d, we argue that the approximation is exact up to O(1d2) and give a conjecture for $\beta_{\rm E}(d)$, in terms of a power series in 1/d, specifying both leading and subleading coefficients.

Résumé
Le problème du voyageur de commerce (TSP) consiste à trouver le chemin fermé le plus court qui relie N "villes". Nous étudions le TSP euclidien où les villes sont distribuées au hasard de manière décorrélée dans l'hypercube de côté 1, en dimension d. En imposant des conditions aux bords périodiques et guidés par une universalité remarquable de la distribution des kièmes voisins, nous trouvons la longueur moyenne du chemin optimal $\langle L_{\rm E}\rangle =\beta_{\rm E}(d)N^{1-1/d}[1+O(1/N)] $ , avec $\beta_{\rm E}=$ 0,7120 $\pm$ 0,0002 et $\beta_{\rm E}(3)=$ 0,6979 $\pm$ 0,0002. Nous établissons ensuite des prédictions analytiques sur ces quantités à l'aide de l'approximation de liens aléatoires, où les longueurs entre les villes sont des variables aléatoires indépendantes. Grâce aux équations "cavité" développées par Krauth, Mézard et Parisi, nous obtenons dans le cas de liens aléatoires les valeurs, $\beta_{\rm RL}(d)$, analogues à $\beta_{\rm E}(d)$. Pour d= 1, 2, 3, les résultats numériques confirment que l'approximation de liens aléatoires est bonne, conduisant à un écart inférieur à 2,1% entre $\beta_{\rm E}(d)$ et $\beta_{\rm RL}(d)$. Pour d grand, nous donnons des arguments montrant que cette approximation est exacte jusqu'à l'ordre 1/d2 et nous proposons une conjecture pour $\beta_{\rm E}(d)$, exprimée en fonction d'une série en 1/d, dont on donne les deux premiers ordres.



© Les Editions de Physique 1997