विभाजन-और-जीत, लोभी, तथा गतिक प्रोग्रामन

पाठ्यक्रम तीन अभिकल्प-तकनीकें नामित करता है, और परीक्षणीय प्रश्न विरलतः यह होता है कि किसी को कैसे कार्यान्वित करें — वह यह है कि कौन-सी लागू है, और लघु-मार्ग सुरक्षित है या नहीं। तीनों समस्या को उप-समस्याओं में तोड़ती हैं; उन्हें यह पृथक् करता है कि टुकड़े परस्पर कैसे संबंधित हैं। विभाजन-और-जीत उन उप-समस्याओं में बाँटती है जो अतिव्यापित नहीं होतीं, उन्हें स्वतंत्र रूप से हल कर संयोजित करती है, इसीलिए उसकी लागत स्वच्छ पुनरावृत्ति है। गतिक प्रोग्रामन तब लागू है जब उप-समस्याएँ अतिव्यापित होती हैं: वही उप-समस्या अनेक बार चाहिए होती है, अतः वह एक बार हल कर संचित की जाती है, और चरघातांकी पुनरावर्तन बहुपदी सारणी में ढह जाता है। लोभी तब लागू है जब कुछ अधिक प्रबल सत्य हो — कि स्थानीय रूप से सर्वोत्तम चुनाव वैश्विक रूप से सर्वोत्तम हल का अंग है — और सम्पूर्ण कठिनाई यह है कि यह कभी असत्य होता है और सदा विश्वसनीय लगता है। स्वच्छतम प्रदर्शन नैपसैक है। भिन्नात्मक संस्करण में प्रति एकांक भार मूल्य के क्रम में वस्तुएँ लेना उपपाद्य रूप से अनुकूलतम है, क्योंकि बची क्षमता अगली वस्तु के अंश से भरी जा सकती है। 0/1 संस्करण में वही नियम सरलतः गलत है: 50 क्षमता तथा 10, 20 व 30 भार पर 60, 100 व 120 मूल्य की वस्तुओं के साथ लोभी नियम 10 व 20 लेकर 160 पाता है, जबकि अनुकूलतम 20 व 30 लेकर 220 है। जाँचने तक लोभी चुनाव में कुछ भी असुरक्षित नहीं लगता, और वही शिक्षा है — लोभी को उपपत्ति चाहिए, और परीक्षा जाँचती है कि आप जानते हैं किन समस्याओं के पास वह है। जहाँ नहीं है वहाँ गतिक प्रोग्रामन ही सहारा है।

कौन-सी तकनीक, और क्यों

तीनों तकनीकें, अपनी मान्यताओं से
तकनीकआवश्यकताएक मानक उदाहरण
विभाजन-और-जीतऐसी उप-समस्याएँ जो अतिव्यापित न होंमर्ज सॉर्ट, द्विआधारी खोज, काराचुबा
गतिक प्रोग्रामनअतिव्यापी उप-समस्याएँ तथा अनुकूलतम उप-संरचनाLCS, 0/1 नैपसैक, आव्यूह-शृंखला, फ़्लॉयड–वॉरशॉल
लोभीएक उपपाद्य लोभी-चुनाव गुणभिन्नात्मक नैपसैक, हफ़मैन, क्रुस्कल, कार्य-चयन
⚠️ नैपसैक: वही वस्तुएँ, वही क्षमता, दो भिन्न उत्तर
क्षमता 50; भार 10, 20, 30 की वस्तुएँ मूल्य 60, 100, 120 सहित, अतः प्रति एकांक भार अनुपात 6, 5 व 4। भिन्नात्मक: 10 व 20 पूरी लें, फिर तीसरी का 20/30, कुल 60 + 100 + 80 = 240, और अनुपात से लोभी उपपाद्य रूप से अनुकूलतम है। 0/1: वही लोभी नियम 10 व 20 लेकर भार 30 पर रुक जाता है, 20 क्षमता अप्रयोज्य छोड़ते हुए, कुल 160। अनुकूलतम यह है कि सर्वोच्च-अनुपात वस्तु पूर्णतः छोड़कर 20 व 30 लें, कुल 220। अतः जो लोभी नियम एक संस्करण पर उपपाद्य रूप से सही है वह दूसरे पर 37% कम है, और नियम में कुछ भी अंतर का संकेत नहीं देता। इसीलिए 0/1 नैपसैक को O(nW) की गतिक-प्रोग्रामन सारणी चाहिए, और इसीलिए परीक्षा बार-बार पूछती है कि उसने आपको कौन-सा संस्करण दिया है।

