गतिक क्रमादेशन

मुक्त ज्ञानकोश विकिपीडिया से
Jump to navigation Jump to search
गतिक प्रोग्रामन का चित्रात्मक निरूपण । समया है - इष्टतम उपसंरचना (optimal substructure) का उपयोग करते हुए किसी मानचित्र में सबसे छोटा मार्ग पता करना। इसमें सरल रेखा ऐसे मार्ग को दिखाती है जिसमें बीच में दूसरा मार्ग नहीं निकलता ; तथा तरंगित रेखा किन्हीं दो बिन्दुओं के बीच सबसे छोटा मार्ग को निरुपित करती है। (इन दो बिन्दुओं के बीच के अन्य मार्ग नहीं दिखाए गए हैं जो अपेक्षाकृत बड़ी दूरी वाले हैं।)। मोटी रेखा में जो मार्ग दिखाया गया है वह आरम्भ से लेकर लक्ष्य तक का सबसे छोटा मार्ग है।

गणित, प्रबन्धन विज्ञान, अर्थशास्त्र, बायोइन्फॉर्मैटिक्स और कम्प्यूटर विज्ञान में गतिक क्रमादेशन या गतिक प्रोग्रामन (डाइनैमिक प्रोग्रामिंग) जटिल समस्याओं को सरल चरणों में तोड़कर हल करने के लिए एक विधि है। इसे 'गतिक इष्टतमीकरण' (डायनैमिक ऑप्टिमाइजेशन) भी कहते हैं। इसका उपयोग इष्टतमकरण (optimization) में होता है और प्रोग्रामन में ऐसी कलनविधियाँ (एल्गोरिद्म) डिजाइन करने में होता है जो कम समय में समस्या का हल निकलने में सहायक होतीं है। गतिक प्रोग्रामन का विकास १९५० के दशक में रिचर्ड बेलमैन (Richard Bellman) ने किया था।

यह उन समस्याओं पर लागू है जो अपनी तरह की छोटी समस्याओं के अतिव्यापन (Overlapping) और प्रतिवर्तन (recursion) को प्रदर्शित करती हैं। जिन स्मस्याओं पर यह लागू होती है, यह विधि सहज (naive) तरीकों से भी कम समय लेती है।

गतिक क्रमादेशन में एक बड़ी समस्या को सबसे पहले छोटी-छोटी (सरल) उपसमस्याओं के रूप में बदला जाता है। इसके बाद इन सरल समस्याओं को केवल एक बार हल किया जाता है तथा इनके हलों को संगृहीत (स्टोर) कर लिया जाता है। इस काम के लिये स्मृति-आधारित डेटा-स्ट्रक्चर का उपयोग किया जाता है। अगली बार जब भी वही उपसमस्या सामने आती है तो उसको पुनः हल करने के बजाय उसके संगृहीत हल को ले लिया जाता है। इस प्रकार कुछ स्मृति का अतिरिक्त उपयोग करके गणना में लगने वाले समय की बचत की जाती है।

उदाहरण के लिए, फिबोनाकी अनुक्रम के nवें सदस्य की गणना दो तरह से की जा सकती है।

साधारण विधि से
   function fib(n)
       if n <= 1 return n
       return fib(n − 1) + fib(n − 2)

मान लिया कि हमें fib(5) प्राप्त करना है। इसमें देख सकते हैं कि एक ऐसा 'काल ट्री' बनाते हैं जो एक ही फलन को कई बार 'काल' करता है। देखिए-

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

जैसे कि, fib(2) का मान तीन बार निकाला गया है। यदि ५ के बजाय बड़ी संख्या का उदाहरण लिया जाय तो एक ही गणना और भी अनेक बार करनी पड़ेगी। इस कारण इसमें बहुत अधिक समय लगेगा।

'ऊपर से नीचे' गतिक प्रोग्रामन द्वारा
   var m := map(0 → 0, 1 → 1)
   function fib(n)
       if key n is not in map m 
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

इस तकनीक में जिन मानों की गणना की गयी है उन्हें भण्डारित (save) भी कर दिया गया है।

'नीचे से ऊपर' गतिक प्रोग्रामन द्वारा

