Loading...
research article
The N-city travelling salesman problem: statistical mechanics and metropolis algorithm
Bonomi, E.
•
Lutton, J.
1984
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.
Type
research article
Web of Science ID
WOS:A1984TP23400003
Authors
Bonomi, E.
•
Lutton, J.
Publication date
1984
Published in
Volume
26
Issue
4
Start page
177
End page
193
Note
PRO 84.05
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 13, 2006
Use this identifier to reference this record