Bitmask DP — TSP intro: Question bank — Hinglish deep dive

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

Worked example Usi DP ko iterate karne ke do tarike

Recurrence predecessors ko pull karta hai; neeche diya code successors ko push karta hai. Dono sahi hain kyunki masks sirf badhte hain, isliye ek chhota mask hamesha khatam ho jaata hai usse pehle ki koi bada mask use kare.

INF = float('inf')          # INF symbol ∞ ka code naam hai
 
# --- PULL (backward): dp[mask][i] ko chhote prev se fill karo ---
def tsp_pull(dist):
    n = len(dist)
    full = (1 << n) - 1
    dp = [[INF]*n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):     # i visited hona chahiye taaki i par end ho
                continue
            prev = mask & ~(1 << i)       # i par arrive karne se pehle wala set
            for j in range(n):
                if prev & (1 << j):       # sirf real predecessors
                    cand = dp[prev][j] + dist[j][i]
                    if cand < dp[mask][i]:
                        dp[mask][i] = cand
    return min(dp[full][i] + dist[i][0] for i in range(1, n))
 
# --- PUSH (forward): dp[mask][i] ko bade masks mein spread karo ---
def tsp_push(dist):
    n = len(dist)
    full = (1 << n) - 1
    dp = [[INF]*n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == INF:        # unreached, push karne ko kuch nahi
                continue
            for k in range(n):
                if mask & (1 << k):       # k pehle se visited hai -> skip
                    continue
                nm = mask | (1 << k)
                cand = dp[mask][i] + dist[i][k]
                if cand < dp[nm][k]:
                    dp[nm][k] = cand
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

True or false — justify

Do orderings jo same set visit karein aur same city par end hon woh future ke liye interchangeable hain.

True. Remaining cost sirf visited set aur current spot (SET + SPOT) par depend karta hai; already-visited prefix ke internal order ka kisi bhi future edge par koi effect nahi, isliye hum sirf sasta prefix rakhte hain.

dp[mask][i] sabse sasta tour store karta hai.

False. Ye city 0 se city

i

tak ka sabse sasta path store karta hai jo exactly mask visit karta hai — abhi tak koi return edge nahi. Tour cost tabhi aata hai jab tum full mask par dist[i][0] add karo.

Tum tour kisi bhi city se shuru kar sakte ho, isliye base case mein sabhi starting cities par loop chahiye.

False. Ek cycle ka koi distinguished start nahi hota; start ko city 0 par fix karne se koi tour nahi chhoot-ta (har cycle 0 se guzarti hai). Ek base case dp[1][0]=0 kaafi hai, aur isse

n

ka ek factor bach jaata hai.

Bitmask DP sirf tab kaam karta hai jab distance matrix symmetric ho.

False. Recurrence dist[j][i] ko ek specific direction mein use karta hai, isliye ye asymmetric costs (dist[i][j] != dist[j][i]) bhi sahi handle karta hai. Symmetry sirf worked example mein convenience ke liye thi.

Ek fixed mask ke liye,

0 \leq i < n

wale har dp[mask][i] entry ka ek meaningful value hota hai.

False. Sirf wahi entries meaningful hain jahan bit

i

, mask mein set ho; "ek unvisited city par end karna" impossible hai, isliye woh

\infty

rehte hain.

DP states ki sankhya

2^{n}

hai.

False. Ye

n \cdot 2^{n}

hai — ek axis

2^{n}

subsets (SET) ke liye aur ek axis

n

possible current cities (SPOT) ke liye.

Bitmask DP ek Hamiltonian cycle tab bhi dhundh leta hai jab graph mein kuch edges missing hon.

True, agar tum missing edges ko

\infty

model karo. Koi bhi transition jo ek missing edge use kare woh

\infty

add kar deta hai aur kabhi min jeet nahi sakta, isliye infeasible tours automatically discard ho jaate hain; agar sab candidates

\infty

hain, toh koi cycle exist nahi karta.

Forward push karna (mask → mask|(1<<k)) aur backward pull karna (prev → mask) alag-alag answers dete hain.

False. Ye upar dikhaye gaye do variants hain — same DP opposite directions mein traverse kiya gaya. Kyunki masks sirf bits gain karte hain, har predecessor prev mask se strictly chhota integer hota hai, isliye masks ko increasing order mein iterate karna dono tarafon se safe hai.

Agar

n = 0

n = 1

ho, toh closed-tour formula min over i!=0 theek hai.

False.

n = 1

ke saath koi

i \neq = 0

nahi hota aur

n = 0

ke saath city 0 hi nahi hoti, isliye min ek empty set par run karta hai (error /

\infty

). Dono degenerate sizes ko special-case karna zaroori hai.

Spot the error

if mask & 1<<i == 0: sahi tarike se test karta hai ki city

i

absent hai ya nahi.

Actually ye sahi hai — Python mein & ka binding == se tighter hota hai, isliye ye (mask & (1<<i)) == 0 parse hota hai, jo sahi test hai. Lekin ye fragile aur padhne mein mushkil hai; trap ye hai ki + jaisa koi operator swap karne se precedence toot jaata, isliye experienced coders phir bhi (mask & (1<<i)) == 0 explicitly likhte hain.

Koi for i in range(n): dp[mask][i] = ... loop karta hai bina bit

i

check kiye.

Error. Woh aise endpoints ke liye values compute karte hain jo kabhi visit hi nahi hue, table ko pollute karte hue. if mask & (1<<i) se guard karo (skip karo) — ek unvisited endpoint

\infty

rehna chahiye.

Answer min(dp[full][i] for i in range(n)) ke roop mein return kiya jaata hai jahan full = (1<<n)-1.

Error (do bugs). Ye

i = 0

ko include karta hai (ek "tour" jo wahan khatam hota hai jahan shuru hua bina travel ke) aur return edge bhool jaata hai. Sahi closed-tour answer: min(dp[full][i] + dist[i][0] for i in range(1,n)).

City

i

remove karne ke liye, code likhta hai mask & (1<<i).

Error. Ye bit

i

ko isolate karta hai, remove nahi. Remove karna hai mask & ~(1<<i); ~ (NOT) mask ko flip karta hai taaki bit

i

0 ho jaaye aur baaki sab rahe.

prev = mask & ~(1<<i) compute kiya jaata hai, phir code sabhi

j

par for j in range(n) loop karta hai.

Error. Tumhe sirf woh

j

lene chahiye jo actually prev mein hain (yani prev & (1<<j)); warna tum

\infty

entries padhoge ya, aur bura, ek invalid predecessor path. Inner loop ko guard karo.

Ek unreachable state detect karne aur kaam skip karne ke liye, code check karta hai if dp[mask][i] > 0: continue.

Error. Ek reachable state ka legitimately positive cost ho sakta hai. Sahi skip test hai if dp[mask][i] == INF: continue (yaad raho INF

\infty

hai) — sirf truly unreachable states hi ise carry karte hain.

dp = [[0]*n for _ in range(1<<n)] se initialize karna.

Error. Saare states 0 cost par reachable shuru hote hain, isliye min kabhi kuch rule out nahi karta — har garbage transition free lagti hai. INF (

= \infty

) se initialize karna zaroori hai aur sirf dp[1][0] = 0 set karo.

Why questions

Hum table ko ek integer mask se kyun index karte hain, Python set se nahi?

DP table ko ek sasta, fixed-range index chahiye, aur integer sabse chhota possible option hai;

2^{n}

subsets exactly integers

0 \dots 2^{n} - 1

par map hote hain, isliye array lookup

O (1)

hai.

Pehli edge (last nahi) ko peel karna — DP likhne ka sahi tarika kyun hai?

State fix karta hai tum abhi kahan ho (city

i

), isliye natural unknown hai "main yahan kaise pahuncha?" — last edge

j \to i

. Use peel karne se ek strictly chhota sub-state (prev, j) expose hota hai jo hum pehle hi solve kar chuke hain.

Optimal-substructure argument zaroori kyun hai (sirf acha-sa lagta isliye nahi)?

DP tabhi valid hoti hai jab optimal whole, optimal parts se bana ho. Agar (prev,j) tak ek sasta sub-path exist karta, hum use splice karke dp[mask][i] ko beat kar sakte — contradiction — aur yahi min ko justify karta hai. Formal statement ke liye Held-Karp Algorithm dekho.

Orderings collapse karne se

n!

kaise

\sim n^{2} 2^{n}

ban jaata hai?

n!

orderings hain lekin sirf

n \cdot 2^{n}

distinct (SET, SPOT) states; kaafi orderings ek state share karti hain aur hum sirf best rakhte hain, isliye kaam orderings se nahi, states se scale hota hai.

Hum simply greedy approach nahi le sakte aur hamesha nearest unvisited city par nahi chal sakte?

Greed locally optimal hai lekin globally nahi: ek sasti early edge baad mein mahangi edges force kar sakti hai. TSP mein koi greedy-safe choice nahi hai, isliye hume saare predecessors par minimize karna padta hai.

n \approx 20

practical ceiling kyun hai?

Memory

O (n 2^{n})

hai aur time

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

;

n = 20

par ye

\sim 4 \times 1 0^{8}

operations hain — feasible — lekin har agla city kaam roughly double kar deta hai, isliye

n = 25

already ~

1 0^{10}

hai. Branch and Bound ise heuristically aage push karne ke liye use hota hai.

Missing edge ko

\infty

model karna (delete karne ki jagah) code ko simple kyun rakhta hai?

Har transition min of sums hai; ek

\infty

summand kabhi minimum nahi ho sakta, isliye infeasible moves automatically filter ho jaate hain bina kisi special-case branching ke.

Start city fix karne se koi optimal tour kyun nahi chhoot-ta?

Ek tour ek cycle hai, aur sabhi cities par har cycle city 0 se exactly ek baar guzarti hai; cycle ko 0 par begin karne ke liye rotate karne se same cost milti hai, isliye koi optimum nahi chhoot-ta.

Edge cases

n = 0

(empty city set) ke liye algorithm kya return karta hai?

Koi city 0 nahi hai, isliye dp[1][0] exist hi nahi karta aur full = 0; poora formulation undefined hai. DP mein enter karne se pehle

n = 0

ko special case treat karo (cost 0, ya convention se "no tour").

n = 1

(ek city) ke liye algorithm kya return karta hai?

Ek city ka closed tour cost 0 hai (wahan raho), lekin formula min over i!=0 empty hai aur special-case karna padega;

n = 1

ko explicitly guard karo.

Do cities, sirf

dist [0] [1]

known aur symmetric — tour kya hai?

0 \to 1 \to 0

cost

dist [0] [1] + dist [1] [0]

ke saath. DP dp[full][1] produce karta hai, phir return edge add karta hai; kuch bhi degenerate nahi hai jab tak dono directions exist karein.

Graph disconnected hai (koi Hamiltonian cycle exist nahi karta). Kya hota hai?

Har full-mask endpoint ya return edge mein ek

\infty

involve hota hai, isliye final min

\infty

hai — algorithm sahi tarike se "no tour" report karta hai crash karne ki jagah.

Ek self-loop dist[i][i] > 0 hai. Kya ye kabhi use hota hai?

Nahi. City

k

par transition sirf tab liya jaata hai jab

k

mask mein nahi hota, isliye tum kabhi

i

i

nahi jaate; self-loop costs DP ke liye irrelevant hain.

Tum ek Hamiltonian path chahte ho (sab visit karo, return nahi). Kya single change chahiye?

+ dist[i][0] return term drop karo; answer min over all i of dp[full][i] ban jaata hai, aur ab start aur end equal nahi hona chahiye.

Distances negative ho sakti hain (jaise rewards). Kya DP phir bhi kaam karta hai?

min recurrence phir bhi sabse sasta visit-all path sahi dhundhta hai, kyunki ye non-negativity assume nahi karta (Dijkstra ke unlike). Lekin "sabse sasta" tabhi unbounded ho sakta hai jab negatives ek repeatable loop banate — yahan impossible hai kyunki har city ek baar visit hoti hai.

Saari distances ek constant

c

ke barabar hain. Har tour ka cost kya hai?

Exactly

n \cdot c

(

n

cities par cycle mein

n

edges hain), isliye har ordering tie karta hai aur DP

n c

return karta hai — ye ek acha sanity check hai ki koi edge double-count ya drop nahi hua.

Recall Ek-line self-test

Agar tum ye teen bina notes ke answer kar sako toh tum trap-space ke maalik ho: State ke do indices kya hain, aur exactly do hi kyun? ::: SET (visited mask) aur SPOT (current city); ye akele do facts hain jo remaining cost affect karte hain. Woh single guard kya hai jo impossible endpoints ko bahar rakhta hai? ::: if mask & (1<<i) — city $i$ wahan end hone ke liye mask mein honi chahiye. Woh single term kya hai jo log closed tour ke liye bhool jaate hain? ::: Return edge + dist[i][0].

Connections

Travelling Salesman Problem — woh problem jiske andar ye traps rehte hain.
Held-Karp Algorithm — is exact DP ka formal naam.
Dynamic Programming — optimal substructure min ko justify karta hai.
Bit Manipulation · Subset Enumeration — mask machinery.
Hamiltonian Path and Cycle — path-vs-cycle edge cases.
Branch and Bound — $n \approx 20$ ke baad kya use karein.