Traveling Salesman DP (Held–Karp Bitmask)

Traveling Salesman DP dp[mask][i] visits all cities once—O(n^2 2^n); Held–Karp baseline for small n.

Why this shows up in the real world

Drone inspection routes for small hubs. PCB probe ordering for tiny nets.

Core idea (explained for students)

Initialize dp[1<<i][i]=0; transition add edge cost; answer min over ending city at full mask.

Try this in Python

def tsp_small(dist: list[list[int]]) -> int:
    n = len(dist)
    FULL = (1 << n) - 1
    dp = [[10**18] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)) or dp[mask][u] >= 10**17:
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                nm = mask | (1 << v)
                dp[nm][v] = min(dp[nm][v], dp[mask][u] + dist[u][v])
    return min(dp[FULL][j] + dist[j][0] for j in range(1, n))


print(tsp_small([[0, 2, 9], [1, 0, 6], [15, 7, 0]]))

Common mistakes

• Using float distances without tolerance—ties fragile.
• Starting city symmetry—fix start to avoid divide-by symmetry duplicates optionally.

Key takeaways

• Bitmask full = (1<<n)-1 check in answer loop.