गतिक क्रमादेशन
गणित, प्रबन्धन विज्ञान, अर्थशास्त्र, बायोइन्फॉर्मैटिक्स और कम्प्यूटर विज्ञान में गतिक क्रमादेशन या गतिक प्रोग्रामन (डाइनैमिक प्रोग्रामिंग) जटिल समस्याओं को सरल चरणों में तोड़कर हल करने के लिए एक विधि है। इसे 'गतिक इष्टतमीकरण' (डायनैमिक ऑप्टिमाइजेशन) भी कहते हैं। इसका उपयोग इष्टतमकरण (optimization) में होता है और प्रोग्रामन में ऐसी कलनविधियाँ (एल्गोरिद्म) डिजाइन करने में होता है जो कम समय में समस्या का हल निकलने में सहायक होतीं है। गतिक प्रोग्रामन का विकास १९५० के दशक में रिचर्ड बेलमैन (Richard Bellman) ने किया था।
यह उन समस्याओं पर लागू है जो अपनी तरह की छोटी समस्याओं के अतिव्यापन (Overlapping) और प्रतिवर्तन (recursion) को प्रदर्शित करती हैं। जिन स्मस्याओं पर यह लागू होती है, यह विधि सहज (naive) तरीकों से भी कम समय लेती है।
गतिक क्रमादेशन में एक बड़ी समस्या को सबसे पहले छोटी-छोटी (सरल) उपसमस्याओं के रूप में बदला जाता है। इसके बाद इन सरल समस्याओं को केवल एक बार हल किया जाता है तथा इनके हलों को संगृहीत (स्टोर) कर लिया जाता है। इस काम के लिये स्मृति-आधारित डेटा-स्ट्रक्चर का उपयोग किया जाता है। अगली बार जब भी वही उपसमस्या सामने आती है तो उसको पुनः हल करने के बजाय उसके संगृहीत हल को ले लिया जाता है। इस प्रकार कुछ स्मृति का अतिरिक्त उपयोग करके गणना में लगने वाले समय की बचत की जाती है।
उदाहरण के लिए, फिबोनाकी अनुक्रम के nवें सदस्य की गणना दो तरह से की जा सकती है।
मान लिया कि हमें codice_1 प्राप्त करना है। इसमें देख सकते हैं कि एक ऐसा 'काल ट्री' बनाते हैं जो एक ही फलन को कई बार 'काल' करता है। देखिए-जैसे कि, codice_7 का मान तीन बार निकाला गया है। यदि ५ के बजाय बड़ी संख्या का उदाहरण लिया जाय तो एक ही गणना और भी अनेक बार करनी पड़ेगी। इस कारण इसमें बहुत अधिक समय लगेगा।इस तकनीक में जिन मानों की गणना की गयी है उन्हें भण्डारित (save) भी कर दिया गया है।
इस विधि में हम छोटे मानों के लिए codice_8 की गणना से शुरू करते हैं और उनका उपयोग करते हुए बड़े मानों के लिए के codice_8 का मान निकालते हैं। इस विधि में भी O("n") समय लगता है , किन्तु इसमें भण्डारण के लिए नियत जगह (O(1)) लगती है जबकि 'ऊपर से नीचे' वाली विधि में भण्डारण के लिए O("n") जगह लगती है।
ऊपर के दोनों उदाहरणों में हम codice_7 की गणना केवल एक बर ही कर रहे हैं (बहुत बार नहीं)। फिर इसका उपयोग codice_11 उरcodice_12 दोनों की गणना करने के लिए कर रहे हैं।
गतिक प्रोग्रामन का उपयोग करके किसी इष्टतमकरण समस्या का हल निकालने के लिए उस जटिल समस्या को छोटी-छोटी सरल समस्याओं के अनुक्रम (sequence) के रूप में बदलना होता है। इष्टतमकरण समस्या की 'बहुचरणी प्रकृति' इसकी मूलभूत विशेषता है। यद्यपि सिद्धान्त रूप में यह कार्य बहुत सरल दिखता है, किन्तु वास्तविक समस्याओं के लिए ग्तिक प्रोग्रामन का उपयोग करना एक चुनौतीपूर्ण कार्य है क्योंकि प्रायः सीधे तौर पर यह बताना सरल नहीं होता कि किसी जटिल समस्या को छोटी-छोटी अतिव्यापी (overlapping) समस्याओं में कैसे तोड़ा जाय। यहीं पर अनुभव काम आता है।
नियंत्रण सिद्धान्त के में, किसी तंत्र को एक अवस्था (स्टेट) से दूसरी अवस्था में ले जाने के लिए अनेक 'मार्ग' होते हैं। इसमें से जिस 'मार्ग' से जाने पर सबसे कम 'खर्च' (cost) आती है, उस मार्ग का चुनाव ही इष्टतम नियंत्रण की मुख्य समस्या है। इस समस्या का निदान गतिक प्रोग्रामन द्वारा निकलता है।
बहुत सी कलनविधियाँ गतिक प्रोग्रामन का उपयोग करतीं हैं। नीचे कुछ उदाहरण दिए गए हैं-डायनामिक प्रोग्रामिंग मुख्य रूप से सादे पुनरावृत्ति पर अनुकूलन है। जहां भी हमें एक पुनरावर्ती समाधान दिखाई देता है, जिसमें समान इनपुट के लिए बार-बार कॉल होते हैं, तो हम इसे डायनामिक प्रोग्रामिंग का उपयोग करके अनुकूलित कर सकते हैं। यह विचार केवल उपप्रकारों के परिणामों को संग्रहित करना है, ताकि बाद में जरूरत पड़ने पर हमें उनका पुन: संगणन न करना पड़े। यह सरल अनुकूलन समय की जटिलताओं को घातीय से बहुपद तक कम करता है। उदाहरण के लिए, यदि हम फाइबोनैचि संख्याओं के लिए सरल पुनरावर्ती समाधान लिखते हैं, तो हम घातीय समय जटिलता प्राप्त करते हैं और यदि हम उपप्रकारों के समाधानों को संग्रहीत करके इसे अनुकूलित करते हैं, तो समय की जटिलता रैखिक में कम हो जाती है।
सारणीकरण बनाम संस्मरण
मूल्यों को संग्रहीत करने के दो अलग-अलग तरीके निम्नलिखित हैं ताकि एक उप-समस्या के मूल्यों का पुन: उपयोग किया जा सके। यहाँ, समस्या को हल करने के दो पैटर्न पर चर्चा करेंगे। इष्टतम निर्माण
किसी दी गई समस्या में ऑप्टिमल सबस्ट्रक्चर प्रॉपर्टी है यदि दिए गए प्रॉब्लम का इष्टतम समाधान उसके सबप्रोब्लेम्स के इष्टतम समाधानों का उपयोग करके प्राप्त किया जा सकता है। उदाहरण के लिए, सबसे छोटी पथ समस्या के पास इष्टतम सबस्ट्रक्चर प्रॉपर्टी है: यदि एक नोड x एक स्रोत नोड यू से गंतव्य नोड वी तक सबसे कम पथ में स्थित है, तो यू से वी तक का सबसे छोटा रास्ता यू से एक्स तक का सबसे छोटा मार्ग और एक्स से वी तक का सबसे छोटा मार्ग का संयोजन है। मानक सभी जोड़ी लघु पथ एल्गोरिदम। फ़्लॉइड-वॉर्सहॉल और बेलमैन-फोर्ड जैसे गतिशील प्रोग्रामिंग के विशिष्ट उदाहरण हैं।
ओवरलैपिंग उपप्रोग्राम
डिवाइड एंड कॉन्कर डायनामिक प्रोग्रामिंग की तरह उप-समस्याओं के समाधान को जोड़ती है। डायनामिक प्रोग्रामिंग का उपयोग मुख्य रूप से तब किया जाता है जब एक ही उप-उत्पाद के समाधान को बार-बार जरूरत होती है। डायनेमिक प्रोग्रामिंग में, उपप्रोम्बलों के लिए संगणित समाधानों को एक तालिका में संग्रहीत किया जाता है ताकि इन पुन: विवादित न हों। इसलिए डायनेमिक प्रोग्रामिंग उपयोगी नहीं है जब कोई सामान्य (ओवरलैपिंग) उपप्रोम्बल्स नहीं होते हैं क्योंकि समाधान की आवश्यकता नहीं होने पर समाधान को स्टोर करने का कोई बिंदु नहीं होता है। उदाहरण के लिए, द्विआधारी खोज में सामान्य उपप्रकार नहीं होते हैं। यदि हम फाइबोनैचि संख्याओं के लिए निम्न पुनरावर्ती कार्यक्रम का उदाहरण लेते हैं, तो कई उपप्रकार हैं जो बार-बार हल किए जाते हैं।
उपप्रॉपल्म्स संपत्ति को ओवरलैप करना
डिवाइड एंड कॉन्कर डायनामिक प्रोग्रामिंग की तरह उप-समस्याओं के समाधान को जोड़ती है। डायनामिक प्रोग्रामिंग का उपयोग मुख्य रूप से तब किया जाता है जब एक ही उप-उत्पाद के समाधान को बार-बार जरूरत होती है। डायनेमिक प्रोग्रामिंग में, उपप्रोम्बलों के लिए संगणित समाधानों को एक तालिका में संग्रहीत किया जाता है ताकि इन पुन: विवादित न हों। इसलिए डायनेमिक प्रोग्रामिंग उपयोगी नहीं है जब कोई सामान्य (ओवरलैपिंग) उपप्रोम्बल्स नहीं होते हैं क्योंकि समाधान की आवश्यकता नहीं होने पर समाधान को स्टोर करने का कोई बिंदु नहीं होता है। उदाहरण के लिए, द्विआधारी खोज में सामान्य उपप्रकार नहीं होते हैं।