Bitmask DP — TSP intro: Visual walkthrough — Coding deep dive

We use one running example the whole way down. Four cities on a plane:

$0, 1, 2, 3$

with symmetric distances (edge $i \to j$ costs the same as $j \to i$ ):

$dist [0] [1] = 2, dist [0] [2] = 9, dist [0] [3] = 10,$ $dist [1] [2] = 6, dist [1] [3] = 4, dist [2] [3] = 3.$

Here $dist [i] [j]$ just means "the number written on the road between city $i$ and city $j$ ." Nothing more.

Step 1 — Draw the world we are optimising

WHY start by drawing? Because every abstract symbol below ( $mask$ , $dp$ , "current city") is a fact about this map. If you can point at it on the map, you understand it. If you can't, you don't.

PICTURE. The four cities are dots; the ten roads are gray with their costs. A tour is a loop that touches every dot once. There are $(4 - 1)! /2 = 3$ genuinely different loops here — few enough to check by hand later, which is exactly why 4 cities is a good teaching size.

Step 2 — Turn "which cities are done" into a single integer

WHY integers and not, say, a Python set? Because our table needs an index — a slot number. An integer is the cheapest slot number that exists. The set ${0, 1}$ becomes the switch row 0011, which as an ordinary number is $1 + 2 = 3$ . So "the set of visited cities" and "the number $3$ " are the same object seen two ways.

PICTURE. A strip of four switches. Below each switch we write its value. The visited set ${0, 2}$ lights switches $0$ and $2$ , giving 0101 $= 1 + 4 = 5$ .

See Bit Manipulation if any of these three lines feels shaky — they are the entire vocabulary we need.

Step 3 — Name the table cell: `dp[mask][i]`

WHAT. One number per (switch-row, current-city) pair. A grid: rows are the $2^{4} = 16$ switch-rows, columns are the $4$ possible "current city" values.

WHY this shape? This is the whole magic of the parent note. A path is a long story ( $0 \to 2 \to 1 \to \dots$ ). But the only two facts that affect what happens next are the SET already done and the SPOT you're on. Every story with the same (SET, SPOT) is interchangeable from here — so we keep just the cheapest and forget the rest. That forgetting is what shrinks $n!$ down to a grid of size $n 2^{n}$ .

PICTURE. A blank $16 \times 4$ grid. Most cells are impossible and painted gray: dp[mask][i] only makes sense if city $i$ 's switch is ON in $mask$ (you can't "end at $i$ " if you never visited $i$ ). Look — exactly half-ish of the grid is legal.

Step 4 — Plant the seed: the base case

WHAT. Set exactly one legal cell to $0$ ; leave all others $\infty$ .

WHY $0$ ? You start at city $0$ having spent nothing and visited nobody but yourself. The switch row is 0001 (only switch $0$ lit) $= 1$ . Cost so far: $0$ roads walked $= 0$ .

PICTURE. The grid from Step 3 with a single green $0$ dropped into row 0001, column $0$ . Every other cell is still $\infty$ . This lone seed is the ancestor of every number we compute after it.

Step 5 — The one rule: grow a path by its last edge

Now the engine. To fill a cell dp[mask][i], ask: who did I visit right before $i$ ?

WHY is this allowed? Optimal substructure. Any cheapest path ending at $i$ has some last-visited city $j$ . Chop off that final road $j \to i$ ; the leftover prefix must itself be a cheapest path to $(prev, j)$ — if a cheaper prefix existed we'd glue it on and beat our own minimum, a contradiction. This is the same logic that makes all Dynamic Programming legal.

PICTURE. One target cell (orange), fed by arrows from the cells one switch smaller. We are literally peeling the last edge and reading the already-filled predecessors. This is Held-Karp Algorithm in a single frame.

Step 6 — Run the engine on our map, layer by layer

WHAT. Fill cells in order of how many switches are lit — because a cell only ever depends on cells with fewer switches. So process popcount $= 1$ , then $2$ , then $3$ , then $4$ . (popcount = how many switches are ON.)

WHY this order? It guarantees every $dp [prev] [j]$ we read on the right-hand side was already finalised on a previous layer. No cell is used before it's ready.

PICTURE — the numbers appearing. Watch each layer light up (recall dist: $01 = 2, 02 = 9, 03 = 10, 12 = 6, 13 = 4, 23 = 3$ ):

Layer 1 (seed): dp[0001][0]=0.
Layer 2 — one hop out of $0$ :

$dp [0011] [1] = 0 + 2 = 2, dp [0101] [2] = 0 + 9 = 9, dp [1001] [3] = 0 + 10 = 10.$

Layer 3 — two cities besides $0$ , e.g. set ${0, 1, 2} = 0111$ , end at $2$ :

$dp [0111] [2] = min (2 dp [0011] [1] + 6 dist [1] [2], illegal, j \neq = i dp [0101] [2]?) = min (2 + 6) = 8.$

