The whole set as one number
Bitmask DP & State Compression
The analogy
When the state is "which of these ten cities have I already visited?", you can pack that entire set into a single integer where each bit is one city. Now a dictionary keyed by that number remembers every situation you have already solved.
Visualizer
The set as one number
step 1 / 9| mask (binary) | visited set | best cost ending at each city | |
|---|---|---|---|
| 1 | 0001 | {A} | computing… |
Travelling salesman over 4 cities. The state we need is "which cities have I visited, and where am I now?"state: (visited set, current city)
from functools import cache
def tsp(dist): # Held-Karp
n = len(dist)
FULL = (1 << n) - 1
@cache
def go(mask, i): # visited=mask, at city i
if mask == FULL:
return dist[i][0] # return home
best = float("inf")
for j in range(n):
if mask >> j & 1:
continue # already visited
best = min(best, dist[i][j] + go(mask | 1 << j, j))
return best
return go(1, 0) # O(2^n * n^2)
# assignment: popcount gives the row for free
def assign(cost):
n = len(cost)
@cache
def go(mask):
i = bin(mask).count("1") # which task we are on
if i == n:
return 0
return min(cost[i][j] + go(mask | 1 << j)
for j in range(n) if not mask >> j & 1)
return go(0)Check yourself
Held-Karp TSP is O(2^n · n²). Roughly what n is the practical ceiling?