An NP-hard problem is at least as difficult as the hardest problems in NP; no polynomial-time solution is known for arbitrary inputs. The traveling salesman problem makes the idea concrete: finding a shortest route through every city becomes dramatically harder as the city count grows. section 8.2
A practical treatment of the traveling salesman problem proceeds by:
- Representing cities as graph vertices and pairwise distances as edges. section 8.2
- Generating every city ordering with recursive backtracking and permutations. section 8.2
- Closing each ordering into a cycle, calculating its distance, and retaining the shortest route. section 8.2
Five Vermont cities
For Rutland, Burlington, White River Junction, Bennington, and Brattleboro, brute force tests every permutation. It finds a 318-mile cycle: Bennington, Brattleboro, White River Junction, Burlington, Rutland, then Bennington. section 8.2
Table 8.2. Driving distances between cities in Vermont
| Rutland |
Burlington |
White River Junction |
Bennington |
Brattleboro |
|
|---|---|---|---|---|---|
| Rutland | 0 | 67 | 46 | 55 | 75 |
| Burlington | 67 | 0 | 91 | 122 | 153 |
| White River Junction | 46 | 91 | 0 | 98 | 65 |
| Bennington | 55 | 122 | 98 | 0 | 40 |
| Brattleboro | 75 | 153 | 65 | 40 | 0 |
A distance table makes the complete graph and each candidate route’s cost directly inspectable. section 8.2
