Bitmask DP — TSP intro: Foundations — Hinglish deep dive

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

Parent note padhne se pehle, usmein use kiya gaya har notation tumhe clear hona chahiye. Ye page har cheez absolute zero se build karta hai — pehle plain words, phir picture, phir kyun is topic ko yeh chahiye. Upar se neeche padho; har block uske upar wale par lean karta hai.

0. Hum actually kaunsa problem solve kar rahe hain?

Neeche diya picture dekho. 4 dots (cities) hain jo lines (roads) se jude hain. Red loop ek possible tour hai; aur bhi bahut hain. Hum sabme se sabse sasta loop chahte hain.

1. $n$ — cities ki sankhya

Picture: $n$ dots kagaz par. Unhe "Paris, Rome…" ki jagah $0.. n - 1$ naam dena aalas nahi hai — iska matlab hai city ka naam directly ek index hai jo hum array mein seedha daal sakte hain. Yahi aadat code ko chhota rakhti hai.

Why the topic needs it

neeche har loop aur har array size

n

ke terms mein likha hai.

2. $dist [i] [j]$ — cost table

Ek spreadsheet imagine karo: cell (row $i$ , col $j$ ) mein ek road ki price hai. Parent ke 3-city example mein dist[0][1]=10 wagerah fill tha.

3. Sets, aur kyun "kaun si cities visit hui" ek set hai

Why the topic needs it

set DP table ke do indices mein se ek hai.

4. Binary digits — set ko ek integer banana

Yahi trick hai jis par poori technique ka naam hai. Hume ek set of cities ko array index ki tarah use karna hai, aur array indices plain integers hone chahiye. Set ko ek single number mein kaise pack karein?

Why the topic needs it

integer sabse sasta possible array index hai, aur

n

cities ke liye exactly

2^{n}

hote hain — DP table ka doosra index.

5. $2^{n}$ aur $2^{n} - 1$ — kitne masks hain, aur "sab visited"

6. Bit operations — mask kaise padhein aur edit karein

Hum mask ko light switches ki ek row jaisa sochtey hain, har city ke liye ek. Ye chaar moves hi hum kabhi use karte hain. Yahan &, |, ~ har bit position par independently kaam karte hain.

In operators ko poori generality mein dekhne ke liye Bit Manipulation dekho.

7. Subsets par iterate karna — masks kahan se aate hain

8. $min$ , $\infty$ , aur "impossible states"

Why the topic needs it

DP ek minimums ki table fill karta hai; jo slots legally reach nahi ho sakte woh

\infty

par rehte hain aur silently ignore ho jaate hain.

9. DP table khud — `dp[mask][i]`

Ab parent ke central definition mein har symbol earn ho chuka hai:

Yahi parent ka mnemonic SET + SPOT hai — do indices, ek kaun si cities ke liye, ek tum kahan ho ke liye. Branch and Bound usi TSP par alag tarike se attack karta hai (pruning se), lekin Held–Karp is table ko exhaustively aur cleverly fill karta hai.

Prerequisite map

Equipment checklist

Daayein side cover karo aur zor se jawab do. Agar koi ruk jaaye, toh uska section dobara padho.

Cities ko

0.. n - 1

naam dene se kya milta hai?

City ka naam directly array index hota hai, toh cities seedha dist[i][j] aur bit

i

mein daali ja sakti hain.

dist [i] [j]

mein kya hota hai, aur iska shape kya hai?

City

i

se city

j

jaane ki cost; ek 2-D grid (spreadsheet), diagonal ke paas mirror agar roads do-taraf hain.

Hum visited cities ka set kyun store karte hain, poora path order kyun nahi?

Future cost sirf us par depend karti hai kaun si cities ticked hain aur tumhara current spot kya hai; order dp value ke andar already optimise ho chuka hai, use rakhne se

n!

wapas aajata.

Visited set

{0, 2}

(

n = 4

ke saath) ko mask integer mein convert karo.

Bits (3,2,1,0)=0101 = 5.

1 ≪ i

kya hai?

Sirf bit

i

set wala integer,

2^{i}

ke barabar.

Teeno edits do: city

i

ko test / add / remove karo.

Test mask & (1<<i) non-zero; add mask | (1<<i); remove mask & ~(1<<i).

full

kaun sa integer hai aur iska set kya maane rakhta hai?

(1 ≪ n) - 1 = 2^{n} - 1

, binary all-ones — har city visited.

Kitne masks hain, aur hum sab par kaise jaate hain?

2^{n}

masks; for mask in range(1<<n) — binary mein count karna har subset ek baar enumerate karta hai.

Impossible states mein

\infty

kyun hota hai?

Yeh unreachable placeholders hain; koi bhi real cost

min

mein

\infty

ko beat kar leti hai, toh yeh answer ko kabhi corrupt nahi karte.

dp[mask][i] ek sentence mein batao.

0 se shuru hone wala sabse sasta path jo exactly mask visit kar chuka hai aur city

i

par khatam hota hai (bit

i

set hona chahiye).