Worked examples — Bitmask DP — TSP intro

3.7.15 · D3 · Coding › Algorithm Paradigms › Bitmask DP — TSP intro

Yeh parent TSP intro ka practice-until-it-hurts companion hai. Wahan humne state dp[SET][SPOT] aur transition build kiya tha. Yahan hum isse run karte hain — har us case ke liye jo problem throw kar sakti hai — tiny inputs, degenerate graphs, asymmetric costs, path-vs-cycle, aur ek exam trap. Agar koi scenario exam mein surprise kare, toh sirf isliye hona chahiye kyunki tum bhool gaye, na ki isliye kyunki tune kabhi dekha hi nahi.

---

Scenario matrix

Neeche har cell DP ke behave karne ka ek alag tarika hai. Har worked example ko woh cell(s) tag kiya gaya hai jo wo cover karta hai.

Cell	Case class	Kya special hai	Covered by
A	Sabse chhota non-trivial ($n=2$)	Do cities, ek round trip — base case barely hilta hai	Ex 1
B	Symmetric triangle ($n=3$)	Dono directions equal; har jagah ties	Ex 2
C	Asymmetric graph	dist[i][j] ≠ dist[j][i] (one-way roads) — direction matters	Ex 3
D	Missing edge (∞ cost)	Do cities ke beech koi road nahi; DP ko route around karna padega	Ex 4
E	Degenerate: unreachable state	Ek dp[mask][i] jo $\infty$ par reh jaata hai aur skip karna padta hai	Ex 4, Ex 6
F	Path, cycle nahi	Return edge drop karo; answer badal jaata hai	Ex 5
G	Real-world word problem	Ek story ko dist matrix mein translate karo	Ex 6
H	Exam twist: "fixed start ≠ fixed end"	0 se start, ek given city par end karna zaroori	Ex 7
I	Limiting behaviour / sanity	Numbers $n$ badhne par kya bante hain; brute-force cross-check	Ex 8

---

Example 1 — Cell A: sabse chhota tour ($n=2$)

Steps.

