Page 36Dynamic Programming
36 — TSP (DP/Bitmask)
Small n Held–Karp demo and 2ⁿ state explosion.
TSP DP / Bitmask
Small n demo starting from city 0. State = (visited mask, last city).
State explosion
dp[mask][j] = minimum cost to start at 0,
visit cities in mask, and end at j
transition:
dp[mask | (1<
Time: O(n²2ⁿ), Space: O(n2ⁿ). Excellent for small n, infeasible for large n.