Bitmask DP — TSP intro: Exercises — Hinglish deep dive

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

Poore note mein, cities $0, 1, \dots, n - 1$ number hain, tour city 0 se start aur end hota hai, aur $dist [i] [j]$ edge $i \to j$ ka cost hai. DP table hai $dp [mask] [i]$ = city $0$ se cheapest path jo exactly set mask visit kar chuka hai aur abhi city $i$ pe khada hai.

Level 1 — Recognition

Exercise L1.1 — Read a mask

n = 5. Mask integer $22$ hai. Kaun si cities visit hui hain, aur kitni? Binary likho.

Recall Solution

A mask is just an integer whose binary digits are tick-boxes. Bit $i$ set hai ⟺ city $i$ visit hui. $22 = 16 + 4 + 2 = 2^{4} + 2^{2} + 2^{1}$ . 5 bits mein binary (bit4…bit0): 10110. Right-to-left padhte hain: bit0=0, bit1=1, bit2=1, bit3=0, bit4=1. Visit ki gayi cities: ${1, 2, 4}$ — teen cities.

Exercise L1.2 — Bit tests

mask = 22 ke saath (upar jaisa), har expression evaluate karo aur batao iska matlab kya hai: (a) mask & (1<<2) (b) mask & (1<<3) (c) mask | (1<<0) (d) mask & ~(1<<1).

Recall Solution

Yaad karo 1<<i $= 2^{i}$ = "woh integer jisme sirf bit $i$ on hai". (a) 1<<2 = 4; 22 & 4 = 4 (non-zero) → city 2 visit HUI hai. (b) 1<<3 = 8; 22 & 8 = 0 → city 3 visit NAHI hui. (c) 1<<0 = 1; 22 | 1 = 23 → city 0 add karo, giving ${0, 1, 2, 4}$ . (d) ~(1<<1) bit1 clear karta hai; 22 & ~2 = 20 → city 1 remove karo, giving ${2, 4}$ .

Exercise L1.3 — Total states

General $n$ ke liye, table $dp [mask] [i]$ mein kitni entries hain, aur kitni reachable hain (matlab bit $i$ , mask mein set ho)? $n = 4$ ke liye count do.

Recall Solution

Masks $0 \dots 2^{n} - 1$ range karte hain, to $2^{n}$ masks; current city $i$ ke $n$ choices hain → $n 2^{n}$ table slots. Ek slot meaningful tabhi hota hai jab bit $i$ , mask mein set ho (tum kisi unvisited city pe "end" nahi kar sakte). Fixed $i$ ke liye, exactly aadhe masks mein bit $i$ on hota hai: $2^{n - 1}$ . Saare $i$ ke upar: $n 2^{n - 1}$ reachable slots. $n = 4$ ke liye: table $= 4 \cdot 16 = 64$ slots, reachable $= 4 \cdot 8 = 32$ .

Level 2 — Application

Exercise L2.1 — Base case

$n = 3$ ke liye full initial dp table likho (sirf non- $\infty$ entry list karo) aur batao kyun har doosri entry $\infty$ hai.

Recall Solution

dp[1][0] = 0 — yani dp[001][0]: sirf city 0 visit hui, 0 pe khade hain, cost 0. Baaki sab $\infty$ hai kyunki start mein koi aisa path nahi jisne pehle se doosri cities visit ki hon. Entry $dp [mask] [i] = \infty$ ka matlab literally hai "yeh situation abhi reachable nahi." Jaise DP aage badhti hai yeh fill hote jaate hain.

Exercise L2.2 — Run 3 cities by hand

Distances (symmetric): $dist [0] [1] = 5, dist [0] [2] = 9, dist [1] [2] = 4$ . Full closed-tour TSP cost compute karo. Har dp entry dikhao.

Recall Solution

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

State	Compute	Value
`dp[011][1]`	`dp[001][0]+dist[0][1]=0+5`	5
`dp[101][2]`	`dp[001][0]+dist[0][2]=0+9`	9
`dp[111][2]`	`dp[011][1]+dist[1][2]=5+4`	9
`dp[111][1]`	`dp[101][2]+dist[2][1]=9+4`	13

