The classic tour problem
The traveling salesman problem, or TSP, asks for the shortest route that visits every city once and returns to the start. It is the optimization cousin of the Hamiltonian cycle question, and it is famously hard. The number of possible tours grows faster than any polynomial, so brute force collapses quickly.
Exact methods
For small inputs we can be exact.
- Brute force tries every ordering, accurate but only viable for a handful of cities.
- Dynamic programming over subsets, the Held Karp method, remembers the best way to reach a subset ending at a given city. It is far faster than brute force yet still grows exponentially.
- Branch and bound prunes whole groups of tours once a partial route already exceeds the best found.
Practical approximations
When the distances obey the triangle inequality, a detour never beats going direct, and good shortcuts appear. A minimum spanning tree can be doubled and shortcut to give a tour within twice the optimal. The cleverer Christofides construction guarantees a tour within one and a half times the best.
Heuristics for scale
For thousands of cities people use construction heuristics then local improvement such as swapping two edges to uncross the route, accepting a near optimal answer.
Key idea
The traveling salesman problem is solved exactly only for small inputs, while large instances rely on bounded approximations and improvement heuristics.