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

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

Hum poore walkthrough mein ek hi running example use karte hain. Plane par chaar cities:

$0, 1, 2, 3$

symmetric distances ke saath (edge $i \to j$ ka cost $j \to i$ ke barabar hai):

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

Yahan $dist [i] [j]$ ka matlab sirf yeh hai ki "city $i$ aur city $j$ ke beech ki road par likha number." Bas itna hi.

Step 1 — Wo duniya draw karo jise hum optimise kar rahe hain

DRAW kyun karte hain pehle? Kyunki neeche har abstract symbol ( $mask$ , $dp$ , "current city") is map ke baare mein ek fact hai. Agar tum use map par point kar sakte ho, tum samajh rahe ho. Agar nahi kar sakte, nahi samajh rahe.

PICTURE. Chaar cities dots hain; das roads gray hain apne costs ke saath. Ek tour ek loop hai jo har dot ko exactly ek baar touch karta hai. Yahan $(4 - 1)! /2 = 3$ genuinely alag loops hain — itne kam ki baad mein haath se check kar sako, aur exactly yahi wajah hai ki 4 cities ek achha teaching size hai.

Step 2 — "Kaun si cities ho gayi" ko ek single integer mein badlo

Integers kyun aur Python set kyun nahi? Kyunki hamari table ko ek index chahiye — ek slot number. Ek integer sabse sasta slot number hai jo exist karta hai. Set ${0, 1}$ switch row 0011 ban jata hai, jo ek ordinary number ke roop mein $1 + 2 = 3$ hai. Toh "visited cities ka set" aur "number $3$ " ek hi object hain — do alag nazariye se dekhe gaye.

PICTURE. Chaar switches ki ek strip. Har switch ke neeche hum uski value likhte hain. Visited set ${0, 2}$ switches $0$ aur $2$ ko light karta hai, deta hai 0101 $= 1 + 4 = 5$ .

Bit Manipulation dekho agar in teen lines mein se koi bhi shaky lage — yahi poori vocabulary hai jo hamein chahiye.

Step 3 — Table cell ka naam: `dp[mask][i]`

KYA. Ek number har (switch-row, current-city) pair ke liye. Ek grid: rows hain $2^{4} = 16$ switch-rows, columns hain $4$ possible "current city" values.

Yeh shape kyun? Yahi parent note ka poora magic hai. Ek path ek lambi kahani hai ( $0 \to 2 \to 1 \to \dots$ ). Lekin woh sirf do facts jo affect karte hain kya hoga aage hain — SET jo already ho gayi aur SPOT jahan tum ho. Har kahani jisका same (SET, SPOT) hai woh yahan se interchangeable hai — toh hum sirf sabse sasta rakhte hain aur baaki bhool jaate hain. Wahi bhoolna $n!$ ko $n 2^{n}$ size ke grid mein shrink karta hai.

PICTURE. Ek blank $16 \times 4$ grid. Zyaadatar cells impossible hain aur gray painted hain: dp[mask][i] sirf tab sense karta hai jab city $i$ ka switch $mask$ mein ON ho (tum "end at $i$ " nahi ho sakte agar tumne $i$ visit hi nahi kiya). Dekho — grid ka exactly aadha-ish hissa legal hai.

Step 4 — Seed lagao: base case

KYA. Exactly ek legal cell ko $0$ set karo; baaki sab $\infty$ rehne do.

$0$ kyun? Tum city $0$ par shuru ho rahe ho, kuch kharch kiye bina aur kisi ko visit kiye bina siwaaye apne aap ke. Switch row hai 0001 (sirf switch $0$ lit) $= 1$ . Cost abhi tak: $0$ roads chale $= 0$ .

PICTURE. Step 3 ka grid jisme ek akela green $0$ row 0001, column $0$ mein drop kiya gaya hai. Har doosri cell abhi bhi $\infty$ hai. Yeh akela seed un sab numbers ka ancestor hai jo hum baad mein compute karte hain.

Step 5 — Ek rule: path ko uski last edge se grow karo

