The N-city travelling salesman problem: statistical mechanics and metropolis algorithm

In any N-city travelling salesman problem there are (N-1)!/2 possible tours. We use the Metropolis algorithm to generate a sequence of such tours. This sequence may be viewed as the random evolution of a physical system in contact with a heat-bath. As the temperature is lowered, the tours gererated approach the optimal tour. It appears for large N one arrives within a few percent of the optimal solution in better than quadratic time.


Published in:
SIAM Review, 26, 4, 177-193
Year:
1984
Note:
PRO 84.05
Laboratories:




 Record created 2006-02-13, last modified 2018-01-27


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)