Cycle close karo (return edge to 0 add karo): $min (9 + 9 = 18 9 + dist [2] [0], 13 + 5 = 18 13 + dist [1] [0]) = 18 .$ Dono orders $0 \to 1 \to 2 \to 0$ aur $0 \to 2 \to 1 \to 0$ ka cost $5 + 4 + 9 = 18$ hai. Answer: 18. ✓

Exercise L2.3 — Reading a transition

$n = 4$ , dp[mask][2] compute kar rahe hain with mask = 0111 $= 7$ . prev, valid predecessors $j$ , aur full expression list karo.

Recall Solution

Check karo endpoint legal hai: 0111 ka bit2 1 hai ✓ (city 2 visit hui hai). prev = 7 & ~(1<<2) = 0111 & 1011 = 0011 $= {0, 1}$ . Valid predecessors woh cities hain jo prev mein hain: $j \in {0, 1}$ . $dp [7] [2] = min (dp [3] [0] + dist [0] [2], dp [3] [1] + dist [1] [2]) .$ City 3 prev mein nahi hai (bit3 = 0), to yeh candidate nahi — tum kisi aisi city se nahi aa sakte jo tumne kabhi visit hi nahi ki.

Level 3 — Analysis

Exercise L3.1 — Why not store the order?

Ek dost insist karta hai: "Do tours jinhone ${0, 1, 2}$ visit kiya aur 2 pe end hue, lekin alag orders mein ( $0 \to 1 \to 2$ vs $0 \to 2 \to 1$ ... ruko, woh 1 pe end hota hai) — surely order future badal deta hai." Precisely rebut karo: kyun hum same-(set, spot) states ko collapse kar sakte hain?

Recall Solution

Remaining cost — tour finish karne ka cost — depend karta hai sirf (a) kaun si cities abhi visit karni hain (= mask ka complement) aur (b) tum abhi kahan khade ho (city $i$ ). Dono $(mask, i)$ mein capture hain. Already-visited prefix ka internal order sirf prefix ke apne accumulated cost ko affect karta hai, jo pehle se value $dp [mask] [i]$ ke roop mein stored hai. To do paths jo same $(mask, i)$ reach karte hain woh aage se interchangeable hain; hum cheaper value rakhte hain aur doosri discard karte hain. Yahi memorylessness hai jo state ko chhota rakhti hai: $n!$ orderings ki jagah $n 2^{n}$ states. Neeche figure dekho.

Exercise L3.2 — Count the work

$n = 13$ ke liye compute karo (i) states ki sankhya, (ii) roughly total transitions $n^{2} 2^{n}$ , aur (iii) $13!$ se compare karo. Ratio ka order-of-magnitude batao.

Recall Solution