Ab engine. Cell dp[mask][i] fill karne ke liye, poochho: $i$ se pehle main kise visit kiya tha?

Yeh allowed kyun hai? Optimal substructure. $i$ par khatam hone wale kisi bhi cheapest path mein koi last-visited city $j$ hoti hai. Woh final road $j \to i$ kaato; bacha hua prefix khud hi $(prev, j)$ tak ka cheapest path hona chahiye — agar ek sasta prefix exist karta toh hum use jodte aur apna minimum beat karte, jo ek contradiction hai. Yahi logic sabhi Dynamic Programming ko legal banata hai.

PICTURE. Ek target cell (orange), ek switch chhote cells se arrows se fed hai. Hum literally last edge peel kar rahe hain aur already-filled predecessors padh rahe hain. Yeh Held-Karp Algorithm ek single frame mein hai.

Step 6 — Engine ko apne map par chalao, layer by layer

KYA. Cells fill karo kitne switches lit hain ke order mein — kyunki ek cell sirf kam switches wali cells par depend karti hai. Toh process karo popcount $= 1$ , phir $2$ , phir $3$ , phir $4$ . (popcount = kitne switches ON hain.)

Yeh order kyun? Yeh guarantee karta hai ki right-hand side par jo bhi $dp [prev] [j]$ hum padhte hain woh pehle hi finalize ho chuka tha ek previous layer par. Koi cell use-hone se pehle ready na ho, aisa nahi hoga.

PICTURE — numbers appear ho rahe hain. Dekho har layer light up hoti hai (yaad raho dist: $01 = 2, 02 = 9, 03 = 10, 12 = 6, 13 = 4, 23 = 3$ ):

Layer 1 (seed): dp[0001][0]=0.
Layer 2 — $0$ se ek hop bahar:

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

Layer 3 — $0$ ke ilawa do cities, e.g. set ${0, 1, 2} = 0111$ , $2$ par khatam:

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

Yahan sirf $j = 1$ legal hai (hamein $j \in prev = {0, 1}$ aur $j \neq = 2$ chahiye; $j = 0$ ko dp[0101][0] chahiye hoga jo $2$ se nahi guzarta... dhyan se: $prev = {0, 1}$ , toh $j \in {0, 1}$ ):

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

Lekin dp[0011][0] $\infty$ hai (tum $0$ par khade nahi ho sakte jab ${0, 1}$ visited ho is DP ke forward growth mein $0$ tak pahunchte hue), toh live term hai $2 + 6 = 8$ . ✓

Step 7 — Poori layer fill karo, phir tour close karo

KYA. Teen cells dp[1111][1], dp[1111][2], dp[1111][3] compute karo, ghar ki road jodo, sabse chota lo.

Hamare numbers ke liye optimal closed tour hai $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.$

$dist [i] [0]$ kyun jodte hain? Ek tour ek cycle hai (dekho Hamiltonian Path and Cycle). DP sirf bahar chala sab tak; woh kabhi wapas aane ke liye nahi bola. Yeh return road bhoolna parent mein trap #3 hai. Agar Hamiltonian path chahiye cycle ki jagah, toh yeh term drop karo aur $min_{i} dp [1111] [i]$ answer do.

PICTURE. Teen full-layer cells apne home-roads ke saath dashed arrows ke roop mein $0$ par wapas; winning $18$ highlighted, uska actual loop map par traced.

Step 8 — Edge aur degenerate cases (koi hole mat chhodna)

Worked example Woh cases jinse tum surprised nahi hone chahiye

