Presets
Playback
Map
Number of cities and map seed. Click the map to add, shift-click to remove, drag to move.
Run settings
Speed of the animation and the annealing schedule.
Layers
Model checks
The science
The problem
Given N cities, find the shortest closed route that visits each exactly once. There are (N-1)!/2 distinct tours (10^155 for 100 cities), and no known algorithm solves every instance in polynomial time: the decision version is NP-complete.
Heuristics shown
Nearest neighbour always walks to the closest unvisited city (typically 20-25 % above optimal). Greedy edge adds the shortest remaining edge that keeps every city at degree two and creates no early cycle (about 14-20 % above). 2-opt repeatedly removes two edges and reconnects the tour the other way when that is shorter; it ends in a local optimum where no such move helps (about 5 % above). Or-opt moves segments of one to three cities. Simulated annealing accepts a worsening 2-opt move with probability exp(-dL / T) while the temperature T falls geometrically, which lets it escape local optima.
Exact solution and bounds
The Held-Karp dynamic programme computes the optimum in O(N^2 2^N) time by building the best path over every subset of cities ending in each city; it is practical here up to N = 13. A lower bound comes from the 1-tree: the minimum spanning tree of all cities except one, plus that city's two shortest edges. Any tour contains such a structure, so 1-tree <= optimum. Doubling the minimum spanning tree gives the classic upper bound optimum <= 2 MST (a 2-approximation).
Random maps
For N uniform random points in a unit square the optimal tour length approaches 0.7124 sqrt(N A) (Beardwood-Halton-Hammersley), with A the area. The page uses that scale only as an intuition; small maps deviate noticeably from the limit.
Honest simplifications
Euclidean distances on a flat map, symmetric costs, all cities visited, one salesperson. The search steps shown are the algorithm's accepted moves, not CPU time. The 1-tree bound used here tries up to 12 choices of the excluded city and is not the stronger Held-Karp ascent bound used by real solvers such as Concorde.
What to try
- Run Nearest neighbour, then 2-opt, then Or-opt on the same map and compare the bars in the second graph.
- "Exact: 11 cities" lets Held-Karp show the true optimum (blue dashed line in graph one); see how far each heuristic is from it.
- Drag a city or click to add one: every bound and optimum is recomputed.
- Look at the third graph to see why brute force dies near 15 cities while Held-Karp lasts to about 25.