239. What approaches exist for the traveling salesman problem?
HardGraph algorithms
Technical
Show model answer
Brute force tries all (n − 1)!/2 tours of a symmetric instance, O(n!). The Held-Karp dynamic program stores the cheapest path that starts at city 0, visits set S and ends at city j; each state extends from a smaller set, giving O(n²·2ⁿ) time and O(n·2ⁿ) space, feasible to about 20 cities.
TSP is NP-hard, so large instances use approximation or heuristics. For metric TSP (triangle inequality), doubling an MST gives a 2-approximation and Christofides' algorithm (MST plus minimum perfect matching on odd-degree vertices) gives 1.5. Practical solvers use nearest neighbor construction plus 2-opt or Lin-Kernighan improvements, or branch-and-bound with LP relaxations for exact answers.