(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$ (lagbhag $1.4 \times 1 0^{6}$ ) — computer ke liye trivial. (iii) $13! = 6, 227, 020, 800 \approx 6.2 \times 1 0^{9}$ . Ratio $13! / (n^{2} 2^{n}) \approx 6.2 \times 1 0^{9} /1.4 \times 1 0^{6} \approx 4.5 \times 1 0^{3}$ . Bitmask DP yahaan lagbhag 4500× kam kaam karta hai — aur $n$ badhne ke saath gap explosively badhta hai.

Exercise L3.3 — Where does optimal substructure come from?

Ek clean argument mein batao, kyun $dp [prev] [j]$ jo min ke andar appear hota hai, khud optimal hona chahiye (exchange argument).

Recall Solution

Maan lo $(mask, i)$ ka best path edge $j \to i$ pe end hota hai, aur uska prefix ( $(prev, j)$ tak ka path) ka cost $c$ tha. Agar $(prev, j)$ tak koi sasta path hota cost $c^{'} < c$ ke saath, to hum edge $j \to i$ usse jod sakte the aur $(mask, i)$ tak cost $c^{'} + dist [j] [i] < c + dist [j] [i]$ wala path paate — supposed best ko beat karte hue. Contradiction. Isliye prefix already optimal hona chahiye, yani $dp [prev] [j]$ ke barabar. Yeh "cut-and-paste" exactly woh optimal-substructure property hai jo recurrence ko legal banati hai.

Level 4 — Synthesis

Exercise L4.1 — Hamiltonian path, not cycle

L2.2 ke same distances ke saath ( $d_{01} = 5, d_{02} = 9, d_{12} = 4$ ), cheapest Hamiltonian path dhundho (0 se start, sab visit karo, return nahi). Kaun sa endpoint jeetta hai?

Recall Solution

Return term drop karo; answer $= min_{i} dp [full] [i]$ sab $i$ ke upar (including $i = 0$ ? nahi — city 0 fixed start hai, to $i \neq = 0$ yahaan kyunki path sab visit karne ke baad kahin aur end hona chahiye). L2.2 se: dp[111][1]=13, dp[111][2]=9. $min (13, 9) = 9$ , city 2 pe end hokar route $0 \to 1 \to 2$ se milta hai. Yeh cycle (18) se sasta hai precisely kyunki humne expensive return edge $2 \to 0 = 9$ skip ki. Yeh Hamiltonian Path and Cycle distinction action mein hai.

Exercise L4.2 — Fixed start AND fixed end (path)

Ab require karo ki path 0 se start ho aur city 1 pe end ho, ${0, 1, 2}$ sab visit karte hue, same distances. Cost?

Recall Solution

Hum directly $dp [full] [1]$ chahte hain — endpoints par min nahi, kyunki endpoint 1 par pinned hai. full = 111. L2.2 se, dp[111][1] = 13 (route $0 \to 2 \to 1$ : $9 + 4 = 13$ ). 1 pe end hone ka aur sirf ek hi tarika hai sab visit karke; aur ek hi "middle" city hai 2, to $0 \to 2 \to 1$ forced hai. Answer: 13. Lesson: endpoint pin karna matlab hai ek single table cell padhna, minimize karna nahi.

Exercise L4.3 — Asymmetric distances (one-way roads)

$n = 3$ , lekin ab directed: $d_{01} = 2, d_{10} = 7, d_{02} = 6, d_{20} = 3, d_{12} = 1, d_{21} = 9$ . 0 se start/end hote hue cheapest closed tour dhundho. Dikhao ki dono directions alag hain.

Recall Solution

Yahaan dist[j][i] ≠ dist[i][j], to direction matter karta hai — isliye transition dist[j][i] use karta hai dist[i][j] nahi.

State	Compute	Value
`dp[011][1]`	`dp[001][0]+d[0][1]=0+2`	2
`dp[101][2]`	`dp[001][0]+d[0][2]=0+6`	6
`dp[111][2]`	`dp[011][1]+d[1][2]=2+1`	3
`dp[111][1]`	`dp[101][2]+d[2][1]=6+9`	15

Close karo: $min (3 + 3 = 6 3 + d [2] [0], 15 + 7 = 22 15 + d [1] [0]) = 6$ . Winning tour $0 \to 1 \to 2 \to 0$ ka cost $2 + 1 + 3 = 6$ hai. Reverse $0 \to 2 \to 1 \to 0 = 6 + 9 + 7 = 22$ . Directions bahut alag hain — answer 6, aur sirf DP ka directional dist[j][i] isse pakadta hai.

Level 5 — Mastery

Exercise L5.1 — Multiple start cities (metric closure trick)

Tum tour kisi bhi city se start kar sakte ho (phir bhi ek closed cycle jo sab visit kare). Kya start ko 0 fix karne se optimality lose hoti hai? Apna answer prove karo.

Recall Solution

Koi optimality lose nahi hoti. Ek closed tour ek cycle hai; ek cycle ka koi distinguished starting point nahi hota — woh same edges visit karta hai chahe tum kaunsa vertex "start" kaho. To optimal cycle city 0 se guzarta hai, aur traversal city 0 se shuru karne ke liye apna labelling rotate karna usi cycle ko same cost ke saath describe karta hai. Isliye start $= 0$ fix karna phir bhi global optimum dhundh leta hai. (Caveat: yeh cycle version ke liye valid hai. Free start wali path ke liye, tum base case ko saare start cities par loop karte, kaam $n$ se multiply hota.)

Exercise L5.2 — Count optimal tours

L2.2 ke symmetric triangle ( $5, 9, 4$ ) ke liye, kitne distinct closed tours optimum achieve karte hain, aur kyun? Generalise karo: symmetric $n = 3$ instance mein exactly 2 optimal tours kab hote hain vs 1?

Recall Solution

$n = 3$ ke liye city 0 se exactly 2 directed closed tours hain: $0 \to 1 \to 2 \to 0$ aur $0 \to 2 \to 1 \to 0$ . Symmetric distances ke saath dono same teen edges ${01, 12, 20}$ opposite directions mein traverse karte hain, to dono hamesha same $d_{01} + d_{12} + d_{02}$ cost karte hain. Yahaan woh $5 + 4 + 9 = 18$ hai, dono tours se achieve hota hai. Generalisation: symmetric $n = 3$ ke liye, do tours mirror images hain aur hamesha tie karte hain — hamesha exactly 2 optimal directed tours hote hain (ya tum unhe 1 undirected tour count kar sakte ho). Strict single winner tabhi aata hai jab distances asymmetric hain, mirror symmetry todti hain (jaise L4.3 mein, jahan $6 \neq = 22$ ).

Exercise L5.3 — Memory halving via forward push

Reference implementation forward push karta hai (mask → nm = mask | (1<<k)). Argue karo kyun masks ko increasing order mein iterate karna correctness guarantee karta hai, aur woh largest $n$ do jiske liye int-indexed dp array of longs $256$ MB mein fit hota hai (assume 8 bytes/entry).

Recall Solution

Increasing order ki correctness: forward push dp[nm][k] ko dp[mask][i] se update karta hai jahan nm = mask | (1<<k) aur bit $k$ , mask mein nahi tha. Pehle-se-zero bit set karna nm > mask strictly banata hai. To increasing loop mein jab bhi hum nm reach karte hain, saare masks $< nm$ (har possible source including) already final hain. Koi state apne final hone se pehle read nahi hoti. ✓ Memory bound: entries $= n 2^{n}$ , har ek 8 bytes. Chahiye $8 n 2^{n} \leq 256 \times 1 0^{6}$ bytes, yani $n 2^{n} \leq 3.2 \times 1 0^{7}$ .

$n = 20$ : $20 \cdot 2^{20} = 20, 971, 520 \approx 2.1 \times 1 0^{7}$ ✓
$n = 21$ : $21 \cdot 2^{21} = 44, 040, 192 \approx 4.4 \times 1 0^{7}$ ✗ Largest $n$ = 20. (Yahi Held-Karp Algorithm ki classic " $n ≲ 20$ " ceiling hai; iske aage tum Branch and Bound ya heuristics use karte ho.)

Recall One-line self-check summary

Mask padhna ::: integer ko powers of two mein decompose karo. Endpoint legality ::: dp[mask][i] valid tabhi jab mask & (1<<i) ho. Peeled edge direction ::: hamesha dist[j][i] (current city mein jaata hai). Cycle vs path ::: cycle +dist[i][0] add karta hai; path nahi. Free vs pinned endpoint ::: free → min_i dp[full][i]; pinned → ek cell. Iteration order ::: increasing masks kaam karte hain kyunki bit set karna sirf mask badhata hai.

Connections

Travelling Salesman Problem, Held-Karp Algorithm — exact problem aur algorithm jo yeh drills implement karti hain.
Bit Manipulation, Subset Enumeration — mask machinery (L1).
Dynamic Programming — optimal substructure (L3.3).
Hamiltonian Path and Cycle — path vs cycle distinction (L4).
Branch and Bound — $n \approx 20$ se aage jaane ke liye kya use karte hain (L5.3).