Dynamic Programming • Bitmask

Traveling Salesperson Problem (TSP)

Find the shortest possible route that visits every node exactly once and returns to the origin node. We use Bitmask DP to reduce O(N!) time to O(N² * 2^N).

Try Interactive Simulator

Overview

Naive TSP checks all permutations of paths, taking `O(N!)`. This becomes impossible around N=12. DP with Bitmasking allows us to solve up to N=20.

The State

The state needs two things: `u` (Where are we currently?) and `mask` (Which nodes have we already visited?).

The Transition

From node `u`, try visiting every unvisited node `v`. The cost is `dist[u][v] + tsp(v, mask | (1 << v))`.

The Base Case

When `mask == (1 << N) - 1`, all bits are 1, meaning all nodes are visited. The only thing left is to return to the start node (usually Node 0), so return `dist[u][0]`.

Current Node: 0

Mask: 001

0

1

2

Code Tracker

:::

1function tsp(u, mask) {

2 // All nodes visited

3 if (mask === (1 << N) - 1) {

4 return dist[u][0];

5 }

6 if (dp[u][mask] !== -1) return dp[u][mask];

7

8 let ans = Infinity;

9 for (let v = 0; v < N; v++) {

10 // If node v is not visited yet

11 if ((mask & (1 << v)) === 0) {

12 let cost = dist[u][v] + tsp(v, mask | (1 << v));

13 ans = Math.min(ans, cost);

14 }

15 }

16 return dp[u][mask] = ans;

17}

Tsp

Tsp

Traveling Salesperson Problem (TSP)

Overview

The State

The Transition

The Base Case

Traveling Salesperson Problem (TSP)

Overview

The State

The Transition

The Base Case