Traveling Salesman Problem (TSP): fast tours that are provably not too bad

How to read this

Accuracy ratio. For a tour s_a built by a heuristic, r(s_a) = f(s_a) / f(s*), where f(s*) is the optimal length. r = 1.00 means optimal; r = 1.25 means 25% longer. The exact optimum is computed by exhaustive search, which is only feasible for n ≤ 9 here: (n − 1)!/2 = 20,160 tours at n = 9. For larger n the table shows f / w(MST) instead, an upper estimate of r, because an optimal tour is always longer than the MST.

Guarantees for Euclidean instances (Levitin §12.3): nearest neighbor and multifragment satisfy r ≤ ½(⌈log₂ n⌉ + 1); twice-around-the-tree r < 2; true Christofides (with a minimum-weight matching) r ≤ 1.5. This page pairs odd vertices greedily instead, which is simpler to watch but loses the 1.5 proof. 2-opt has no general guarantee, yet usually lands within a few percent.

Pictures. Blue edges are the MST; purple dashed edges are the matching; the orange path is the tour under construction; in 2-opt, red dashed edges are removed and green ones added by a 2-change.

Try this

1. Nearest neighbor depends on the start. On the Example, change the start city and watch the length in the table. Which start gives the worst tour, and where is its long last leg?
2. Trap nearest neighbor. Put cities evenly on a line and one far away off to the side; nearest neighbor walks down the line and pays for a long return edge.
3. Twice-around-the-tree. Check the bound live: the walk length is exactly 2·w(MST), and the tour after shortcuts is never longer than the walk (triangle inequality).
4. 2-opt as a polisher. Watch each 2-change remove two crossing edges: after 2-opt no two tour edges cross. Compare its r with the nearest-neighbor tour it started from.
5. Beyond exact. Make 12 random cities. Exhaustive search would need 11!/2 ≈ 20 million tours; the heuristics finish instantly. Which one wins most often on random instances?