Home/Questions/Q 3531
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:52:42-05:00 In: ,

Traveling Salesperson Problem: How does Bitmask DP reduce (N – 1)! factorial to O(N^2 * 2^N)?

We are building an autonomous drone route planner that must visit N = 20 delivery drop points with minimum total travel distance.

Brute-force testing all permutations is (N - 1)!. For N = 20, $19! pprox 1.21 imes 10^{17}$, which would take hundreds of years of CPU time. The classic Held-Karp algorithm uses Bitmask Dynamic Programming to solve this in O(N^2 * 2^N). How does an integer bitmask represent subsets of cities, and how does the state transition work?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Anonymous
    Begginer

    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)!
    • 0
  2. Abhishek
    Begginer

    Here is the iterative bottom-up C++20 Bitmask DP (Held-Karp) implementation for TSP.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <algorithm>

const int INF = 1e9;

int tspHeldKarp(const std::vector<std::vector<int>>& dist) {
    int n = dist.size();
    int total_masks = 1 << n;
    // dp[mask][curr_city]
    std::vector<std::vector<int>> dp(total_masks, std::vector<int>(n, INF));

    // Base case: start at city 0
    dp[1][0] = 0;

    for (int mask = 1; mask < total_masks; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;

            // Transition to next unvisited city v
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v))) {
                    int next_mask = mask | (1 << v);
                    dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    // Return to start city 0
    int ans = INF;
    int final_mask = total_masks - 1;
    for (int u = 1; u < n; ++u) {
        ans = std::min(ans, dp[final_mask][u] + dist[u][0]);
    }
    return ans;
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    std::cout << "Minimum TSP Tour Distance: " << tspHeldKarp(matrix) << "n";
    return 0;
}

    Complexity: Runs in O(N^2 * 2^N) time, solving N=20 in ~1 second.

    • 0