Branch and bound: Worked examples — Hinglish deep dive

3.7.18 · D3 · Coding › Algorithm Paradigms › Branch and bound

Yeh page ek drill sheet hai. Parent note ne idea build kiya tha (branch, bound, prune). Yahan hum us idea ko har tarah ki situation mein run karte hain, taaki koi bhi case aisa na rahe jo tune pehle worked out dekha na ho.

Shuru karne se pehle, ek reminder plain words mein, kyunki neeche sab kuch isi pe lean karta hai:

Do abbreviations jo hum har jagah reuse karenge: UB = upper bound (maximize ceiling), LB = lower bound (minimize floor).

Agar inme se kuch shaky lagta hai, parent note unhe zero se build karta hai. Related tools: 0-1 Knapsack, Travelling Salesman Problem, Backtracking, Greedy Algorithms, Dynamic Programming, A* Search, Big-O Notation.

The scenario matrix

Har B&B problem inme se kisi ek case class mein aati hai. Neeche ke worked examples mein har ek ke saath [Cell 1] jaisa tag hota hai taaki tum dekh sako ki poora grid cover ho gaya hai. (Yaad karo: UB = upper bound, LB = lower bound, dono abhi upar define kiye hain.)

#	Case class	Isme tricky kya hai	Covered by
1	Maximization (upper bound UB, prune when $UB \leq incumbent$ )	inequality ki direction	Ex 1, Ex 2
2	Minimization (lower bound LB, prune when $LB \geq incumbent$ )	ulti inequality	Ex 5, Ex 6
3	Degenerate input: empty / zero capacity	kuch fit nahi hota, answer trivial hai	Ex 3
4	Everything fits (constraint inactive)	bound = take-all, koi pruning nahi hoti	Ex 4
5	Stale-node case (node wait kar raha tha tab incumbent improve hua)	pop pe bound re-check karna zaroori	Ex 7
6	Forced/forbidden decision tightens bound	bound "sahi" direction mein move karta hai	Ex 6
7	Real-world word problem	English → objective + constraint translate karo	Ex 8
8	Exam twist: wrong-direction bound trap	invalid prune pakdo	Ex 9

Example 1 — Maximization, the full knapsack tree `[Cell 1]`

Is example ke liye notation. Kisi bhi node pe hum do running numbers track karte hain jo already decided items ke baare mein hain: let $p$ = decided profit (jo items hum lene ke liye commit kar chuke hain unki total value) aur let $w$ = decided weight (unka total weight). Hum $p$ use karte hain $v$ ki jagah kyunki $v$ ka matlab density step mein ek single item ki value tha; $p$ ek branch ke along accumulated value hai.

Yahan lagu prune rule (maximization): ek node ko tab discard karo jab $UB \leq incumbent$ .

Step 1 — Densities compute karo aur sort karo. value/weight ( $v / w$ ): A $= 20$ , B $= 6$ , C $= 5$ , D $= 2$ . Order: A, B, C, D. Yeh step kyun? Fractional (relaxed) knapsack ko greedily by density solve kiya jaata hai; woh greedy value hamara bound hai, isliye density order pehle fix karna zaroori hai.

Step 2 — Root bound. Greedily fill karo fractions allow karte hue: A full $(+ 40, w = 2)$ , B full $(+ 30, w = 7)$ , C ko 10 chahiye par sirf 3 capacity bachi → fraction $\frac{3}{10} \cdot 50 = 15$ . $root bound = 40 + 30 + 15 = 85.$ Yeh step kyun? 85 woh best hai jo koi bhi finished answer hope kar sakta hai. Yeh hamare optimism ka ceiling set karta hai.

Step 3 — A pe branch karo.

Include A $(p = 40, w = 2)$ : optimistically complete karo → B full $+ 30$ , C fraction $3/10 \cdot 50 = 15$ → bound $= 85$ .
Exclude A $(p = 0, w = 0)$ : B full $+ 30 (w = 5)$ , C fraction $5/10 \cdot 50 = 25$ → bound $= 55$ .

Yeh step kyun? LC-B&B woh node expand karta hai jiska best bound ho (85 = include-A) pehle, kyunki sabse bada optimistic ceiling sabse zyada likely jagah hai jahan true optimum hoga.