गतिक प्रोग्रामन, तथा सारणी का आकार

गतिक प्रोग्राम एक सारणी तथा एक पुनरावृत्ति है, और उसकी जटिलता प्रायः सदा (कोष्ठों की संख्या) × (प्रति कोष्ठ काम) है। वही एक वाक्य इस विषय के अधिकांश जटिलता-प्रश्नों का उत्तर बिना किसी विश्लेषण दे देता है: लंबाई m व n की मालाओं के LCS की m × n सारणी है जिसका प्रत्येक कोष्ठ O(1) में भरता है, अतः O(mn); 0/1 नैपसैक की n × W सारणी है, अतः O(nW); आव्यूह-शृंखला गुणन की n × n सारणी है जिसका प्रत्येक कोष्ठ n विभाजन-बिंदु तक आज़माता है, अतः O(n³)।

🎯 O(nW) निवेश-आकार में बहुपदी क्यों नहीं है
यही वह सूक्ष्मता है जिसे स्पष्ट रखना उपयोगी है, क्योंकि वह विरोधाभास जैसी लगती है। 0/1 नैपसैक NP-कठिन है, फिर भी यहाँ O(nW) कलनविधि है — तो कैसे? क्योंकि W एक मान है, आकार नहीं। संख्या W लिखने में केवल log W बिट लगते हैं, अतः W के अनुपाती समय में चलती कलनविधि अपने निवेश की लंबाई में चरघातांकी है। उसे छद्म-बहुपदी कहते हैं, और इसीलिए सारणी-विधि 1000 क्षमता हेतु पूर्णतः व्यावहारिक और 2⁶⁴ क्षमता हेतु निरर्थक है। O(nW), NP-कठिनता का खंडन करता है या नहीं यह पूछता प्रश्न ठीक यही पूछ रहा है, और उत्तर है कि नहीं करता।

LCS को स्थिर करने हेतु एक हल किया आँकड़ा: AGGTAB व GXTXAYB का दीर्घतम सामान्य उप-अनुक्रम GTAB है, लंबाई 4। ध्यान दें कि उप-अनुक्रम को संलग्न होना आवश्यक नहीं — वही उसे उप-माला से पृथक् करता है, और दोनों को भ्रमित करना O(mn) गतिक प्रोग्राम को भिन्न व सरल समस्या बना देता है।

जहाँ लोभी उपपाद्य है: हफ़मैन

हफ़मैन कूटन वह लोभी कलनविधि है जिसकी उपपत्ति सर्वाधिक स्वच्छ है: बारंबार दो सबसे कम बारंबार प्रतीक मिलाएँ, और परिणाम अनुकूलतम उपसर्ग-कूट होता है। बारंबारताएँ 5, 9, 12, 13, 16 व 45 लें। मिलानों की लागत 14, 25, 30, 44 व 100 है, योग 224, जो कुल कूटित लंबाई भी है — और दोनों सहमत हैं क्योंकि प्रत्येक मिलान अपने नीचे के प्रत्येक प्रतीक में एक बिट जोड़ता है।

परिणामी कूट-लंबाइयाँ, तथा कुल
बारंबारताकूट-लंबाईयोगदान
45145
16348
13339
12336
9436
5420
कुल—224 बिट
🧠 सर्वाधिक बारंबार प्रतीक को सबसे छोटा कूट मिलता है, और वृक्ष अद्वितीय नहीं
दो तथ्य समय बचाते हैं। सर्वाधिक बारंबार प्रतीक को सदा सबसे छोटा कूट मिलता है — यहाँ 45 को एक ही बिट — अतः वह प्रश्न जिसमें विरल प्रतीक का कूट सामान्य प्रतीक से छोटा हो, कुछ भी बनाए बिना अस्वीकार किया जा सकता है। और वृक्ष अद्वितीय नहीं है: प्राथमिकता-कतार में बराबरी किसी भी प्रकार तोड़ी जा सकती है, जो समान कुल लंबाई सहित भिन्न वृक्ष देती है, अतः कुल पूछता प्रश्न सुगठित है जबकि किसी विशिष्ट प्रतीक का कूट पूछता प्रश्न नहीं भी हो सकता। उत्तर बराबरी-तोड़ पर निर्भर है या नहीं यह जाँचना उसमें लगने वाले दो सेकंड के योग्य है।

