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

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

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

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

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

    function fib(n)
        if n <= 1 return n
        return fib(n − 1) + fib(n − 2)

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

 fib(5)
 fib(4) + fib(3)
 (fib(3) + fib(2)) + (fib(2) + fib(1))
 ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
 (((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 एक स्रोत नोड यू से गंतव्य नोड वी तक सबसे कम पथ में स्थित है, तो यू से वी तक का सबसे छोटा रास्ता यू से एक्स तक का सबसे छोटा मार्ग और एक्स से वी तक का सबसे छोटा मार्ग का संयोजन है। मानक सभी जोड़ी लघु पथ एल्गोरिदम। फ़्लॉइड-वॉर्सहॉल और बेलमैन-फोर्ड जैसे गतिशील प्रोग्रामिंग के विशिष्ट उदाहरण हैं।

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

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

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

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

सन्दर्भ

 https://www.geeksforgeeks.org/dynamic-programming/#concepts
 https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/tutorial/
 https://www.codechef.com/wiki/tutorial-dynamic-programming
 https://en.wikipedia.org/wiki/Dynamic_programming

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

इष्टतमीकरण