Figure s01 padho (neeche ka tree). Figure exactly woh tree dikhata hai jo hum abhi build kar rahe hain: yellow ROOT (bound 85) ek blue include-A node (bound 85) aur ek pink exclude-A node (bound 55) mein split hota hai. Include-A phir Step-4 ke dono children mein split hota hai. Blue path follow karo — woh branch hai jisme B&B pehle dive karta hai kyunki uska bound sabse zyada hai. Crossed-out pink node woh hai jise hum Step 5 mein prune karte hain.

Step 4 — Include-A mein dive karo, B pe branch karo.

Include A, B $(p = 70, w = 7)$ : C fraction $3/10 \cdot 50 = 15$ → bound $= 85$ . Cap left $= 3$ , C(10) aur D(5) fit nahi hote → feasible value 70 pe finished. Yeh incumbent ban jaata hai.
Include A, exclude B $(p = 40, w = 2)$ : C ko 10 chahiye, sirf 8 bachi → fraction $8/10 \cdot 50 = 40$ → bound $= 80$ .

Yeh step kyun? Hum include-A subtree (bound 85) mein diving karte rehte hain kyunki LC-B&B hamesha sabse bade-UB wale live node ko expand karta hai; yahan ek complete leaf tak pahunchna humein pehla incumbent (70) deta hai, jo woh yardstick hai jiske against har future prune compare karta hai.

Step 5 — Incumbent 70 se prune karo. Yahan prune kyun? Maximization rule ke hisaab se, ek node tab die hota hai jab $UB \leq incumbent$ — uska best imaginable completion bhi 70 se haarta hai jo hum already hold karte hain, isliye ise explore karna help nahi kar sakta.

Exclude-A node ka bound 55 tha; test $55 \leq 70$ → true → pruned, poora subtree ek comparison mein gaya (yeh Figure s01 mein crossed-out node hai).
Include-A/exclude-B node ka bound $80$ hai; test $80 \leq 70$ → false → keep. Ise complete karo: ${A}$ se, C add karo? $2 + 10 = 12 > 10$ nahi; D add karo? $2 + 5 = 7 \leq 10$ , value $40 + 10 = 50 < 70$ . Koi improvement nahi.

Answer: maximum value $= 70$ (items A + B).

Verify: ${A, B, C, D}$ ke sab 16 subsets brute force se check karne pe max feasible value 70 milti hai. ✔ ${A, B}$ ka weight $= 7 \leq 10$ . ✔

Example 2 — Maximization, ek genuine density tie `[Cell 1]`

Example 1 jaisi hi notation: $p$ = decided profit, $w$ = branch ke along decided weight.

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ .

Step 1 — Densities aur tie. value/weight: P $= 10/2 = 5$ , Q $= 15/3 = 5$ , R $= 12/4 = 3$ . P aur Q 5 pe tie hain. Tie-break rule jo hum adopt karte hain: lighter item pehle (chhota weight zyada flexibility deta hai), isliye order hai P (w=2), Q (w=3), R (w=4). Yeh step kyun? Bound density order mein fill karke banta hai; jab do densities equal hoti hain to bound value dono taraf se identical hoti hai (same value-per-kg), par ek definite tie-break branching order ko deterministic aur reproducible rakhta hai.

Step 2 — Root bound. P full $(+ 10, w = 2)$ , Q full $(+ 15, w = 5)$ , R ko 4 chahiye, sirf 1 bachi → $\frac{1}{4} \cdot 12 = 3$ . Bound $= 10 + 15 + 3 = 28$ . Yeh step kyun? Yeh fractional fill maximization UB hai — woh optimism ceiling jo koi bhi finished answer exceed nahi kar sakta.

Step 3 — Confirm karo ki tie bound ke liye harmless hai. Fill dubara karo Q pehle P se pehle grab karte hue (tie ka doosra side): Q full $(+ 15, w = 3)$ , P full $(+ 10, w = 5)$ , R fraction $\frac{1}{4} \cdot 12 = 3$ → bound $= 28$ phir se. Yeh step kyun? Yeh is example ka poora point hai: density tie ka matlab hai ki koi bhi ordering same bound (28) deta hai, isliye tie optimistic estimate ko kabhi corrupt nahi karta — yeh sirf cosmetic branching order decide karta hai.

Step 4 — P pe branch karo aur prune karo.