इस विधि में हम छोटे मानों के लिए fib की गणना से शुरू करते हैं और उनका उपयोग करते हुए बड़े मानों के लिए के fib का मान निकालते हैं। इस विधि में भी O(n) समय लगता है , किन्तु इसमें भण्डारण के लिए नियत जगह (O(1)) लगती है जबकि 'ऊपर से नीचे' वाली विधि में भण्डारण के लिए O(n) जगह लगती है।

   function fib(n)
       if n = 0
           return 0
       else
           var previousFib := 0, currentFib := 1
           repeat n − 1 times // loop is skipped if n = 1
               var newFib := previousFib + currentFib
               previousFib := currentFib
               currentFib  := newFib
       return currentFib

ऊपर के दोनों उदाहरणों में हम fib(2) की गणना केवल एक बर ही कर रहे हैं (बहुत बार नहीं)। फिर इसका उपयोग fib(4) उरfib(3) दोनों की गणना करने के लिए कर रहे हैं।

उपयोग[संपादित करें]

इष्टतमकरण[संपादित करें]

गतिक प्रोग्रामन का उपयोग करके किसी इष्टतमकरण समस्या का हल निकालने के लिए उस जटिल समस्या को छोटी-छोटी सरल समस्याओं के अनुक्रम (sequence) के रूप में बदलना होता है। इष्टतमकरण समस्या की 'बहुचरणी प्रकृति' इसकी मूलभूत विशेषता है। यद्यपि सिद्धान्त रूप में यह कार्य बहुत सरल दिखता है, किन्तु वास्तविक समस्याओं के लिए ग्तिक प्रोग्रामन का उपयोग करना एक चुनौतीपूर्ण कार्य है क्योंकि प्रायः सीधे तौर पर यह बताना सरल नहीं होता कि किसी जटिल समस्या को छोटी-छोटी अतिव्यापी (overlapping) समस्याओं में कैसे तोड़ा जाय। यहीं पर अनुभव काम आता है।

नियंत्रण सिद्धान्त[संपादित करें]

नियंत्रण सिद्धान्त के में, किसी तंत्र को एक अवस्था (स्टेट) से दूसरी अवस्था में ले जाने के लिए अनेक 'मार्ग' होते हैं। इसमें से जिस 'मार्ग' से जाने पर सबसे कम 'खर्च' (cost) आती है, उस मार्ग का चुनाव ही इष्टतम नियंत्रण की मुख्य समस्या है। इस समस्या का निदान गतिक प्रोग्रामन द्वारा निकलता है।

प्रोग्रामन[संपादित करें]

बहुत सी कलनविधियाँ गतिक प्रोग्रामन का उपयोग करतीं हैं। नीचे कुछ उदाहरण दिए गए हैं-

गतिक प्रोग्रामन की मूल अवधारणा[संपादित करें]

डायनामिक प्रोग्रामिंग मुख्य रूप से सादे पुनरावृत्ति पर अनुकूलन है। जहां भी हमें एक पुनरावर्ती समाधान दिखाई देता है, जिसमें समान इनपुट के लिए बार-बार कॉल होते हैं, तो हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके अनुकूलित कर सकते हैं। यह विचार केवल उपप्रकारों के परिणामों को संग्रहित करना है, ताकि बाद में जरूरत पड़ने पर हमें उनका पुन: संगणन न करना पड़े। यह सरल अनुकूलन समय की जटिलताओं को घातीय से बहुपद तक कम करता है। उदाहरण के लिए, यदि हम फाइबोनैचि संख्याओं के लिए सरल पुनरावर्ती समाधान लिखते हैं, तो हम घातीय समय जटिलता प्राप्त करते हैं और यदि हम उपप्रकारों के समाधानों को संग्रहीत करके इसे अनुकूलित करते हैं, तो समय की जटिलता रैखिक में कम हो जाती है।

सारणीकरण बनाम संस्मरण[2]

मूल्यों को संग्रहीत करने के दो अलग-अलग तरीके निम्नलिखित हैं ताकि एक उप-समस्या के मूल्यों का पुन: उपयोग किया जा सके। यहाँ, डायनामिक प्रोग्रामिंग समस्या को हल करने के दो पैटर्न पर चर्चा करेंगे।

  • सारणीकरण(निचला भाग)
  • संस्मरण (ऊपर नीचे)

इष्टतम निर्माण[3]

