Senior LevelData Structures & Algorithms
What is Bitmask Dynamic Programming and how does it solve the Travelling Salesman Problem?
ā Interview Prompt: Explain Bitmask DP for subset enumeration, apply it to TSP in O(2^N Ć NĀ²), and discuss when bitmask DP is appropriate.
Bitmask DP uses an integer bitmask to represent a subset of elements as a DP state, allowing $O(2^N \times N)$ or $O(2^N \times N^2)$ algorithms for small $N$ (typically $N \leq 20$).
TSP (Travelling Salesman Problem):
dp[mask][i] = minimum cost to visit all cities in mask (bitmask), ending at city i.
```
dp[mask | (1<<j)][j] = min(dp[mask][i] + cost[i][j])
```
ā¢
Time: $O(2^N \times N^2)$, Space: $O(2^N \times N)$.
ā¢
TSP is NP-Hard; bitmask DP is exact but only feasible for $N \leq 20$.
Code Implementation Example
typescript
function tspBitmask(cost: number[][]): number {
const n = cost.length;
const INF = Infinity;
const dp: number[][] = Array.from({ length: 1 << n }, () => new Array(n).fill(INF));
dp[1][0] = 0; // Start at city 0, visited = {0}
for (let mask = 1; mask < (1 << n); mask++) {
for (let u = 0; u < n; u++) {
if (!(mask & (1 << u)) || dp[mask][u] === INF) continue;
for (let v = 0; v < n; v++) {
if (mask & (1 << v)) continue; // already visited
const nextMask = mask | (1 << v);
dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + cost[u][v]);
}
}
}
const fullMask = (1 << n) - 1;
let ans = INF;
for (let u = 1; u < n; u++) ans = Math.min(ans, dp[fullMask][u] + cost[u][0]);
return ans;
}š”TSP Bitmask DP ā O(2^N Ć NĀ²) exact solution for N ā¤ 20.
šÆ Interview Key Takeaway
Bitmask DP encodes subset membership as integer bits. For N ā¤ 20, it provides exact polynomial-in-N-squared Ć exponential-in-N solutions to NP-Hard problems.
#DSA#Bitmask DP#TSP#Advanced#Senior
Back to all Data Structures & Algorithms Questionsā