Simulated Annealing

There is a very famous problem in computer science known as the Travelling Salesman Problem: 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, the Travelling Salesman Problem is actually an example of an NP-hard problem. The technical definition of this is tricky, but it essentially means that people are relatively agreed that there is 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 whose order it thinks about swapping. If that makes the entire path shorter, it makes the swap. If it makes the path longer, though, it will still sometimes make the swap. The frequency with which it does this depends on the temperature of the system — just a number in the algorithm, but a number that is analogous to actual temperature in very hot metal. The algorithm’s temperature starts at a very high level 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. 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 the same and only take swaps that improve its position.

Maximum speed