किसी दी गई समस्या में ऑप्टिमल सबस्ट्रक्चर प्रॉपर्टी है यदि दिए गए प्रॉब्लम का इष्टतम समाधान उसके सबप्रोब्लेम्स के इष्टतम समाधानों का उपयोग करके प्राप्त किया जा सकता है। उदाहरण के लिए, सबसे छोटी पथ समस्या के पास इष्टतम सबस्ट्रक्चर प्रॉपर्टी है: यदि एक नोड x एक स्रोत नोड यू से गंतव्य नोड वी तक सबसे कम पथ में स्थित है, तो यू से वी तक का सबसे छोटा रास्ता यू से एक्स तक का सबसे छोटा मार्ग और एक्स से वी तक का सबसे छोटा मार्ग का संयोजन है। मानक सभी जोड़ी लघु पथ एल्गोरिदम। फ़्लॉइड-वॉर्सहॉल और बेलमैन-फोर्ड जैसे गतिशील प्रोग्रामिंग के विशिष्ट उदाहरण हैं।

ओवरलैपिंग उपप्रोग्राम[4]

डिवाइड एंड कॉन्कर डायनामिक प्रोग्रामिंग की तरह उप-समस्याओं के समाधान को जोड़ती है। डायनामिक प्रोग्रामिंग का उपयोग मुख्य रूप से तब किया जाता है जब एक ही उप-उत्पाद के समाधान को बार-बार जरूरत होती है। डायनेमिक प्रोग्रामिंग में, उपप्रोम्बलों के लिए संगणित समाधानों को एक तालिका में संग्रहीत किया जाता है ताकि इन पुन: विवादित न हों। इसलिए डायनेमिक प्रोग्रामिंग उपयोगी नहीं है जब कोई सामान्य (ओवरलैपिंग) उपप्रोम्बल्स नहीं होते हैं क्योंकि समाधान की आवश्यकता नहीं होने पर समाधान को स्टोर करने का कोई बिंदु नहीं होता है। उदाहरण के लिए, द्विआधारी खोज में सामान्य उपप्रकार नहीं होते हैं। यदि हम फाइबोनैचि संख्याओं के लिए निम्न पुनरावर्ती कार्यक्रम का उदाहरण लेते हैं, तो कई उपप्रकार हैं जो बार-बार हल किए जाते हैं।

उपप्रॉपल्म्स संपत्ति को ओवरलैप करना

डिवाइड एंड कॉन्कर डायनामिक प्रोग्रामिंग की तरह उप-समस्याओं के समाधान को जोड़ती है। डायनामिक प्रोग्रामिंग का उपयोग मुख्य रूप से तब किया जाता है जब एक ही उप-उत्पाद के समाधान को बार-बार जरूरत होती है। डायनेमिक प्रोग्रामिंग में, उपप्रोम्बलों के लिए संगणित समाधानों को एक तालिका में संग्रहीत किया जाता है ताकि इन पुन: विवादित न हों। इसलिए डायनेमिक प्रोग्रामिंग उपयोगी नहीं है जब कोई सामान्य (ओवरलैपिंग) उपप्रोम्बल्स नहीं होते हैं क्योंकि समाधान की आवश्यकता नहीं होने पर समाधान को स्टोर करने का कोई बिंदु नहीं होता है। उदाहरण के लिए, द्विआधारी खोज में सामान्य उपप्रकार नहीं होते हैं।

सन्दर्भ[संपादित करें]

  1. सन्दर्भ त्रुटि: <ref> का गलत प्रयोग; Eddy नाम के संदर्भ में जानकारी नहीं है।
  2. "Dynamic Programming". GeeksforGeeks (अंग्रेज़ी में). अभिगमन तिथि 2020-08-22.
  3. "Introduction to Dynamic Programming 1 Tutorials & Notes | Algorithms". HackerEarth (अंग्रेज़ी में). अभिगमन तिथि 2020-08-22.
  4. "Dynamic programming", Wikipedia (अंग्रेज़ी में), 2020-08-22, अभिगमन तिथि 2020-08-22
  1. https://www.geeksforgeeks.org/dynamic-programming/#concepts
  2. https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/
  3. https://www.codechef.com/wiki/tutorial-dynamic-programming
  4. https://en.wikipedia.org/wiki/Dynamic_programming

इन्हें भी देखें[संपादित करें]