Greedy choice: exchange proof और counterexample
लक्ष्य और पूर्वज्ञान
Sorting, asymptotic bounds और sets आधार हैं। Greedy algorithm स्थानीय अच्छी choice लेकर उसे वापस नहीं बदलता। Optimality के लिए objective, feasibility constraints, choice rule और यह सिद्ध करें कि कोई optimum उस choice को शामिल कर सकता है। “अभी अच्छा लगता है” proof नहीं। केवल optimal substructure पर्याप्त नहीं; DP में भी यह हो सकता है जबकि greedy rule गलत हो।
1. Unweighted interval scheduling
हर activity half-open [s,f), s<f है। एक resource पर अधिकतम nonoverlapping activities चुनें। Endpoint पर छूने वाली activities compatible हैं। Finish time के nondecreasing क्रम में sort करें। Scan में start>=last accepted finish होने पर accept करें; शुरुआत में कोई accepted activity नहीं। समान finish पर कोई भी tie-break मान्य है।
उदाहरण A=[0,3), B=[1,2), C=[2,4), D=[3,5), E=[4,6)। Finish order B,A,C,D,E। B accept, A reject, C accept, D reject, E accept: तीन activities। Shortest-duration या earliest-start अलग algorithms हैं।
2. Exchange proof
g सबसे जल्दी finish होने वाली activity हो। Optimal nonempty schedule O की पहली activity o लें। f(g)<=f(o), इसलिए o की जगह g रखें। O की हर बाद की activity f(o) के बाद शुरू होती है, अतः f(g) के बाद भी। Replacement से feasibility और count दोनों बचते हैं। इसलिए कोई optimum g से शुरू होता है। शेष instance में start>=f(g) वाली activities हैं; उसी argument को छोटे instance पर लगाएँ। Induction maximum cardinality सिद्ध करता है; empty instance base case है।
Exchange केवल पहली choice बदलता है, objective नहीं घटाता। यह activities के equal value पर निर्भर है। Sort O(n log n), scan O(n)। Input finish-sorted हो तो केवल scan O(n)।
3. Counterexamples से assumptions जाँचें
Earliest-start: [0,10), [1,2), [2,3), [3,4)। Rule केवल पहला लेता है; बाकी तीन compatible हैं। Weighted case में earliest-finish भी गलत: [0,1) value 1 और [0,2) value 100 overlap हैं। Rule 1 लेता है, optimum 100। Earlier finish से replacement value घटा सकता है; cardinality proof लागू नहीं।
Coin-change में denominations जरूरी हैं। Unlimited {1,3,4}, amount 6: largest-first 4+1+1, तीन coins; 3+3 में दो। परिचित currency का अनुभव arbitrary denominations का proof नहीं। अगला DP पाठ यही counterexample हल करता है।
4. Density कहाँ सही है
Fractional knapsack में item बाँट सकते हैं, weights positive, values nonnegative, और fraction का value linear है। Value/weight descending sort करके capacity भरें। यदि lower-density weight लिया है और higher-density weight उपलब्ध है, equal weight exchange value कम नहीं करता; densities अलग हों तो बढ़ाता है। Repeated exchanges से density-ordered optimum मिलता है।
0/1 indivisible items में equal-weight fraction exchange illegal हो सकता है। Capacity 50 और (weight,value)=(10,60),(20,100),(30,120): density-first पहले दो लेकर 160 देता है; अंतिम दो 220 देते हैं। Fractional में पहले दो और तीसरे का 20/30 लेकर 240 वैध है; 0/1 में नहीं।
Proof checklist
कौन-सा solution बदल रहे हैं, exchange के बाद feasibility, objective comparison और छोटा remaining problem लिखें। एक counterexample universal claim गलत करता है; कई सफल examples proof नहीं। यह design principle का पाठ है, नए specialized greedy catalogue का नहीं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Unweighted interval scheduling की सिद्ध greedy choice:
A. सबसे जल्दी start B. सबसे छोटी duration C. सबसे जल्दी finish D. सबसे बड़ा interval
उत्तर: C
A: लंबी early activity कई रोकती है।
B: यह सिद्ध rule नहीं।
C: Exchange count और future feasibility बचाता है।
D: बड़े intervals alternatives रोकते हैं।
P02. बताए convention में [1,3),[3,5) compatible हैं?
A. हाँ B. नहीं C. केवल समान weights पर D. एक छोटा करने पर
उत्तर: A
A: Half-open intervals endpoint छू सकते हैं।
B: Occupied time overlap नहीं।
C: Weights overlap तय नहीं करते।
D: बदलाव जरूरी नहीं।
P03. Coins {1,3,4}, amount 6 पर largest-first कितने coins?
A. 1 B. 2 C. 3 D. 6
उत्तर: C
A: 6 coin नहीं।
B: दो optimum है, greedy trace नहीं।
C: Greedy 4+1+1।
D: पहले 4 लेता है, सारे ones नहीं।
P04. Weighted activities में unweighted exchange proof क्यों टूटता है?
A. Sorting असंभव B. Replacement total value घटा सकता है C. Endpoints छू नहीं सकते D. Weights length बदलते हैं
उत्तर: B
A: Sort फिर भी संभव है।
B: Equal count का अर्थ equal value नहीं।
C: Convention वही रह सकता है।
D: Weights time length नहीं बदलते।
P05. Capacity 50, items (10,60),(20,100),(30,120): optimal 0/1 value?
A. 160 B. 180 C. 220 D. 240
उत्तर: C
A: पहले दो का density greedy suboptimal है।
B: पहला/तीसरा feasible पर कम।
C: दूसरा/तीसरा weight 50,value 220।
D: 240 में fraction चाहिए।
P06. Valid exchange proof में क्या दिखाना होगा?
A. केवल local choice तेज है B. Exchange के बाद feasibility और objective न घटना C. सभी optima identical D. हर item चुना जाए
उत्तर: B
A: Speed optimality proof नहीं।
B: Optimum में replacement के लिए दोनों चाहिए।
C: Multiple optima संभव हैं।
D: Feasibility में items छोड़ने पड़ सकते हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन