Bitmask DP — TSP intro — Hinglish notes

3.7.15 · Coding › Algorithm Paradigms

WHY a bitmask?

State aur recurrence (scratch se derive karo)

Hum ise kaise build karte hain? Last step ke baare mein socho. $i$ pe khade hone ke liye aur mask visit kar chuke hone ke liye, tumhe zaroor kisi pehle wale city $j$ se aana pada hoga jo mask mein bhi hai, $j \neq = i$ , aur jisne mask minus $i$ visit kiya tha. Hum saare aise $j$ pe minimize karte hain:

Complexity (aur 80/20)

Worked example 1 — 3 cities by hand

Cities $0, 1, 2$ . Distances (symmetric): $dist [0] [1] = 10, dist [0] [2] = 15, dist [1] [2] = 20$ .

Base: dp[001][0] = dp[1][0] = 0.

Step	State	Compute	Yeh step kyun?
1	`dp[011][1]`	`dp[001][0]+dist[0][1] = 0+10 = 10`	Start se city 1 add karo. mask `011`={0,1}, last=1.
2	`dp[101][2]`	`dp[001][0]+dist[0][2] = 0+15 = 15`	Start se city 2 add karo.
3	`dp[111][2]`	`dp[011][1]+dist[1][2] = 10+20 = 30`	Sab visited, 1→2 se aaye.
4	`dp[111][1]`	`dp[101][2]+dist[2][1] = 15+20 = 35`	Sab visited, 2→1 se aaye.
5	Close	$min (30 + dist [2] [0], 35 + dist [1] [0])$	Start pe wapas jao.
		$min (30 + 15, 35 + 10) = min (45, 45) = 45$	Tour cost = 45.

Dono routes $0 \to 1 \to 2 \to 0$ aur $0 \to 2 \to 1 \to 0$ ka cost 45 hai (symmetric triangle), toh 45 optimal hai. ✓

Worked example 2 — bits padhna

Maano $n = 4$ aur tum dp[mask][3] compute kar rahe ho jahan mask = 1011 (binary) $= 11$ .

Yeh step kyun? 1011 ka bit 3 1 hai? 1011 → bits hain (3210)=1011, bit3=1 ✓ toh city 3 endpoint ke roop mein allowed hai.
prev = mask & ~(1<<3) = 1011 & 0111 = 0011 $= {0, 1}$ .
Yeh step kyun? Humein 3 pe prev mein already kisi city se aana pada hoga, toh $j \in {0, 1}$ .
dp[11][3] = min( dp[3][0]+dist[0][3], dp[3][1]+dist[1][3] ).

Reference implementation

INF = float('inf')
def tsp(dist):
    n = len(dist)
    dp = [[INF]*n for _ in range(1<<n)]
    dp[1][0] = 0                       # base: at 0, visited {0}
    for mask in range(1<<n):
        for i in range(n):
            if dp[mask][i] == INF:     # unreachable, skip
                continue
            for k in range(n):         # try going to city k next
                if mask & (1<<k):      # already visited -> skip
                    continue
                nm = mask | (1<<k)
                nd = dp[mask][i] + dist[i][k]
                if nd < dp[nm][k]:
                    dp[nm][k] = nd
    full = (1<<n)-1
    return min(dp[full][i] + dist[i][0] for i in range(1,n))

Note: yeh version forward push karta hai (mask → nm); upar wali recurrence backward pull karti hai. Same DP hai, do iteration directions — dono valid hain kyunki masks sirf badhte hain.

Common mistake Steel-manned traps

1. "Order matter karta hai, toh mujhe sequence store karni chahiye." Sahi lagta hai kyunki tours mein obviously ek order hota hai. Fix: sirf visited set + current city remaining cost ko affect karte hain; prefix ka internal order dp value ke andar already optimise ho chuka hai. Order store karna wapas $n!$ tak explode kar dega.

2. dp[mask][i] ke liye bit $i$ ka mask mein set hona bhool jaana. Sahi lagta hai ki saare $i$ pe loop karein. Fix: agar city $i$ visited nahi hai, toh " $i$ pe khatam hona" meaningless hai — woh state $\infty$ rehti hai. Guard lagao: if mask & (1<<i).

3. Return edge bhool jaana. Sahi lagta hai kyunki dp ne sab kuch visit kar liya hai. Fix: TSP ek cycle hai; end mein + dist[i][0] add karo. Isse sirf tab skip karo jab Hamiltonian path chahiye.

4. Operator precedence. mask & 1<<i kaam karta hai (shift tighter bind karta hai), lekin mask & 1 == 0 nahi karta (== & se tighter bind karta hai). Hamesha parenthesise karo: (mask & x) == 0.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho tumhe har dost ke ghar ek baar jaana hai aur kam se kam chalke ghar wapas aana hai. Poora path yaad rakhne ki jagah, tum sirf do cheezein ek sticky note pe likhte ho: kaun se ghar ho chuke hain (tick boxes) aur abhi kis ke ghar khade ho. Agar do alag walks ne tumhe same "tick boxes + current house" pe pahuncha diya, toh ab se dono same hain — toh sirf sasta wala rakho aur doosra phenko. Woh sticky notes bitmask hain. Duplicates phenkna hi reason hai ki yeh fast hai.

Active recall

TSP bitmask DP mein dp[mask][i] kya store karta hai?

City 0 se shuru hone wale, exactly set mask visit karne wale, aur city i pe khatam hone wale (mask mein bit i set) path ki min cost.

Bitmask DP

n!

brute force ko kyun beat karta hai?

Yeh saare orderings jo same (visited-set, current-city) pe pahunchte hain unhe ek state mein collapse karta hai,

O (n!)

ki jagah

O (n^{2} 2^{n})

deta hai.

Base case kya hai?

dp[1][0] = 0 (sirf city 0 visited, 0 pe khade ho, cost 0); baaki sab

\infty

Transition likho.

dp[mask][i] = min over j in prev of dp[prev][j] + dist[j][i], jahan prev = mask & ~(1<<i).

Final closed-tour answer kaise nikaalte ho?

min over i!=0 of dp[(1<<n)-1][i] + dist[i][0].

City i mask mein hai ya nahi kaise test karte ho?

mask & (1<<i) non-zero hai.

Mask se city i kaise remove karte ho?

mask & ~(1<<i).

Time aur space complexity?

Time

O (n^{2} 2^{n})

, space

O (n 2^{n})

dp[mask][i] valid hone ke liye bit i mask mein set kyun hona chahiye?

"i pe khatam hona" require karta hai ki i visit ho chuka ho; warna state impossible hai aur

\infty

rehti hai.

Agar cycle ki jagah Hamiltonian path chahiye toh kya badalta hai?

+dist[i][0] return term drop karo; answer ban jaata hai min_i dp[full][i].

Connections

Dynamic Programming — state, optimal substructure, overlapping subproblems.
Travelling Salesman Problem — woh NP-hard problem jise yeh chhote $n$ ke liye exactly solve karta hai.
Held-Karp Algorithm — is exact DP ka formal naam.
Bit Manipulation — masks, shifts, and-not.
Subset Enumeration — $2^{n}$ subsets pe iterate karna.
Hamiltonian Path and Cycle — valid tour kya hota hai.
Branch and Bound — bade $n$ ke liye alternative exact method.