Worked examples — Bitmask DP — TSP intro

This is the practice-until-it-hurts companion to the parent TSP intro. There we built the state dp[SET][SPOT] and the transition. Here we run it across every case the problem can throw at you — tiny inputs, degenerate graphs, asymmetric costs, path-vs-cycle, and an exam trap. If a scenario surprises you in an exam, it should be because you forgot it, not because you never saw it.

---

The scenario matrix

Every cell below is a distinct way the DP can behave. Each worked example is tagged with the cell(s) it covers.

Cell	Case class	What's special	Covered by
A	Smallest non-trivial ($n=2$)	Two cities, one round trip — the base case barely moves	Ex 1
B	Symmetric triangle ($n=3$)	Both directions equal; ties everywhere	Ex 2
C	Asymmetric graph	dist[i][j] ≠ dist[j][i] (one-way roads) — direction matters	Ex 3
D	Missing edge (∞ cost)	No road between two cities; DP must route around	Ex 4
E	Degenerate: unreachable state	A dp[mask][i] that stays $\infty$ and must be skipped	Ex 4, Ex 6
F	Path, not cycle	Drop the return edge; answer changes	Ex 5
G	Real-world word problem	Translate a story into a dist matrix	Ex 6
H	Exam twist: "fixed start ≠ fixed end"	Start at 0, must end at a given city	Ex 7
I	Limiting behaviour / sanity	What the numbers become as $n$ grows; brute-force cross-check	Ex 8

---

Example 1 — Cell A: the smallest tour ($n=2$)

Steps.

