गतिशील प्रोग्रामिंग क्या है?

जब कंप्यूटर प्रोग्रामिंग की बात आती है, तो डायनेमिक प्रोग्रामिंग उतनी ही बहुमुखी है जितनी कि यह गणितीय है। रिचर्ड बेलमैन ने 50 के दशक में तकनीक का निर्माण किया था, और तब से इसे वैमानिकी इंजीनियरिंग से लेकर अर्थशास्त्र तक हर चीज में इस्तेमाल किया गया है।

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

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

आप ऑनलाइन कोर्सेज की मदद से सॉफ्टवेयर इंजीनियरिंग सीख सकते हैं।

गणितीय अनुकूलन

वृद्धिशील विकल्पों की एक श्रृंखला में एक जटिल विकल्प को विघटित करके, जैसा कि गतिशील प्रोग्रामिंग में किया जाता है, एक गणितीय अनुकूलन समस्या को संचालन के लिए और अधिक प्रबंधनीय बनाया जा सकता है। इसे प्राप्त करने के लिए, हम मूल्य कार्यों V1, V2,…, Vn के एक सेट को परिभाषित करते हैं, जिनमें से प्रत्येक y को 0 से n के समय I में एक निश्चित समय पर सिस्टम की स्थिति का वर्णन करने के लिए एक तर्क के रूप में लेता है। Vn (y) उस समय का मान है जो राज्य y से प्राप्त किया गया था। बेलमैन समीकरण के रूप में ज्ञात पुनरावर्ती कनेक्शन का उपयोग करके, हम पिछली अवधि I = n1, n2,…, 2, 1 पर Vi के मान निर्धारित कर सकते हैं। एक विकल्प से लाभ के एक साधारण फ़ंक्शन (अक्सर योग) को अधिकतम करके समय I 1 और सिस्टम की नई स्थिति में फ़ंक्शन Vi, हम Vi से किसी भी राज्य y पर Vi1 प्राप्त कर सकते हैं, जहां I = 2,…, n। यह प्रक्रिया आवश्यक राज्यों के लिए Vi1 लौटाती है क्योंकि Vi की गणना उनके लिए पहले ही की जा चुकी है। और अंत में, इष्टतम समाधान मान, V1, सिस्टम की प्रारंभिक स्थिति में पाया जाता है। पहले की संगणनाओं से चरणों को पुनः प्राप्त करके, पसंद चर के इष्टतम मूल्यों को एक बार में एक बार पुनः प्राप्त किया जा सकता है।

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

एक सॉफ्टवेयर इंजीनियरिंग सर्टिफिकेट प्रोग्राम आपके कौशल को बढ़ा सकता है।

एक इष्टतम उप-संरचना के साथ एक अनुकूलन समस्या को इसके उप-समस्याओं के समाधान के संयोजन से हल किया जा सकता है। आदर्श संरचनाओं को आमतौर पर रिकर्सन के माध्यम से परिभाषित किया जाता है। ग्राफ G=(V,E) में प्रत्येक मध्यवर्ती शीर्ष ने एक शीर्ष u से एक शीर्ष v तक सबसे छोटा पथ p जीता है, इष्टतम उपसंरचना का एक उदाहरण है। यदि पथ p सबसे छोटा है, तो इसे दो पथों में विभाजित किया जा सकता है, p1 से u से w तक और p2 से w से v तक, जो उनके संबंधित युग्मों के बीच सबसे छोटा भी है। इस प्रकार, बेलमैन-फोर्ड और फ्लोयड-वॉर्शल एल्गोरिदम सबसे छोटे रास्तों को खोजने के लिए पुनरावर्तन का उपयोग करते हैं।

डायनेमिक प्रोग्रामिंग पद्धति का उपयोग करने के पीछे तर्क क्या है?

गतिशील प्रोग्रामिंग की प्रक्रिया इस प्रकार है:

1. ऐसा करने से, यह मूल मुद्दे के सभी पहलुओं की जटिलता को कम करता है।
2. इन छोटी-छोटी समस्याओं को हल करने के लिए, यह सर्वोत्तम संभव उत्तर निर्धारित करता है।
3. यह छोटी चुनौतियों (मेमोइज़ेशन) के समाधान का ट्रैक रखता है। याद रखना छोटी समस्याओं के समाधान को याद रखने की क्रिया है।
4. यह उन्हें इस तरह रीसायकल करता है कि समस्या का एक ही हिस्सा कई बार हल किया जा सकता है।
5. इन सब के बाद, आपको कठिन मुद्दे का उत्तर जानने की आवश्यकता है।

1. अतिव्यापी उपसमस्याओं के साथ इष्टतम उपसंरचनाएं और मुद्दे। इस संदर्भ में, "इष्टतम सबस्ट्रक्चर" शब्द एक ऐसी विधि को संदर्भित करता है जिसके द्वारा अनुकूलन के मुद्दों को उनके घटक उप-समस्याओं के सर्वोत्तम समाधानों को एकीकृत करके हल किया जा सकता है।
2. चूंकि मध्यवर्ती परिणामों को संग्रहीत किया जाना चाहिए, गतिशील प्रोग्रामिंग की अंतरिक्ष जटिलता बढ़ती है, भले ही समय जटिलता गिरती है।