Include P $(p = 10, w = 2)$ : Q full $+ 15 (w = 5)$ , R fraction $\frac{1}{4} \cdot 12 = 3$ → bound $28$ . Finish ${P, Q}$ : weight $5 \leq 6$ , value 25. Incumbent $= 25$ .
Exclude P $(p = 0)$ : Q full $+ 15 (w = 3)$ , R ko 4 chahiye, sirf 3 bachi → $\frac{3}{4} \cdot 12 = 9$ → bound $= 24$ .

Yahan prune kyun? Exclude-P pe maximization rule apply karo: test $UB = 24 \leq incumbent = 25$ → true → pruned. Uska best imaginable completion (24) already 25 se haarta hai jo haath mein hai, isliye poora exclude-P subtree ek comparison mein discard ho jaata hai.

Step 5 — Baki include-P completions check karo. ${P}$ se (w=2): include Q → upar ho gaya (25). Exclude Q, include R: $2 + 4 = 6 \leq 6$ , value $10 + 12 = 22 < 25$ . Koi improvement nahi. Yeh step kyun? Pruning ne exclude-P ko maar diya, par promising include-P subtree abhi bhi finish karna hai; sirf ek rakhe hue branch ke andar har feasible leaf check karne ke baad hum incumbent ko optimal maan sakte hain.

Answer: maximum $= 25$ (items P + Q). Tie ka lesson kyun matter karta hai: real data mein equal densities common hain; ek clear tie-break rule B&B ko deterministic rakhta hai, aur — crucially — bound tie ke liye invariant hai, isliye correctness kabhi iss par depend nahi karti ki tum pehle kaunsa tied item grab karte ho.

Verify: weight $\leq 6$ wale sab subsets pe brute force 25 deta hai; aur dono tie-orderings same root bound 28 produce karte hain. ✔

Example 3 — Degenerate: zero capacity `[Cell 3]`

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ .

Step 1 — Root bound. Capacity 0 ka fractional fill = kuch fit nahi hota → bound $= 0$ . Yeh step kyun? Zero capacity ke saath even koi bhi positive-weight item ka fraction allowed nahi hai, isliye optimistic fractional fill kuch nahi jodata.

Step 2 — Branch karo aur trivial answer confirm karo. Har "include" child ko weight $w_{i} > 0$ chahiye par capacity $0$ hai, isliye har ek infeasible hai aur live set mein kabhi aata hi nahi. Sirf "sab exclude karo" survive karta hai, value 0 ka ek complete leaf → incumbent $= 0$ . Yeh step kyun? Hume dikhana hai kyun branches vanish hoti hain: infeasibility (weight capacity se zyada) unhe kisi bound comparison se pehle hi remove kar deti hai — degenerate input poore tree ko ek empty leaf mein collapse kar deta hai.

Answer: maximum $= 0$ , empty knapsack.

Verify: ${X, Y}$ ka best feasible subset with total weight $\leq 0$ hai $\emptyset$ , value 0. ✔

Example 4 — Constraint inactive: everything fits `[Cell 4]`

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ .

Step 1 — Root bound. Total weight $= 1 + 2 + 3 = 6 \leq 100$ . Sab fit ho jaata hai → bound $= 7 + 3 + 8 = 18$ . Yeh step kyun? Jab capacity bite nahi kar sakti, fractional fill har item ko whole leta hai, isliye UB take-all value ke barabar hai.

Step 2 — Take-all leaf tak pahuncho. "Sab teen include karo" wali leaf immediately feasible hai (weight $6 \leq 100$ ) value $18$ ke saath = root bound. Incumbent $= 18$ . Yeh step kyun? Ek leaf jiska value root UB ke barabar ho woh provably optimal hai: poore tree mein kuch bhi root ceiling exceed nahi kar sakta, aur yeh leaf already usse touch kar raha hai — isliye hum believe karna band kar sakte hain ki koi doosri branch isse beat karegi.

Step 3 — Baaki sab prune ho jaata hai. Koi bhi alternative node (koi item drop karo) ka UB $\leq 18$ hoga. Rule apply karo: $UB \leq incumbent = 18$ → true → pruned (ya tie hai aur koi improvement nahi). Result: practically zero real search. Yeh step kyun? Yeh inactive-constraint behaviour dikhata hai — B&B ek single take-all node tak degenerate ho jaata hai kyunki slack constraint bound aur answer ko immediately coincide kara deta hai.

