Advanced DP: Bitmask & Tree DP

The Held-Karp Bitmask DP algorithm is the premier textbook demonstration of converting a factorial combinatorial explosion into a manageable exponential dynamic programming state space.

1. The Core Insight (Subproblem Overlap)

Suppose a drone visits cities in the order: 1 → 2 → 3 → 4.

Another candidate path visits cities in the order: 1 → 3 → 2 → 4.

Notice that in both cases, the set of visited cities is identical ({1, 2, 3, 4}), and the current ending city is identical (City 4)!

For future route choices (visiting the remaining cities 5 through 20), it does not matter how you traveled between 1, 2, and 3—all that matters is what is the minimum cost to have visited that exact subset and currently be sitting at City 4!

2. The State Definition

We define our DP state with two parameters: dp(mask, u)

• mask: An integer whose binary bits represent the subset of visited cities. If bit i is 1, City i has been visited. If bit i is 0, City i is unvisited.
• u: The current city where the drone is currently parked.

Transition:

To move to an unvisited city v (where (mask & (1 << v)) == 0):

dp(mask | (1 << v), v) = min(
    dp(mask | (1 << v), v),
    dp(mask, u) + dist[u][v]
)

Clean Python 3.12 Implementation with Memoization

from functools import lru_cache

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    ALL_VISITED = (1 << n) - 1

    @lru_cache(maxsize=None)
    def solve(mask: int, curr: int) -> int:
        # Base case: All cities have been visited -> return to starting city 0
        if mask == ALL_VISITED:
            return dist[curr][0]

        min_cost = float('inf')

        # Try visiting every unvisited city
        for nxt in range(n):
            if not (mask & (1 << nxt)):
                cost = dist[curr][nxt] + solve(mask | (1 << nxt), nxt)
                min_cost = min(min_cost, cost)

        return min_cost

    # Start at city 0 with only bit 0 set (1 << 0 = 1)
    return solve(1, 0)

Complexity Breakdown: From 10^17 down to 10^7

• Total Distinct States: $2^N$ masks $ imes N$ current cities = $N cdot 2^N$.
• Work per State: Loop over $N$ candidate next cities.
• Total Time Complexity: $O(N^2 cdot 2^N)$.

For $N = 20$:

• Brute force $19! pprox 1.21 imes 10^{17}$ operations (would take 3,800 years at 1 GHz).
• Held-Karp $20^2 cdot 2^{20} = 400 imes 1,048,576 pprox 4.19 imes 10^8$ operations (runs in under 1.5 seconds on a modern CPU)!