查看文章

This paper presents an algorithm for the traveling salesman problem in k-dimensional Euclidean space. For n points independently uniformly distributed in a set , we show that, for any choice of a function of n increasing to infinity with n more slowly than n, we can adjust the algorithm so that, in probability, the time taken by the algorithm will be of order less than that of as . The algorithm puts the n points in a cyclic order, and we also show that, with probability one, the length of the corresponding tour (that is, the sum of the n distances between adjacent points in the order given) will be asymptotic to the minimal tour length as . The latter is known (also with probability one) to be asymptotic to , where is a constant depending only on the dimension k, is the volume of the set , , and . Our result is stronger, and the algorithm is faster, than any other we have been able …