Answer: maximum $= 18$ (sab items).

Verify: sab values ka sum $= 18$ ; weight $6 \leq 100$ . ✔

Example 5 — Minimization: TSP lower bound `[Cell 2]`

Worked example Statement

4 cities, symmetric cost matrix (diagonal pe ∞):

	1	2	3	4
1	∞	10	15	20
2	10	∞	35	25
3	15	35	∞	30
4	20	25	30	∞

2-min lower bound compute karo (har city ke do saste incident edges, halved). Yahan LB = lower bound (upar define kiya hai).

Forecast: kya LB true optimal tour cost se neeche hoga, ya upar?

Yahan lagu prune rule (minimization): discard karo jab $LB \geq incumbent$ .

Step 1 — Har city ke do saste edges.

City 1: 10, 15 → 25
City 2: 10, 25 → 35
City 3: 15, 30 → 45
City 4: 20, 25 → 45

Yeh step kyun? Kisi bhi tour mein har city exactly 2 incident edges use karti hai; uske do saste edges uske contribution pe floor hain.

Step 2 — Sum karo aur halve karo. $LB = \frac{1}{2} (25 + 35 + 45 + 45) = \frac{1}{2} (150) = 75.$ $\frac{1}{2}$ kyun: har tour edge dono endpoints pe count hoti hai, isliye per-city sum double-count karta hai.

Step 3 — Ek real tour se sanity check. Tour $1 \to 2 \to 4 \to 3 \to 1$ : $10 + 25 + 30 + 15 = 80$ . Yeh step kyun? Ek LB tabhi valid hai jab woh kisi bhi genuine feasible cost se kabhi zyada na ho; hum ek real tour (cost 80) exhibit karte hain aur check karte hain $75 \leq 80$ , jo confirm karta hai ki estimate sach mein under-estimate hai — exactly jo minimization prune rule safe hone ke liye require karta hai.

Answer: LB $= 75$ ; ek genuine tour ka cost 80 hai, isliye optimum $[75, 80]$ mein hai.

Verify: LB $= 75$ ; 3 distinct Hamiltonian cycles mein se har ek ka cost $\geq 75$ hai (min tour $= 80$ ). ✔

Example 6 — Minimization: ek edge force karne se bound raise hoti hai `[Cell 6]`

Yahan lagu prune rule (minimization): discard karo jab $LB \geq incumbent$ — isliye ek zyada LB matlab zyada strong pruning.

Step 1 — City 3 ko edge(3,4)=30 use karna hi hoga. Uski doosri sasti edge 15 hai (city 1 tak). Contribution $= 30 + 15 = 45$ . Yeh step kyun? Forcing freedom khatam karti hai: city 3 ke do edges mein ab 30 zaroor shamil hona chahiye, isliye hum ek aisi sasti alternative swap nahi kar sakte jo city 4 ko ignore kare.

Step 2 — City 4 ko bhi edge(3,4)=30 use karna hoga. Uski agali sasti edge 20 hai (city 1 tak). Contribution $= 30 + 20 = 50$ . Yeh step kyun? Same logic doosre endpoint pe: city 4 bhi 30-edge mein lock hai, aur uski doosri edge uska sasta remaining option (20) hona chahiye, jo uska floor free-case 45 se 50 tak raise kar deta hai.

Step 3 — Cities 1, 2 unchanged. City 1 $= 25$ , City 2 $= 35$ . Yeh step kyun? Forced edge sirf cities 3 aur 4 ko touch karti hai; cities 1 aur 2 apni poori freedom rakhte hain, isliye unke 2-cheapest floors unchanged hain — sirf wahi recompute karo jo forcing ne actually affect kiya.

Step 4 — Nayi LB. $LB = \frac{1}{2} (25 + 35 + 45 + 50) = \frac{1}{2} (155) = 77.5.$ Yeh kyun matter karta hai: $77.5 > 75$ — ek edge force karne se lower bound tighten hua, exactly jaisa promise kiya tha. Min prune rule ( $LB \geq incumbent$ ) ke under, ek zyada LB prune zyada baar fire karta hai, isliye deeper forced decisions zyada hard prune karte hain.

Answer: forced-edge LB $= 77.5$ (75 se upar).

Verify: $77.5 > 75$ aur $77.5 \leq 80$ (real forced tour se abhi bhi neeche). ✔

