डायनामिक प्रोग्रामिंग

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

Definition

डायनामिक प्रोग्रामिंग एक ऐसी विधि है जो अतिव्यापी उप-समस्याओं के संदर्भ में पुनरावर्ती रूप से अपने मूल्य को परिभाषित करके और प्रत्येक विशिष्ट उप-समस्या को ठीक एक बार गणना करके, परिणाम को कैश करके एक अनुकूलन या गणना समस्या को हल करती है ताकि इसे पुनर्गणना के बजाय पुन: उपयोग किया जा सके।

Scope

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

Core questions

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

Key concepts

• इष्टतम उप-संरचना
• अतिव्यापी उप-समस्याएँ
• इष्टतमता का सिद्धांत
• मेमोइज़ेशन
• टैबुलेशन
• स्टेट स्पेस और पुनरावृत्ति
• सबसे लंबी सामान्य अनुवर्ती
• एडिट डिस्टेंस
• नैपसैक समस्या

Key theories

इष्टतमता का सिद्धांत

बेलमैन का इष्टतमता का सिद्धांत बताता है कि एक इष्टतम नीति में यह गुण होता है कि, प्रारंभिक स्थिति और निर्णय कुछ भी हो, शेष निर्णय परिणामी स्थिति के लिए एक इष्टतम नीति का गठन करना चाहिए — डायनामिक प्रोग्रामिंग पुनरावृत्तियों का औपचारिक आधार।

मेमोइज़ेशन बनाम टैबुलेशन

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

Clinical relevance

डायनामिक प्रोग्रामिंग व्यवहार में सर्वव्यापी है: कम्प्यूटेशनल जीव विज्ञान में अनुक्रम संरेखण (नीडलमैन-वंश, स्मिथ-वाटरमैन), वर्तनी-जाँच और संस्करण-नियंत्रण अंतर में एडिट डिस्टेंस, वाक् पहचान और संचार में विटरबी एल्गोरिथम, और संचालन अनुसंधान, वित्त और सुदृढीकरण सीखने में डायनामिक प्रोग्राम।

History

रिचर्ड बेलमैन ने 1950 के दशक में RAND कॉर्पोरेशन में रहते हुए डायनामिक प्रोग्रामिंग विकसित की, आंशिक रूप से शोध प्रायोजकों के लिए स्वीकार्य होने के लिए नाम चुना। इष्टतमता का सिद्धांत और बेलमैन समीकरण संचालन अनुसंधान, नियंत्रण सिद्धांत और कंप्यूटर विज्ञान में मूलभूत बन गए, और इस तकनीक को बाद में एल्गोरिदम पाठ्यपुस्तकों में एक मुख्य एल्गोरिथम प्रतिमान के रूप में संहिताबद्ध किया गया।

Key figures

• Richard Bellman
• Thomas H. Cormen
• Jon Kleinberg
• Éva Tardos

Seminal works

• bellman1957
• cormen2009

Frequently asked questions

डिवाइड-एंड-कॉन्कर और डायनामिक प्रोग्रामिंग में क्या अंतर है?

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

डायनामिक प्रोग्रामिंग कब लागू नहीं होती है?

इसके लिए इष्टतम उप-संरचना और विशिष्ट उप-समस्याओं के बहुपद-आकार के सेट की आवश्यकता होती है। यदि समस्या में इष्टतम उप-संरचना का अभाव है, या यदि प्राकृतिक स्टेट स्पेस घातीय है और इसे संपीड़ित नहीं किया जा सकता है, तो डायनामिक प्रोग्रामिंग या तो गलत है या अब कुशल नहीं है।