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

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

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

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

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

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

    **function** fib(n)
        **if** n 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) भी कर दिया गया है। 

; 'नीचे से ऊपर' गतिक प्रोग्रामन द्वारा
इस विधि में हम छोटे मानों के लिए <code>fib</code> की गणना से शुरू करते हैं  और उनका उपयोग करते हुए बड़े मानों के लिए के <code>fib</code> का मान निकालते हैं। इस विधि में भी 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

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

==उपयोग==
===इष्टतमकरण===
गतिक प्रोग्रामन का उपयोग करके किसी इष्टतमकरण समस्या का हल निकालने के लिए उस जटिल समस्या को छोटी-छोटी सरल समस्याओं के अनुक्रम (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, [[discounting|discounted]], [[Time-invariant system|time-invariant]] dynamic optimization problems
* Many [[String (computer science)|string]] algorithms including [[longest common subsequence problem|longest common subsequence]], [[Longest increasing subsequence problem|longest increasing subsequence]], [[Longest common substring problem|longest common substring]], [[Levenshtein distance]] (edit distance)
* Many algorithmic problems on [[undirected graph|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 [[CYK algorithm|Cocke–Younger–Kasami (CYK) algorithm]] which determines whether and how a given string can be generated by a given [[context-free grammar]]
* [[Word wrap|Knuth's word wrapping algorithm]] that minimizes raggedness when word wrapping text
* The use of [[transposition table]]s and [[refutation table]]s in [[computer chess]]
* The [[Viterbi algorithm]] (used for [[hidden Markov model]]s, 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|RNA structure prediction]] 
* [[Floyd–Warshall algorithm|Floyd's all-pairs shortest path algorithm]]
* Optimizing the order for [[chain matrix multiplication]]
* [[Pseudo-polynomial time]] algorithms for the [[subset sum problem|subset sum]], [[Knapsack problem|knapsack]] and [[Partition problem|partition]] problems
* The [[dynamic time warping]] algorithm for computing the global distance between two time series
* The [[Patricia Selinger|Selinger]] (a.k.a. [[IBM System R|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 process]]es
* 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 (music)|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 [https://www-pub.iaea.org/MTCD/publications/PDF/CMS-16.pdf Wein Automatic System Planning (WASP)] package

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

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

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

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

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

किसी दी गई समस्या में ऑप्टिमल सबस्ट्रक्चर प्रॉपर्टी है यदि दिए गए प्रॉब्लम का इष्टतम समाधान उसके सबप्रोब्लेम्स के इष्टतम समाधानों का उपयोग करके प्राप्त किया जा सकता है। उदाहरण के लिए, सबसे छोटी पथ समस्या के पास इष्टतम सबस्ट्रक्चर प्रॉपर्टी है: यदि एक नोड 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)
*इष्टतमकरण समस्या

श्रेणी:इष्टतमीकरण