$n = 1$ . Ek city, already ghar. $full = 1$ , base dp[1][0]=0, close karne ke liye koi doosri city nahi → tour cost $0$ . min(... for i in 1..n) loop empty hai; ise guard karo ya answer $0$ define karo.
$n = 2$ . Cities $0, 1$ . Sirf ek route: $0 \to 1 \to 0$ costs $dist [0] [1] + dist [1] [0]$ . DP: dp[11][1]=dist[0][1], close karo +dist[1][0] se. ✓
Asymmetric roads ( $dist [i] [j] \neq = dist [j] [i]$ ). Kuch nahi toota — DP ne kabhi symmetry assume nahi ki; woh hamesha directed edge $dist [j] [i]$ use karta hai arrival ke liye aur $dist [i] [0]$ return ke liye. Hamaara example sirf isliye symmetric tha ki haath se checking easy ho.
Missing road ( $i \to j$ ka koi edge nahi). $dist [i] [j] = \infty$ store karo; $min$ naturally kisi bhi path ko reject kar deta hai jo usme se force-through ho. Agar har full-layer close $\infty$ hai, toh koi Hamiltonian cycle exist nahi karta.
Unreachable cell. Cells jo processing ke baad bhi $\infty$ hain woh impossible states hain — code ka if dp[mask][i]==INF: continue unhe skip karta hai, kaam bachata hai. Yeh ek mini Branch and Bound idea hai: dead ko prune karo.

PICTURE. Chaar tiny grids side by side: $n = 1$ (single seed = answer), $n = 2$ (two-cell chain), ek asymmetric arrow pair, aur ek broken road red $\infty$ ke roop mein jo $min$ skip karta hai.

Ek-picture summary

Upar sab kuch, compressed: seed neeche, arrows upar layers mein flow karte hain jaise switches ek ek karke on hote hain (har arrow = " $+ dist [j] [i]$ , min rakhna"), aur dashed home-roads upar cycle close karti hain. Poora Held-Karp Algorithm hai paani switch-rows ki lattice mein upar bahna, phir ghar girna.

Recall Feynman: poora walkthrough simple shabdon mein

Maine chaar ghar draw kiye aur unke beech ki roads (Step 1). Poore walks yaad rakhne ki jagah, maine ek sticky note par chaar light switches lagaye — ek har ghar ke liye — aur switch on kiya jab maine woh ghar visit kiya; switches ki poori row ek single number ke roop mein padhi jaati hai jo "mask" hai (Step 2). Meri scratch grid mein ek box hai har (switch-row, ghar-jisme-main-abhi-hoon) pair ke liye, aur jo boxes claim karte hain ki main ek aisi ghar par khatam hua jiska switch off hai woh nonsense hain, toh maine unhe gray kar diya (Step 3). Maine ek akela $0$ drop kiya "sirf-ghar-switch-on, ghar-par-khada" wale box mein — sab kuch ka seed (Step 4). Mera ek rule: koi bhi box fill karne ke liye, maine woh aakhri road peel ki jo main chala, pehle se filled box lookup kiya "ek ghar pehle" ke liye, aur us road ki cost jodi, sirf sabse saste predecessor ko rakhte hue (Step 5). Maine boxes waves mein fill kiye — ek switch on, phir do, phir teen, phir charon — taaki jo bhi box main padh raha tha woh already done ho (Steps 6–7). Jab sab switches on ho gaye toh maine ek aakhri road ghar wapas pay ki aur sabse chota total liya: $18$ (Step 7). Finally maine weird cases check kiye — ek city, do cities, ek-taraf ki roads, tooti roads — taaki kuch bhi mujhe surprise na kar sake (Step 8).

Recall

dp[mask][i] mein mask physically kya hai aur integer kyun? ::: Pehle se visit ki gayi cities ka set, light switches ki tarah store kiya gaya (bit i on ⟺ city i visited). Yeh integer isliye hai kyunki DP table ko ek sasta index chahiye. Cells increasing popcount order mein kyun fill karte hain? ::: Har cell sirf ek kam switch wali cells par depend karti hai, toh switches-ki-sankhya ke order mein process karne se guarantee milti hai ki predecessors ready hain. Final +dist[i][0] kyun? ::: Ek tour ek cycle hai; DP sirf bahar chala, toh hum ek aakhri road ghar pay karte hain. Hamiltonian path ke liye ise drop karo. Running example mein optimal tour cost kya hai? ::: 18, 0→1→3→2→0 ke zariye.

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