DPDynamic Programming
Bitmask DP (TSP)
State is a bitmask encoding which of n ≤ ~20 elements are used, plus optionally the last element; transitions add one bit.
| end 0 | end 1 | end 2 | end 3 | |
|---|---|---|---|---|
| 0000 | ∞ | ∞ | ∞ | ∞ |
| 0001 | 0 | ∞ | ∞ | ∞ |
| 0010 | ∞ | ∞ | ∞ | ∞ |
| 0011 | ∞ | ∞ | ∞ | ∞ |
| 0100 | ∞ | ∞ | ∞ | ∞ |
| 0101 | ∞ | ∞ | ∞ | ∞ |
| 0110 | ∞ | ∞ | ∞ | ∞ |
| 0111 | ∞ | ∞ | ∞ | ∞ |
| 1000 | ∞ | ∞ | ∞ | ∞ |
| 1001 | ∞ | ∞ | ∞ | ∞ |
| 1010 | ∞ | ∞ | ∞ | ∞ |
| 1011 | ∞ | ∞ | ∞ | ∞ |
| 1100 | ∞ | ∞ | ∞ | ∞ |
| 1101 | ∞ | ∞ | ∞ | ∞ |
| 1110 | ∞ | ∞ | ∞ | ∞ |
| 1111 | ∞ | ∞ | ∞ | ∞ |
1/17dp[mask][u] = shortest path that visits exactly the nodes in mask (bit i = node i, shown as a binary string, low bit rightmost) and ends at u. Start: only node 0 visited, cost 0.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Bitmask DP →
1dp[1][0] = 0 // visited {0}, ending at 02for mask in increasing order, for u in mask with dp[mask][u] < ∞:3 for v not in mask:4 dp[mask | 1<<v][v] = min(dp[mask | 1<<v][v], dp[mask][u] + d[u][v])5answer = min over u of dp[FULL][u] + d[u][0]Variables
n4
masks16
Complexity
worst O(2^n · n²) for TSP-style (mask, last) states; O(2^n · n) for dp[mask] with one-bit transitions; O(3^n) for submask enumeration
space O(2^n · n) or O(2^n)
Speed