« Reading List: Influx | Main | Google Chrome Drops Support for Setting Cookies with "meta http-equiv" »
Thursday, June 14, 2018
Simulated Annealing: The Travelling Salesman Problem
The travelling salesman problem—finding the shortest itinerary to visit each of a number of cities—is a classic of combinatorial optimisation. Finding optimal solutions by brute force is effectively impossible: there are more than 1032 possible paths to visit thirty cities, and if you could test a billion paths a second, it would take 600,000 times the age of the universe to compare them all and choose the shortest.
If you don't require an absolutely optimal solution, but rather one that's within a few percent of the best possible, there are a number of optimisation techniques which will get the job done. A new interactive page, Simulated Annealing: The Travelling Salesman Problem, explores one of the most elegant, simulated annealing. By analogy to creating large scale order by annealing metal, random perturbations to a path, performed according to a schedule where the degree of perturbation (“temperature”) steadily decreases, finds near-optimal solutions to even very large problems. You can experiment with the cost function and observe its effect on the solutions found. A number of standard test cases, some of which have known optimal solutions, are included.
This page runs entirely within your browser using JavaScript and HTML5 canvas graphics. There is no need to download, build, or install any software to use it.
Posted at June 14, 2018 13:55