| 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 〈LE〉=βE(d)N1-1/d[1+O(1/N)] with βE=0.7120±0.0002 and βE(3)=0.6979±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 β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 βE(d) and βRL(d). For large d, we argue that the approximation is exact up to O(1d2) and give a conjecture for βE(d), in terms of a power series in 1/d, specifying both leading and subleading coefficients. |
Récupérer au format
