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

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

किसी समस्या के दो मुख्य गुण बताते हैं कि डायनामिक प्रोग्रामिंग का उपयोग करके दी गई समस्या को हल किया जा सकता है। ये गुण हैंoverlapping sub-problems and optimal substructure।

ओवरलैपिंग उप-समस्याएं

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

उदाहरण के लिए, बाइनरी सर्च में ओवरलैपिंग उप-समस्या नहीं है। जबकि फाइबोनैचि संख्याओं के पुनरावर्ती कार्यक्रम में कई अतिव्यापी उप-समस्याएं हैं।

इष्टतम उप-संरचना

किसी दी गई समस्या में ऑप्टिमल सबस्ट्रक्चर प्रॉपर्टी है, यदि दी गई समस्या का इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधान का उपयोग करके प्राप्त किया जा सकता है।

उदाहरण के लिए, सबसे छोटी पथ समस्या में निम्नलिखित इष्टतम सबस्ट्रक्चर प्रॉपर्टी है -

यदि एक नोड x स्रोत नोड से सबसे कम पथ पर स्थित है u गंतव्य के लिए नोड v, फिर सबसे छोटा रास्ता u सेवा v से सबसे छोटे मार्ग का संयोजन है u सेवा x, और सबसे छोटा रास्ता x सेवा v।

फ्लोयड-वारशॉल और बेलमैन-फोर्ड जैसे मानक ऑल पेयर शॉर्टेस्ट पाथ एल्गोरिदम डायनेमिक प्रोग्रामिंग के विशिष्ट उदाहरण हैं।