1. Base: dp[01][0] = dp[1][0] = 0. Yeh step kyun? Har DP ko us akele state ko seed karke shuru kiya jaata hai jisko hum free mein jaante hain: start par baithna, sirf $\{0\}$ visit kiya hua, cost $0$.
2. City 1 tak pahuncho: dp[11][1] = dp[01][0] + dist[0][1] = 0 + 7 = 7. Yeh step kyun? mask=11 matlab $\{0,1\}$ visited; 1 par end karne ke liye hum last edge $0\to 1$ peel karte hain.
3. Tour close karo: full = 11, answer $=dp[11][1]+\text{dist}[1][0]=7+7=14$. Yeh step kyun? TSP ek cycle hai, isliye hum return edge $1\to 0$ ka cost pay karna zaroori hai (parent mein Mistake #3).

Verify: sirf possible route $0\to 1\to 0=7+7=14$ hai. Minimise karne ke liye kuch nahi hai — match karta hai. ✓ (Units: cost units, consistent.)

---

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

Yeh parent ka Worked Example 1 hai, re-run kiya gaya taaki neeche ki figure dono competing final routes side by side dikhaye.

Steps.

1. dp[011][1] = 0 + 10 = 10 ($0\to 1$ jaao); dp[101][2] = 0 + 15 = 15 ($0\to 2$ jaao). Yeh step kyun? Base state se hum har unvisited city ki taraf branch karte hain — yeh do pehle moves hain.
2. dp[111][2] = dp[011][1] + \text{dist}[1][2] = 10 + 20 = 30. Yeh step kyun? Mask $\{0,1,2\}$ ko 2 par end karte hue fill karo, 1 se aake.
3. dp[111][1] = dp[101][2] + \text{dist}[2][1] = 15 + 20 = 35. Yeh step kyun? Sab kuch fill karne ka doosra tarika, 1 par end karte hue, 2 se aake.
4. Close: $\min (30+\text{dist}[2][0],35+\text{dist}[1][0])=\min (30+15,35+10)=\min (45,45)=45$. Yeh step kyun? Do full-mask states, do return edges — sasta wala lo.

Verify: $0\to 1\to 2\to 0=10+20+15=45$; $0\to 2\to 1\to 0=15+20+10=45$. Tie real hai (figure mein do coloured loops dekho — same edges, opposite direction). ✓

---

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

Steps.

1. Pehle moves: dp[011][1] = dist[0][1] = 1; dp[101][2] = dist[0][2] = 9. Yeh step kyun? Direction ab matter karta hai — $0\to 1$ ka cost 1 hai lekin $0\to 2$ ka cost 9 hai. DP dono ko honestly record karta hai.
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. Yeh steps kyun? Tour do tarike se complete karo; expensive branch (18) haar jaayega.
4. Close: $\min (dp[111][2]+dist[2][0],dp[111][1]+dist[1][0])=\min (3+3,18+9)=\min (6,27)=6$. Yeh step kyun? Return edge bhi directional hai — $2\to 0$ sasta hai (3), $1\to 0$ mehnga hai (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 ne 6 liya. ✓ Isliye hum dist[i][j] ko ek full matrix mein store karte hain, kabhi assume nahi karte ki dist[i][j]==dist[j][i].

---

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

Steps.

1. dp[011][1] = 4, dp[101][2] = 6. Yeh step kyun? 0 se dono pehle hops exist karte hain, isliye dono states finite hain.
2. dp[111][2] = dp[011][1] + \text{dist}[1][2] = 4 + \infty = \infty. Yeh step kyun? Full mask ke saath 2 par end karne ka sirf ek tarika hai $1\to 2$ se, jo exist nahi karta — yeh state unreachable hai (Cell E). Code mein, if dp[mask][i]==INF: continue ise skip karta hai.
3. dp[111][1] = dp[101][2] + \text{dist}[2][1] = 6 + \infty = \infty. Yeh step kyun? Symmetrically dead — 1 par end karne ke liye $2\to 1$ chahiye, jo bhi missing hai.
4. Close: $\min (\infty +\text{dist}[2][0],\infty +\text{dist}[1][0])=\infty$. Yeh step kyun? Dono full-mask states $\infty$ hain, isliye answer $\infty$ = koi valid tour nahi.

Verify: 3 cities par koi bhi Hamiltonian cycle edge $1-2$ use karta hai (ek triangle mein sab teeno ko visit karke close karne ka koi doosra tarika nahi). Kyunki woh edge missing hai, koi cycle exist nahi karta. DP correctly $\infty$ return karta hai. ✓ Yeh Hamiltonian Path and Cycle existence question hai jo DP ke andar free mein surface ho raha hai.

---

Example 5 — Cell F: Hamiltonian path (ghar wapas nahi)

Steps.

1. Example 2 ka DP table reuse karo — internal states identical hain; sirf final aggregation change hoti hai. Yeh step kyun? Recurrence ne kabhi return edge use nahi ki, isliye last line se pehle kuch bhi alag nahi hai.
2. Path answer $={\min }_{i}dp[\text{full}][i]=\min (dp[111][1],dp[111][2])=\min (35,30)=30$. Yeh step kyun? Path ke liye hum dist[i][0] add nahi karte; bas end karne ki sabse sasti jagah lete hain (Mistake #3 ne doosri direction handle ki thi).

Verify: path $0\to 1\to 2=10+20=30$; path $0\to 2\to 1=15+20=35$. Sabse sasta 30 hai, aur $30<45$ (cycle) as forecast. ✓

---

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

Matrix banao (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. Hum chaar candidate delivery orders evaluate karte hain ($n=4$ ke saath $(n-1)!=6$ tours hain, lekin symmetry unhe 3 distinct costs mein pair karta hai — har ek ek baar count hota hai):

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$. Yeh steps kyun? Har row ek full-mask endpoint choice hai jo DP compare karega; DP ka min sabse chhota pick karta hai.
4. Answer $=\min (18,28,24)=18$, route depot→A→B→C→depot. Yeh step kyun? DP ki closing line ${\min }_i(dp[\text{full}][i]+dist[i][0])$ exactly yahi comparison automatically karti hai.

Verify: $5+3+6+4=18$ minutes, aur yeh doosron ko beat karta hai. Units: har jagah minutes, koi mixing nahi. ✓ (Cell E note: koi bhi intermediate dp[mask][i] jahan bit i mask mein nahi tha, $\infty$ par raha aur skip hua — same guard jaise Ex 4.)

---

Example 7 — Cell H: exam twist, ek specific city par end karna zaroori

Steps.

1. Fixed endpoint ka matlab answer exactly $dp[\text{full}][3]$ hai — last city par minimise nahi, aur koi return edge nahi. Yeh step kyun? "C par end karo" dono — endpoint ka free choice aur return term — remove karta hai.
2. 3 par end hone wale orders enumerate karo, 0 se start karke:
   • $0\to 1\to 2\to 3=5+3+6=14$.
   • $0\to 2\to 1\to 3=9+3+8=20$. Yeh step kyun? C ko last aane ke yeh do tarike hain; DP dp[1111][3] mein sasta wala store karta hai.
3. Answer $=\min (14,20)=14$.

Verify: $5+3+6=14$. Yeh cycle (18) se sasta hai kyunki hum $C\to$depot edge (cost 4) skip karte hain: $18-4=14$. Consistent. ✓ Lesson: ek fixed end general path se bhi aasaan hai — tum ek cell padhte ho, dp[full][target].

---

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

Steps.

1. States $=n\cdot 2^n=4\cdot 16=64$. Yeh step kyun? $2^n=16$ masks $\times n=4$ current-city slots — table ka size (dekho Held-Karp Algorithm).
2. Transitions $=n^2\cdot 2^n=16\cdot 16=256$ (upper bound; unreachable/illegal states ise prune karte hain). Yeh step kyun? Har state $\le n$ predecessors par minimise karta hai — extra factor $n$.
3. Brute force $(n-1)!=3!=6$ full tours try karta hai. Tiny $n$ ke liye brute force kam operations hai — DP ki jeet sirf $n$ badhne par dikhti hai. Yeh step kyun? $n=4$ par, $6<64$; exponential-vs-factorial crossover (parent ka 80/20) lagbhag $n\approx 7$ par hai aur $n=20$ tak astronomical ho jaata hai.
4. Cross-check: 6 tours par brute force costs $\{18,28,24,24,28,18\}$ deta hai → min $=18$, Example 6 se match karta hai. Yeh step kyun? Do independent methods ka agree karna sabse strong sanity check hai (Branch and Bound same optimum tak prune karta).

Verify: $4\cdot 16=64$, $16\cdot 16=256$, $3!=6$, aur brute-force min $=18=$ DP answer. Sab confirm. ✓

---

Recall Kaun si final line kis question ke liye?

Closed tour (cycle) ::: min over i!=0 of dp[full][i] + dist[i][0] Path, koi bhi endpoint ::: min over i of dp[full][i] Path, fixed endpoint t ::: bas dp[full][t] (ek cell, koi min nahi) Koi valid tour exist nahi karta ::: chosen expression $\infty$ evaluate karta hai

---

Connections

• Bitmask DP — TSP intro (index 3.7.15) — parent (state + recurrence wahan build ki gayi)
• Travelling Salesman Problem — woh problem jo yeh examples solve karte hain
• Held-Karp Algorithm — is DP ka formal naam; Ex 8 mein complexity
• Dynamic Programming — optimal-substructure backbone
• Bit Manipulation / Subset Enumeration — masks kaise index hoti hain
• Hamiltonian Path and Cycle — existence Ex 4 mein surface hui
• Branch and Bound — alternative exact method (Ex 8 cross-check idea)
• 🇮🇳 3.7.15 Bitmask DP — TSP intro (Hinglish)