मुख्य बिंदु

  • विभाजन-और-जीत को अ-अतिव्यापी उप-समस्याएँ चाहिए; गतिक प्रोग्रामन इसलिए है कि वे अतिव्यापित होती हैं।
  • लोभी को उपपाद्य लोभी-चुनाव गुण चाहिए — वह कभी असत्य होता है और सदा विश्वसनीय लगता है।
  • अनुपात से लोभी भिन्नात्मक नैपसैक हेतु अनुकूलतम व 0/1 हेतु गलत है: 240 बनाम 220 अनुकूलतम व 160 लोभी।
  • गतिक प्रोग्राम की लागत (कोष्ठ-संख्या) × (प्रति कोष्ठ काम) है: LCS O(mn), नैपसैक O(nW), आव्यूह-शृंखला O(n³)।
  • O(nW) छद्म-बहुपदी है — W मान है, आकार नहीं — अतः वह NP-कठिनता का खंडन नहीं करता।
  • उप-अनुक्रम को संलग्न होना आवश्यक नहीं; उप-माला को होना ही है।
  • हफ़मैन दो सबसे कम बारंबार प्रतीक मिलाता है; 5, 9, 12, 13, 16, 45 पर कुल 224 बिट है।
  • सर्वाधिक बारंबार प्रतीक को सबसे छोटा कूट मिलता है, और हफ़मैन वृक्ष अद्वितीय नहीं पर उसका कुल है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. 0/1 नैपसैक की क्षमता 50 है तथा वस्तुएँ भार 10, 20, 30 व मूल्य 60, 100, 120 की हैं। अधिकतम कुल मूल्य क्या है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 220

    सर्वोत्तम 0/1 चुनाव 20 व 30 है, क्षमता ठीक भरते हुए 100 + 120 = 220। प्रति भार मूल्य से लोभी 10 (अनुपात 6) व 20 (अनुपात 5) लेता, भार 30 पर पहुँचता, और 30 को समा नहीं पाता — 160 पर रुकते हुए। और भिन्नात्मक उत्तर 240 है, अंतिम वस्तु का दो-तिहाई लेते हुए। एक वस्तु-सूची हेतु तीन भिन्न संख्याएँ, और कौन-सी सही है यह पूर्णतः इस पर निर्भर है कि वस्तुएँ विभाजित हो सकती हैं या नहीं। कुछ भी निकालने से पूर्व प्रश्न से वह पढ़ना ही सम्पूर्ण कौशल है; 240 उस प्रश्न का उत्तर है जो पूछा नहीं गया।

  2. प्रति एकांक भार मूल्य से लोभी उपपाद्य रूप से अनुकूलतम है:

    1. 0/1 नैपसैक हेतु
    2. भिन्नात्मक नैपसैक हेतु
    3. दोनों हेतु
    4. किसी हेतु नहीं
    उत्तर देखें

    उत्तर: B — भिन्नात्मक नैपसैक हेतु

    केवल भिन्नात्मक संस्करण हेतु। उपपत्ति इस पर निर्भर है कि बची किसी भी क्षमता को अगली-सर्वोत्तम वस्तु के अंश से भरा जा सके, अतः कोई क्षमता कभी व्यर्थ नहीं जाती — विभाज्यता हटाएँ और तर्क ढह जाता है, क्योंकि बचा अंतराल कुछ भी न समा सके। ऊपर का उदाहरण हानि दिखाता है: जहाँ 220 उपलब्ध है वहाँ लोभी 160 पाता है। विकल्प C वह उत्तर है जो अभ्यर्थी भिन्नात्मक स्थिति पर लोभी को काम करते देखकर सामान्यीकरण से देता है, और ठीक वही आदत तोड़ने हेतु यह युग्म है। 0/1 को गतिक प्रोग्रामन चाहिए, O(nW) पर।

  3. प्रतीकों की बारंबारताएँ 5, 9, 12, 13, 16 व 45 हैं। अनुकूलतम हफ़मैन कूटन की कुल लंबाई बिटों में क्या है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 224

    हर बार दो सबसे कम बारंबार मिलाने पर 14 (5+9), 25 (12+13), 30 (14+16), 44 (कतार-क्रम से 25+30…) तथा अंततः 100 के मिलान मिलते हैं, और मिलान-लागतों का योग 224 है — जो कुल कूटित लंबाई है, क्योंकि प्रत्येक मिलान अपने नीचे के प्रत्येक प्रतीक में एक बिट जोड़ता है। दूसरे प्रकार से जाँचने पर सहमति मिलती है: 45, 16, 13, 12, 9, 5 हेतु कूट-लंबाइयाँ 1, 3, 3, 3, 4, 4 निकलती हैं, और 45×1 + 16×3 + 13×3 + 12×3 + 9×4 + 5×4 = 224। दोनों प्रकार से निकालना यहाँ विश्वसनीय आदत है, क्योंकि मिलान-योग विधि तेज़ है और लंबाई-विधि गलत बने वृक्ष को पकड़ती है।

  4. 0/1 नैपसैक गतिक प्रोग्राम O(nW) में चलता है। चूँकि 0/1 नैपसैक NP-कठिन है, इसका अर्थ है:

    1. P = NP
    2. परिबंध छद्म-बहुपदी है, क्योंकि W मान है, निवेश-आकार नहीं
    3. कलनविधि गलत है
    4. 0/1 नैपसैक वस्तुतः P में है
    उत्तर देखें

    उत्तर: B — परिबंध छद्म-बहुपदी है, क्योंकि W मान है, निवेश-आकार नहीं

    क्षमता W लिखने में लगभग log₂W बिट लगते हैं, अतः जिस कलनविधि का चलन-समय W के अनुपाती है वह उस निवेश की लंबाई में चरघातांकी है। उसे छद्म-बहुपदी कहते हैं, और वह प्रत्यक्ष विरोधाभास को किसी को अस्थिर किए बिना सुलझा देती है: कलनविधि सही है, समस्या अभी भी NP-कठिन है, और P बनाम NP के विषय में कोई दावा नहीं। व्यावहारिक पाठ ही उपयोगी है — सारणी-विधि कुछ हज़ार क्षमता हेतु ठीक है और 64-बिट क्षमता हेतु निराशाजनक, और वह उदाहरण की संख्याओं के विषय में कथन है, वस्तुओं की संख्या के विषय में नहीं।

  5. AGGTAB व GXTXAYB का दीर्घतम सामान्य उप-अनुक्रम कितना लंबा है?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 4

    LCS है GTAB, लंबाई 4। अक्षरों को किसी भी माला में सटा होना आवश्यक नहीं — वही उसे उप-माला के बजाय उप-अनुक्रम बनाता है, और संलग्न मेल ढूँढ़ता अभ्यर्थी केवल लंबाई 1 या 2 पाता है। गतिक प्रोग्राम m × n सारणी है जहाँ अक्षर मिलने पर कोष्ठ 1 + विकर्ण है और अन्यथा अपने दोनों पड़ोसियों में बड़ा, अतः लागत O(mn) है — यहाँ 6 × 7 = 42 कोष्ठ। उप-अनुक्रम बनाम उप-माला का भेद स्पष्ट रूप से पढ़ने योग्य है, क्योंकि दोनों समस्याओं के उत्तर व कलनविधियाँ भिन्न हैं।

  6. अनुकूलतम हफ़मैन कूट के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

    1. सर्वाधिक बारंबार प्रतीक का कूट किसी कम बारंबार प्रतीक से लंबा कभी नहीं होता
    2. कोई कूट-शब्द किसी अन्य का उपसर्ग नहीं होता
    3. दी गई बारंबारताओं हेतु वृक्ष अद्वितीय होता है
    4. सभी कूट-शब्दों की लंबाई समान होती है
    उत्तर देखें

    उत्तर: A — सर्वाधिक बारंबार प्रतीक का कूट किसी कम बारंबार प्रतीक से लंबा कभी नहीं होता; B — कोई कूट-शब्द किसी अन्य का उपसर्ग नहीं होता

    A व B। A यहाँ अनुकूलतमता का अर्थ ही है — यदि किसी विरल प्रतीक का कूट छोटा होता, तो दोनों की अदला-बदली कुल घटा देती, अतः किसी अनुकूलतम कूट की वह आकृति नहीं हो सकती, और यह आपको प्रस्तावित निर्दिष्टीकरण देखते ही अस्वीकार करने देता है। B उपसर्ग-मुक्त गुण है, जो कूट को विभाजकों के बिना विकोडनीय बनाता है और प्रत्याभूत है क्योंकि प्रत्येक प्रतीक पत्ती पर बैठता है। C असत्य है: प्राथमिकता-कतार में बराबरी किसी भी प्रकार टूट सकती है, अतः कई भिन्न वृक्ष वही कुल प्राप्त करते हैं — यहाँ 224 — इसीलिए कुल पूछता प्रश्न सुगठित है और कोई विशेष कूट-शब्द पूछता प्रश्न नहीं भी हो सकता। D नियत-लंबाई कूट का वर्णन करता है, जिसे हफ़मैन सुधारता है।

  7. आव्यूह-शृंखला गुणन गतिक प्रोग्रामन से हल होता है:

    1. O(n²)
    2. O(n³)
    3. O(2ⁿ)
    4. O(n log n)
    उत्तर देखें

    उत्तर: B — O(n³)

    O(n³), सीधे उस नियम से कि गतिक प्रोग्राम की लागत कोष्ठ × प्रति कोष्ठ काम है: सारणी उप-शृंखलाओं पर n × n है, और एक कोष्ठ भरना उस उप-शृंखला के भीतर प्रत्येक विभाजन-बिंदु आज़माता है, जो n तक हैं। विकल्प C सभी कोष्ठकनों को सूचीबद्ध करने की लागत है, जो कैटलन-अनेक है और ठीक वही जिसे टालने हेतु सारणी है। यह वह मानक प्रदर्शन भी है कि गुणन का क्रम उत्तर बदले बिना महत्व रखता है — गुणनफल वही है, अदिश गुणनों की संख्या नहीं, और इसीलिए समस्या हल करने योग्य है।

  8. गतिक प्रोग्रामन साधारण विभाजन-और-जीत से वरीय ठीक तब है जब:

    1. समस्या न्यूनीकरण समस्या हो
    2. उप-समस्याएँ अतिव्यापित हों, अतः वही एक बारंबार हल हो
    3. निवेश वर्गीकृत हो
    4. पुनरावर्तन दो स्तर से अधिक गहरा हो
    उत्तर देखें

    उत्तर: B — उप-समस्याएँ अतिव्यापित हों, अतः वही एक बारंबार हल हो

    अतिव्यापी उप-समस्याएँ ही सम्पूर्ण शर्त हैं, और दोनों तकनीकें उसी अंतर पर घूमती हैं। मर्ज सॉर्ट के आधे असंयुक्त हैं, अतः परिणाम संचित करने से कुछ न मिलता — पुनरावृत्ति कभी नहीं होती। फिबोनाची व LCS वही उप-समस्या अनेक बार देखते हैं, अतः संचय चरघातांकी पुनरावर्तन को बहुपदी सारणी में ढहा देता है। गतिक प्रोग्रामन को दूसरी शर्त अनुकूलतम उप-संरचना चाहिए, कि अनुकूलतम हल उप-समस्याओं के अनुकूलतम हलों से बने; उसके बिना सारणी वे उत्तर संचित करती जिन्हें संयोजित नहीं किया जा सकता। विकल्प A अप्रासंगिक है — बहुत से गतिक प्रोग्राम अधिकतम करते हैं, और बहुत सी विभाजन-और-जीत कलनविधियाँ कुछ भी अनुकूलित नहीं करतीं।