1. Base: dp[01][0] = dp[1][0] = 0. Why this step? Every DP starts by seeding the only state we know for free: sitting at the start, having visited only $\{0\}$, cost $0$.
2. Reach city 1: dp[11][1] = dp[01][0] + dist[0][1] = 0 + 7 = 7. Why this step? mask=11 means $\{0,1\}$ visited; to end at 1 we peel the last edge $0\to 1$.
3. Close the tour: full = 11, answer $=dp[11][1]+\text{dist}[1][0]=7+7=14$. Why this step? TSP is a cycle, so we must pay the return edge $1\to 0$ (Mistake #3 in the parent).

Verify: the only possible route is $0\to 1\to 0=7+7=14$. There is nothing to minimise over — matches. ✓ (Units: cost units, consistent.)

---

Example 2 — Cell B: symmetric triangle, ties ($n=3$)

This is the parent's Worked Example 1, re-run so the figure below shows both competing final routes side by side.

Steps.

1. dp[011][1] = 0 + 10 = 10 (go $0\to 1$); dp[101][2] = 0 + 15 = 15 (go $0\to 2$). Why this step? From the base state we branch to each unvisited city — these are the two first moves.
2. dp[111][2] = dp[011][1] + \text{dist}[1][2] = 10 + 20 = 30. Why this step? Fill the mask $\{0,1,2\}$ ending at 2, arriving from 1.
3. dp[111][1] = dp[101][2] + \text{dist}[2][1] = 15 + 20 = 35. Why this step? The other way to fill everything, ending at 1, arriving from 2.
4. Close: $\min (30+\text{dist}[2][0],35+\text{dist}[1][0])=\min (30+15,35+10)=\min (45,45)=45$. Why this step? Two full-mask states, two return edges — take the cheaper.

Verify: $0\to 1\to 2\to 0=10+20+15=45$; $0\to 2\to 1\to 0=15+20+10=45$. The tie is real (look at the two coloured loops in the figure — same edges, opposite direction). ✓

---

Example 3 — Cell C: asymmetric graph (one-way roads)

Steps.

1. First moves: dp[011][1] = dist[0][1] = 1; dp[101][2] = dist[0][2] = 9. Why this step? Direction now matters — $0\to 1$ costs 1 but $0\to 2$ costs 9. The DP records both honestly.
2. dp[111][2] = dp[011][1] + dist[1][2] = 1 + 2 = 3.
3. dp[111][1] = dp[101][2] + dist[2][1] = 9 + 9 = 18. Why these steps? Complete the tour two ways; the expensive branch (18) will lose.
4. Close: $\min (dp[111][2]+dist[2][0],dp[111][1]+dist[1][0])=\min (3+3,18+9)=\min (6,27)=6$. Why this step? Return edge is also directional — $2\to 0$ is cheap (3), $1\to 0$ is dear (9).

Verify: cheap loop $0\to 1\to 2\to 0=1+2+3=6$; other loop $0\to 2\to 1\to 0=9+9+9=27$. DP took 6. ✓ This is why we store dist[i][j] as a full matrix, never assume dist[i][j]==dist[j][i].

---

Example 4 — Cells D + E: a missing road (∞ edge → unreachable state)

Steps.

1. dp[011][1] = 4, dp[101][2] = 6. Why this step? Both first hops from 0 exist, so both states are finite.
2. dp[111][2] = dp[011][1] + \text{dist}[1][2] = 4 + \infty = \infty. Why this step? The only way to end at 2 with full mask is via $1\to 2$, which doesn't exist — the state is unreachable (Cell E). In code, if dp[mask][i]==INF: continue skips it.
3. dp[111][1] = dp[101][2] + \text{dist}[2][1] = 6 + \infty = \infty. Why this step? Symmetrically dead — ending at 1 needs $2\to 1$, also missing.
4. Close: $\min (\infty +\text{dist}[2][0],\infty +\text{dist}[1][0])=\infty$. Why this step? Both full-mask states are $\infty$, so the answer is $\infty$ = no valid tour.

Verify: any Hamiltonian cycle on 3 cities uses edge $1-2$ (a triangle has no way to visit all three and close without every edge). Since that edge is missing, no cycle exists. DP correctly returns $\infty$. ✓ This is the Hamiltonian Path and Cycle existence question surfacing inside the DP for free.

---

Example 5 — Cell F: Hamiltonian path (no return home)

Steps.

1. Reuse the DP table from Example 2 — the internal states are identical; only the final aggregation changes. Why this step? The recurrence never used the return edge, so nothing before the last line differs.
2. Path answer $={\min }_{i}dp[\text{full}][i]=\min (dp[111][1],dp[111][2])=\min (35,30)=30$. Why this step? For a path we do not add dist[i][0]; we just take the cheapest place to end (Mistake #3 handled the other direction).

Verify: path $0\to 1\to 2=10+20=30$; path $0\to 2\to 1=15+20=35$. Cheapest is 30, and $30<45$ (the cycle) as forecast. ✓

---

Example 6 — Cells G + E: word problem (delivery driver)

Build the matrix (symmetric): $\text{dist}=\left[\begin{array}{cccc}0& 5& 9& 4\\ 5& 0& 3& 8\\ 9& 3& 0& 6\\ 4& 8& 6& 0\end{array}\right]$

Steps. We evaluate the four candidate delivery orders (with $n=4$ there are $(n-1)!=6$ tours, but symmetry pairs them into 3 distinct costs — each counted once):

1. $0\to 1\to 2\to 3\to 0=5+3+6+4=18$.
2. $0\to 1\to 3\to 2\to 0=5+8+6+9=28$.
3. $0\to 2\to 1\to 3\to 0=9+3+8+4=24$. Why these steps? Each row is one full-mask endpoint choice the DP would compare; the DP's min picks the smallest.
4. Answer $=\min (18,28,24)=18$, route depot→A→B→C→depot. Why this step? The DP's closing line ${\min }_i(dp[\text{full}][i]+dist[i][0])$ does exactly this comparison automatically.

Verify: $5+3+6+4=18$ minutes, and it beats the others. Units: minutes throughout, no mixing. ✓ (Cell E note: any intermediate dp[mask][i] where bit i isn't in mask stayed $\infty$ and was skipped — same guard as Ex 4.)

---

Example 7 — Cell H: exam twist, must end at a specific city

Steps.

1. Fixed endpoint means the answer is exactly $dp[\text{full}][3]$ — no minimising over the last city, and no return edge. Why this step? "End at C" removes both the free choice of endpoint and the return term.
2. Enumerate orders ending at 3, starting at 0:
   • $0\to 1\to 2\to 3=5+3+6=14$.
   • $0\to 2\to 1\to 3=9+3+8=20$. Why this step? These are the two ways to arrive at C last; the DP stores the cheaper in dp[1111][3].
3. Answer $=\min (14,20)=14$.

Verify: $5+3+6=14$. It's cheaper than the cycle (18) because we skip the $C\to$depot edge (cost 4): $18-4=14$. Consistent. ✓ Lesson: a fixed end is even easier than a general path — you read one cell, dp[full][target].

---

Example 8 — Cell I: limiting behaviour & brute-force cross-check

Steps.

1. States $=n\cdot 2^n=4\cdot 16=64$. Why this step? $2^n=16$ masks $\times n=4$ current-city slots — the table's size (see Held-Karp Algorithm).
2. Transitions $=n^2\cdot 2^n=16\cdot 16=256$ (upper bound; unreachable/illegal states prune this). Why this step? Each state minimises over $\le n$ predecessors — the extra factor $n$.
3. Brute force tries $(n-1)!=3!=6$ full tours. For tiny $n$ brute force is fewer operations — DP's win only appears as $n$ grows. Why this step? At $n=4$, $6<64$; the exponential-vs-factorial crossover (parent's 80/20) is around $n\approx 7$ and becomes astronomical by $n=20$.
4. Cross-check: brute force over the 6 tours gives costs $\{18,28,24,24,28,18\}$ → min $=18$, matching Example 6. Why this step? Two independent methods agreeing is the strongest sanity check (Branch and Bound would prune to the same optimum).

Verify: $4\cdot 16=64$, $16\cdot 16=256$, $3!=6$, and the brute-force min $=18=$ DP answer. All confirmed. ✓

---

Recall Which final line for which question?

Closed tour (cycle) ::: min over i!=0 of dp[full][i] + dist[i][0] Path, any endpoint ::: min over i of dp[full][i] Path, fixed endpoint t ::: just dp[full][t] (one cell, no min) No valid tour exists ::: the chosen expression evaluates to $\infty$

---

Connections

• Bitmask DP — TSP intro (index 3.7.15) — parent (state + recurrence built there)
• Travelling Salesman Problem — the problem these examples solve
• Held-Karp Algorithm — the formal name for this DP; complexity in Ex 8
• Dynamic Programming — optimal-substructure backbone
• Bit Manipulation / Subset Enumeration — how masks are indexed
• Hamiltonian Path and Cycle — existence surfaced in Ex 4
• Branch and Bound — alternative exact method (Ex 8 cross-check idea)
• 🇮🇳 3.7.15 Bitmask DP — TSP intro (Hinglish)