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

गतिक प्रोग्रामन का चित्रात्मक निरूपण । समया है - इष्टतम उपसंरचना (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) आती है, उस मार्ग का चुनाव ही इष्टतम नियंत्रण की मुख्य समस्या है। इस समस्या का निदान गतिक प्रोग्रामन द्वारा निकलता है।

प्रोग्रामन

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

• प्रोटीन-डीएनए बाइन्डिंग के लिए लैटिस मॉडेलों के प्रतिवर्ती हल (Recurrent solutions)
• Backward induction as a solution method for finite-horizon discrete-time dynamic optimization problems
• Method of undetermined coefficients can be used to solve the Bellman equation in infinite-horizon, discrete-time, discounted, time-invariant dynamic optimization problems
• Many string algorithms including longest common subsequence, longest increasing subsequence, longest common substring, Levenshtein distance (edit distance)
• Many algorithmic problems on graphs can be solved efficiently for graphs of bounded treewidth or bounded clique-width by using dynamic programming on a tree decomposition of the graph.
• The Cocke–Younger–Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar
• Knuth's word wrapping algorithm that minimizes raggedness when word wrapping text
• The use of transposition tables and refutation tables in computer chess
• The Viterbi algorithm (used for hidden Markov models, and particularly in part of speech tagging)
• The Earley algorithm (a type of chart parser)
• The Needleman–Wunsch algorithm and other algorithms used in bioinformatics, including sequence alignment, structural alignment, RNA structure prediction
• Floyd's all-pairs shortest path algorithm
• Optimizing the order for chain matrix multiplication
• Pseudo-polynomial time algorithms for the subset sum, knapsack and partition problems
• The dynamic time warping algorithm for computing the global distance between two time series
• The Selinger (a.k.a. System R) algorithm for relational database query optimization
• De Boor algorithm for evaluating B-spline curves
• Duckworth–Lewis method for resolving the problem when games of cricket are interrupted
• The value iteration method for solving Markov decision processes
• Some graphic image edge following selection methods such as the "magnet" selection tool in Photoshop
• Some methods for solving interval scheduling problems
• Some methods for solving the travelling salesman problem, either exactly (in exponential time) or approximately (e.g. via the bitonic tour)
• Recursive least squares method
• Beat tracking in music information retrieval
• Adaptive-critic training strategy for artificial neural networks
• Stereo algorithms for solving the correspondence problem used in stereo vision
• Seam carving (content-aware image resizing)
• The Bellman–Ford algorithm for finding the shortest distance in a graph
• Some approximate solution methods for the linear search problem
• Kadane's algorithm for the maximum subarray problem
• Optimization of electric generation expansion plans in the Wein Automatic System Planning (WASP) package

गतिक प्रोग्रामन की मूल अवधारणा

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

सारणीकरण बनाम संस्मरण

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

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

इष्टतम निर्माण

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

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

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

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

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

सन्दर्भ

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

इन्हें भी देखें

• रैखिक क्रमादेशन (लिनियर प्रोग्रामिंग)
• इष्टतम नियंत्रण (Optimal control)
• इष्टतमकरण समस्या