Exercises — Bitmask DP — TSP intro

A mask is just an integer whose binary digits are tick-boxes. Bit $i$ set ⟺ city $i$ visited. $22=16+4+2=2^4+2^2+2^1$. Binary over 5 bits (bit4…bit0): 10110. Reading right-to-left: bit0=0, bit1=1, bit2=1, bit3=0, bit4=1. Visited cities: $\{1,2,4\}$ — three cities.

Recall 1<<i $=2^i$ = "the integer with only bit $i$ on". (a) 1<<2 = 4; 22 & 4 = 4 (non-zero) → city 2 IS visited. (b) 1<<3 = 8; 22 & 8 = 0 → city 3 is NOT visited. (c) 1<<0 = 1; 22 | 1 = 23 → add city 0, giving $\{0,1,2,4\}$. (d) ~(1<<1) clears bit1; 22 & ~2 = 20 → remove city 1, giving $\{2,4\}$.

Masks range $0\dots 2^n-1$, so $2^n$ masks; current city $i$ has $n$ choices → $n{2}^n$ table slots. A slot is meaningful only if bit $i$ is set in mask (you can't "end at" an unvisited city). For a fixed $i$, exactly half the masks have bit $i$ on: $2^{n-1}$. Over all $i$: $n{2}^{n-1}$ reachable slots. For $n=4$: table $=4\cdot 16=64$ slots, reachable $=4\cdot 8=32$.

dp[1][0] = 0 — that is dp[001][0]: only city 0 visited, standing at 0, cost 0. Everything else is $\infty$ because at the start there is no path that has already visited other cities. An entry $\text{dp}[\text{mask}][i]=\infty$ literally means "this situation is not yet reachable." As the DP progresses these fill in.

Base: dp[001][0]=0. Peel-the-last-edge transition: $\text{dp}[\text{mask}][i]={\min }_{j\in \text{prev}}(\text{dp}[\text{prev}][j]+\text{dist}[j][i])$, $\text{prev}=$ mask & ~(1<<i).

Close the cycle (add return edge to 0): $\min (\underset{9+9=18}{\underbrace{9+\text{dist}[2][0]}},\underset{13+5=18}{\underbrace{13+\text{dist}[1][0]}})=18.$ Both orders $0\to 1\to 2\to 0$ and $0\to 2\to 1\to 0$ cost $5+4+9=18$. Answer: 18. ✓

Check endpoint is legal: bit2 of 0111 is 1 ✓ (city 2 is visited). prev = 7 & ~(1<<2) = 0111 & 1011 = 0011 $=\{0,1\}$. Valid predecessors are cities in prev: $j\in \{0,1\}$. $\text{dp}[7][2]=\min (\text{dp}[3][0]+\text{dist}[0][2],\text{dp}[3][1]+\text{dist}[1][2]).$ City 3 is not in prev (bit3 = 0), so it is not a candidate — you cannot have come from a city you never visited.

The remaining cost — the cost of finishing the tour — depends only on (a) which cities still need visiting (= complement of mask) and (b) where you currently stand (city $i$). Both are captured by $(\text{mask},i)$. The internal order of the already-visited prefix affects only the prefix's own accumulated cost, which is already stored as the value $\text{dp}[\text{mask}][i]$. So two paths reaching the same $(\text{mask},i)$ are interchangeable from here on; we keep the cheaper value and discard the other. This is the memorylessness that makes the state small: $n{2}^n$ states instead of $n!$ orderings. See figure below.

(i) States $=n{2}^n=13\cdot 2^{13}=13\cdot 8192=106,496$. (ii) Transitions $\approx n^2{2}^n=169\cdot 8192=1,384,448$ (about $1.4\times 10^6$) — trivial for a computer. (iii) $13!=6,227,020,800\approx 6.2\times 10^9$. Ratio $13!/(n^2{2}^n)\approx 6.2\times 10^9/1.4\times 10^6\approx 4.5\times 10^3$. Bitmask DP does about 4500× less work here — and the gap widens explosively with $n$.

Suppose the best path to $(\text{mask},i)$ ends with edge $j\to i$, and its prefix (a path to $(\text{prev},j)$) had cost $c$. If there existed a cheaper path to $(\text{prev},j)$ of cost $c^{\prime }<c$, we could glue edge $j\to i$ onto it and obtain a path to $(\text{mask},i)$ of cost $c^{\prime }+\text{dist}[j][i]<c+\text{dist}[j][i]$ — beating the supposed best. Contradiction. Hence the prefix must already be optimal, i.e. equal to $\text{dp}[\text{prev}][j]$. This "cut-and-paste" is exactly the optimal-substructure property that legalises the recurrence.

Drop the return term; answer $={\min }_i\text{dp}[\text{full}][i]$ over all $i$ (including $i=0$? no — city 0 is the fixed start, so $i\ne 0$ here since the path must end elsewhere after visiting all). From L2.2: dp[111][1]=13, dp[111][2]=9. $\min (13,9)=9$, achieved by ending at city 2 via route $0\to 1\to 2$. This is cheaper than the cycle (18) precisely because we skipped the expensive return edge $2\to 0=9$. This is the Hamiltonian Path and Cycle distinction in action.

We want $\text{dp}[\text{full}][1]$ directly — no min over endpoints, because the endpoint is pinned to 1. full = 111. From L2.2, dp[111][1] = 13 (route $0\to 2\to 1$: $9+4=13$). The only other way to end at 1 having visited all is $0\to ?\to 1$; the sole "middle" city is 2, so $0\to 2\to 1$ is forced. Answer: 13. Lesson: pinning the endpoint means reading one table cell instead of minimising.

Here dist[j][i] ≠ dist[i][j], so direction matters — this is why the transition uses dist[j][i] not dist[i][j].

Close: $\min (\underset{3+3=6}{\underbrace{3+d[2][0]}},\underset{15+7=22}{\underbrace{15+d[1][0]}})=6$. Winning tour $0\to 1\to 2\to 0$ costs $2+1+3=6$. The reverse $0\to 2\to 1\to 0=6+9+7=22$. Directions differ wildly — answer 6, and only the DP's directional dist[j][i] catches this.

No optimality is lost. A closed tour is a cycle; a cycle has no distinguished starting point — it visits the same edges regardless of which vertex you call "start." So the optimal cycle passes through city 0, and rotating our labelling to begin the traversal at 0 describes the same cycle with the same cost. Hence fixing start $=0$ still finds the global optimum. (Caveat: this holds for the cycle version. For a path with a free start, you would loop the base case over all start cities, multiplying the work by $n$.)

For $n=3$ there are exactly $(n-1)!/?$ — precisely 2 directed closed tours from city 0: $0\to 1\to 2\to 0$ and $0\to 2\to 1\to 0$. With symmetric distances both traverse the same three edges $\{01,12,20\}$ in opposite directions, so they always cost the same $d_{01}+d_{12}+d_{02}$. Here that is $5+4+9=18$, achieved by both tours. Generalisation: for symmetric $n=3$, the two tours are mirror images and always tie — there are always exactly 2 optimal directed tours (or you may count them as 1 undirected tour). A strict single winner appears only when distances are asymmetric, breaking the mirror symmetry (as in L4.3, where 6 ≠ 22).

Correctness of increasing order: the forward push updates dp[nm][k] from dp[mask][i] where nm = mask | (1<<k) and bit $k$ was not in mask. Setting a previously-zero bit makes nm > mask strictly. So every source mask is a smaller integer than its target — by the time we reach nm in the increasing loop, all masks $<nm$ (including every possible source) are already final. No state is read before it is finished. ✓ Memory bound: entries $=n{2}^n$, each 8 bytes. Need $8n{2}^n\le 256\times 10^6$ bytes, i.e. $n{2}^n\le 3.2\times 10^7$.

• $n=20$: $20\cdot 2^{20}=20,971,520\approx 2.1\times 10^7$ ✓
• $n=21$: $21\cdot 2^{21}=44,040,192\approx 4.4\times 10^7$ ✗ Largest $n$ = 20. (This is the classic "$n\lesssim 20$" ceiling of the Held-Karp Algorithm; beyond it you switch to Branch and Bound or heuristics.)

Read a mask ::: decompose the integer into powers of two. Endpoint legality ::: dp[mask][i] valid only if mask & (1<<i). Peeled edge direction ::: always dist[j][i] (into the current city). Cycle vs path ::: cycle adds +dist[i][0]; path does not. Free vs pinned endpoint ::: free → min_i dp[full][i]; pinned → one cell. Iteration order ::: increasing masks work because setting a bit only grows the mask.