Here only $j = 1$ is legal (we need $j \in prev = {0, 1}$ and $j \neq = 2$ ; $j = 0$ would need dp[0101][0] which doesn't reach through $2$ ... careful: $prev = {0, 1}$ , so $j \in {0, 1}$ ):

$dp [0111] [2] = min (dp [0011] [0] + dist [0] [2], dp [0011] [1] + dist [1] [2]) .$

But dp[0011][0] is $\infty$ (you can't stand at $0$ with ${0, 1}$ visited via this DP's forward growth reaching $0$ ), so the live term is $2 + 6 = 8$ . ✓

Step 7 — Fill the full layer, then close the tour

WHAT. Compute the three cells dp[1111][1], dp[1111][2], dp[1111][3], add the road home, take the smallest.

For our numbers the optimal closed tour is $0 \to 1 \to 3 \to 2 \to 0$ :

$2 (0 \to 1) + 4 (1 \to 3) + 3 (3 \to 2) + 9 (2 \to 0) = 18.$

WHY add $dist [i] [0]$ ? A tour is a cycle (see Hamiltonian Path and Cycle). The DP only walked out to everyone; it never paid to come back. Forgetting this return road is trap #3 in the parent. If you wanted a Hamiltonian path instead of a cycle, drop this term and answer $min_{i} dp [1111] [i]$ .

PICTURE. The three full-layer cells with their home-roads drawn as dashed arrows back to $0$ ; the winning $18$ highlighted, its actual loop traced on the map.

Step 8 — Edge & degenerate cases (never leave a hole)

Worked example The cases you must not be surprised by

$n = 1$ . One city, already home. $full = 1$ , base dp[1][0]=0, no other city to close from → tour cost $0$ . The min(... for i in 1..n) loop is empty; guard it or define the answer as $0$ .
$n = 2$ . Cities $0, 1$ . Only route: $0 \to 1 \to 0$ costs $dist [0] [1] + dist [1] [0]$ . DP: dp[11][1]=dist[0][1], close with +dist[1][0]. ✓
Asymmetric roads ( $dist [i] [j] \neq = dist [j] [i]$ ). Nothing breaks — the DP never assumed symmetry; it always uses the directed edge $dist [j] [i]$ for the arrival and $dist [i] [0]$ for the return. Our example was symmetric only to make hand-checking easy.
Missing road (no edge $i \to j$ ). Store $dist [i] [j] = \infty$ ; the $min$ naturally rejects any path forced through it. If every full-layer close is $\infty$ , no Hamiltonian cycle exists.
Unreachable cell. Cells still $\infty$ after processing are impossible states — the code's if dp[mask][i]==INF: continue skips them, saving work. This is a mini Branch and Bound idea: prune the dead.

PICTURE. Four tiny grids side by side: $n = 1$ (single seed = answer), $n = 2$ (two-cell chain), an asymmetric arrow pair, and a broken road drawn as a red $\infty$ that the $min$ skips.

The one-picture summary

Everything above, compressed: the seed at bottom, arrows flowing up the layers as switches turn on one at a time (each arrow = " $+ dist [j] [i]$ , keep the min"), and the dashed home-roads at the top closing the cycle. The whole Held-Karp Algorithm is water flowing uphill through a lattice of switch-rows, then falling home.

Recall Feynman: the whole walkthrough in plain words

I drew four houses and the roads between them (Step 1). Instead of remembering full walks, I put four light switches on a sticky note — one per house — and flipped a switch on when I visited that house; the whole row of switches read as a single number is the "mask" (Step 2). My scratch grid has one box for every (switch-row, house-I'm-in-now) pair, and boxes claiming I ended in a house whose switch is off are nonsense, so I gray them out (Step 3). I dropped a single $0$ in the box "only-home-switch-on, standing-at-home" — the seed of everything (Step 4). My one rule: to fill any box, I peel off the last road I walked, look up the already-filled box for "one house earlier," and add that road's cost, keeping only the cheapest predecessor (Step 5). I filled boxes in waves — one switch on, then two, then three, then all four — so every box I read was already done (Steps 6–7). Once all switches were on I paid one last road back home and took the smallest total: $18$ (Step 7). Finally I checked the weird cases — one city, two cities, one-way roads, broken roads — so nothing can surprise me (Step 8).

Recall

In dp[mask][i], what does mask physically mean and why an integer? ::: The set of already-visited cities, stored as light switches (bit i on ⟺ city i visited). It's an integer because the DP table needs a cheap index. Why fill cells in increasing popcount order? ::: Each cell depends only on cells with one fewer switch on, so processing by number-of-switches guarantees predecessors are ready. Why the final +dist[i][0]? ::: A tour is a cycle; the DP only walked outward, so we pay one last road home. Drop it for a Hamiltonian path. What is the optimal tour cost in the running example? ::: 18, via 0→1→3→2→0.

Connections

Parent: Bitmask DP — TSP intro
Dynamic Programming · Travelling Salesman Problem · Held-Karp Algorithm
Bit Manipulation · Subset Enumeration · Hamiltonian Path and Cycle · Branch and Bound