Simulated Annealing

The Travelling Salesman Problem: is a famous one. Given a list of cities and their locations on a map, what is the shortest total route that passes through all of them and ends where it begins? Although it may seem simple on the surface, it’s is actually an example of an NP-hard problem. Nailing down exactly what that means is tricky, but roughly speaking, most people are mostly agreed that there’s no “quick” algorithm to solve the problem.

There are plenty of ways to quickly approximate it, though. One of them, called simulated annealing, takes inspiration from metallurgy. The algorithm starts by choosing a random path through the cities, and then it picks two cities at random and thinks about swapping them. It always does if that swap makes the entire path shorter, but even if it makes the path longer, it still sometimes makes the swap. The chance that it does depends on the temperature of the system — a number in the algorithm that’s analogous to actual temperature in very hot metal. The algorithm’s temperature starts very large and cools down over time — shown as red nodes fading to white — and the probability that the walk becomes longer lowers with it. This seemingly chaotic strategy ensures that the algorithm doesn’t just get stuck in a nonoptimal state where any swap will lead to a longer walk, but there are still shorter paths possible. Instead, it has the freedom to move around and try lots of different strategies at first, but as the temperature lowers, it’s forced to stay relatively still and only take swaps that improve its position.

Maximum speed

Double-click canvas to enter fullscreen