Example 7 — The stale-node case `[Cell 5]`

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ .

Step 1 — Pop time pe re-test karo. Rule ab apply karo, pop time pe: $UB = 62$ , $incumbent = 65$ , test $62 \leq 65$ → true → prune $Z$ . Yeh step kyun? Incumbent improve hua (55 → 65) jab $Z$ queue mein baitha tha; insertion pe ki gayi check purana incumbent use karti thi aur ab out of date hai, isliye rule current incumbent ke against re-apply karna zaroori hai.

Step 2 — Woh bug note karo jo tumne avoid kiya. Re-check ke bina (parent pseudocode mein continue line), tum $Z$ ke poore subtree ko wastefully expand kar dete, jisme se kuch bhi 65 ko beat nahi kar sakta. Yeh step kyun? Yeh concrete failure mode ko naam deta hai — silent wasted work — taaki tum yaad rakho kyun extraction-time test exist karta hai na ki ise ek redundant duplicate maano.

Answer: $Z$ pop pe prune ho jaata hai; koi children generate nahi hote.

Verify: $62 \leq 65$ True hai, isliye extraction-time prune fire hota hai. ✔

Example 8 — Real-world word problem `[Cell 7]`

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ .

Step 1 — Model karo. Objective: total fee maximize karo. Constraint: total weight $\leq 12$ . Yeh 0/1 0-1 Knapsack hai. Yeh step kyun? "12 kg tak carry karo, items chuno, max paise" literally knapsack hai; objective aur constraint naam karna batata hai ki hume ek upper bound aur max prune rule chahiye.

Step 2 — Densities (fee/kg) aur order. J $= 12$ , K $\approx 16.7$ , L $= 15$ , N $\approx 13.3$ . Order K, L, N, J. Yeh step kyun? Fractional bound density order mein banta hai, isliye pehle sort karo.

Step 3 — Root bound. Take K fully $(+ 100, w = 6)$ . Try L (weight 8): $6 + 8 = 14 > 12$ , poora fit nahi → fraction lo, capacity left $12 - 6 = 6$ of L's 8 → $\frac{6}{8} \cdot 120 = 90$ . Bound $= 100 + 90 = 190$ . Yeh step kyun? Yeh fractional fill poore problem ke liye optimism ceiling (UB) hai; " $14 > 12$ " test exactly wahi reason hai kyun L split hota hai poora lene ki jagah.

Step 4 — K pe branch karo.

Include K $(p = 100, w = 6)$ : remaining 6 kg optimistically fill karo — L fraction $\frac{6}{8} \cdot 120 = 90$ → bound $190$ .
Exclude K $(p = 0, w = 0)$ : L full $(+ 120, w = 8)$ , N fraction? capacity left $4$ of N's 3 → N full $(+ 40, w = 11)$ , J fraction $\frac{1}{4} \cdot 60 = 15$ → bound $= 120 + 40 + 15 = 175$ .

Yeh step kyun? LC-B&B bade-UB child ko pehle expand karta hai (include K, 190), optimum ke liye sabse promising jagah.

Step 5 — Include-K mein dive karo, incumbent dhundo. ${K}$ se (w=6): density order mein agla L hai (w=8) → $6 + 8 = 14 > 12$ infeasible, isliye exclude L. Phir N (w=3) → $6 + 3 = 9 \leq 12$ , include karo → ${K, N}$ , fee $140$ . Phir J (w=5) → $9 + 5 = 14 > 12$ infeasible. Complete leaf ${K, N}$ : value 140, incumbent $= 140$ . ${K, J}$ bhi finish karo (exclude N): $6 + 5 = 11 \leq 12$ , fee $160$ → incumbent improve hokar 160 ho jaata hai. Yeh step kyun? Promising branch ke andar complete leaves tak pahunchna yardstick (160) deta hai jiske against baad ke prunes measure karte hain.

Step 6 — Exclude-K prune karo. Rule apply karo: exclude-K bound $= 175$ , test $175 \leq 160$ → false → keep aur expand karo. Isliye hum abhi ise prune nahi kar sakte; uske feasible leaves explore karo: ${L, N}$ weight $11 \leq 12$ , fee $160$ ; ${L, J}$ weight $13 > 12$ infeasible; ${L}$ akela fee 120. Yahan best $= 160$ , incumbent se tie, koi strict improvement nahi. Yeh step kyun? Yeh honest B&B outcome hai — 175 ka bound incumbent 160 se upar hai matlab exclude-K prunable nahi hai aur search karna zaroori hai; sirf uske leaves, ek baar check karne ke baad, confirm karte hain ki koi improvement nahi.

Answer: maximum fee $= ₹160$ (L+N carry karo, ya K+J).

Verify: weight $\leq 12$ wale sab subsets pe brute force max fee 160 deta hai. ✔

Example 9 — Exam twist: invalid prune pakdo `[Cell 8]`

Yahan lagu prune rule (maximization): discard karo jab $UB \leq incumbent$ — aur note karo UB word: bound ek over-estimate hona chahiye.

Step 1 — Yaad karo bound exactly kya hona chahiye. Maximization ke liye bound ek upper bound (UB) hona chahiye — subtree ki sab cheez ka ek guaranteed over-estimate. Sirf tab prune karo jab even the best possible completion $\leq$ incumbent ho. Yeh step kyun? Pruning ek proof of hopelessness hai; proof sirf tabhi valid hai jab hum jo number compare karte hain woh branch ka optimistic ceiling ho, koi chhoti quantity nahi.

Step 2 — Student ke estimate ko classify karo. "Ek best item jo fit ho, lo" yeh ignore karta hai ki subtree kaafi saare items ko saath mein pack kar sakti hai, isliye yeh achievable value ko under-state karta hai — yeh ek lower bound hai, upper bound nahi. Yeh step kyun? Estimate ki direction ko naam dena crux hai: UB ki jagah mein lower bound hona safety argument ko silently invert kar deta hai.

Step 3 — Counterexample banao. Suppose karo yeh node actually value 50 tak complete ho sakti hai items combine karke (capacity ke andar fully allowed), jabki one-best-item score sirf 30 hai. Student ka test $30 \leq 45$ node ko prune karta hai — par uska true best $50 > 45$ incumbent improve karta. Optimum delete ho jaata hai. Yeh step kyun? Ek concrete number ( $50 > 45$ jo score of $30$ ke peeche chhupa hai) abstract worry ko ek provable failure mein badal deta hai.

Step 4 — Verdict. Prune invalid hai. Fix: Ex 1 ki tarah fractional (relaxed) upper bound use karo, jo ek provable over-estimate hai, isliye $UB \leq incumbent$ genuinely hopelessness prove karta hai. Yeh step kyun? Yeh loop close karta hai — trap "pruning" nahi balki "wrong-direction bound ke against pruning" hai, aur remedy relaxation-based UB hai.

Answer: SAFE nahi hai. Ek under-estimate ko incumbent se compare karna correctness todta hai — 30 score wali ek subtree mein true optimum 50 ho sakta hai.

Verify: ek subtree value $50 > 45$ hold kar sakti hai jabki uska pessimistic score $30 \leq 45$ hai, isliye prune unsound hai. ✔

Recall Quick self-test

Yeh ek collapsible review block hai (kholne ke liye title click karo). Har line neeche Question ::: Answer format mein likhi hai — question padho, apne dimag mein answer karo, phir ::: ke baad text se check karo.

Maximization: ek node ko prune karo jab uska bound ... ::: $\leq$ incumbent ho (bound ek over-estimate hai, yaani UB). Minimization: ek node ko prune karo jab uska bound ... ::: $\geq$ incumbent ho (bound ek under-estimate hai, yaani LB). Density tie ke saath, kya tied item ko pehle grab karne ki choice bound ko change karti hai? ::: Nahi — equal densities same value-per-kg deti hain, isliye fractional bound identical hai; tie-break sirf branching order fix karta hai. TSP tour mein ek edge force karne se lower bound ... ::: raise hoti hai (ya equal rehti hai) — kabhi fall nahi karti. Node pop karte waqt bound re-check kyun karte hain? ::: kyunki node queue mein wait karte waqt incumbent improve ho sakta hai, jisse node ab prunable ho jaata hai bhale hi insertion pe check pass hua tha. Ex 8 mein exclude-K ko kyun search karna padta hai, prune nahi? ::: uska bound 175 > incumbent 160 hai, isliye prune rule (UB ≤ incumbent) false hai; node tabhi prune hota hai jab even uska best case haare.