गतिशील प्रोग्रामिंग

इस ट्यूटोरियल में, आप सीखेंगे कि गतिशील प्रोग्रामिंग क्या है। साथ ही, आप समस्याओं को हल करने के लिए गतिशील प्रोग्रामिंग और लालची एल्गोरिदम के बीच तुलना पाएंगे।

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

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

गतिशील प्रोग्रामिंग उदाहरण

रिट्रेसमेंट सीक्वेंस जेनरेट करने के मामले को लें।

यदि अनुक्रम F (1) F (2) F (3)… F (50) है, तो यह नियम F (n) = F (n-1) + F (n-2) का अनुसरण करता है।

 एफ (50) = एफ (49) + एफ (48) एफ (49) = एफ (48) + एफ (47) एफ (48) = एफ (47) + एफ (46) … 

ध्यान दें कि कैसे ओवरलैपिंग उपप्रोम्बल्स हैं, हमें एफ (48) और एफ (50) और एफ (49) दोनों की गणना करने की आवश्यकता है। यह ठीक उसी प्रकार का एल्गोरिथ्म है जहां डायनामिक प्रोग्रामिंग चमकता है।

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

डायनेमिक प्रोग्रामिंग सबप्रोब्लेम्स के परिणाम को संग्रहीत करके काम करता है ताकि जब उनके समाधान की आवश्यकता हो, तो वे हाथ में हों और हमें उन्हें पुनर्गणना करने की आवश्यकता नहीं है।

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

 var m = map (0 → 0, 1 → 1) फ़ंक्शन फ़ाइब (n) यदि कुंजी n मैप मिमी (n) = फ़ाइब (n - 1) + फ़ाइब (n - 2) रिटर्न m (n) में नहीं है 

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

 फ़ंक्शन फ़ाइब (n) यदि n = 0 वापसी 0 और संस्करण prevFib = 0, currFib = 1 दोहराना n - 1 बार var newFib = prevFib + currFib prevFib = currFib currFib = newFib वापसी 

पुनरावर्तन बनाम गतिशील प्रोग्रामिंग

डायनामिक प्रोग्रामिंग ज्यादातर पुनरावर्ती एल्गोरिदम पर लागू होती है। यह एक संयोग नहीं है, अधिकांश अनुकूलन समस्याओं में पुनरावृत्ति की आवश्यकता होती है और अनुकूलन के लिए गतिशील प्रोग्रामिंग का उपयोग किया जाता है।

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

यही कारण है कि मर्ज सॉर्ट जैसा एक पुनरावर्ती एल्गोरिथ्म डायनेमिक प्रोग्रामिंग का उपयोग नहीं कर सकता है, क्योंकि उपप्रोग्राम किसी भी तरह से अतिव्यापी नहीं हैं।

लालची एल्गोरिदम बनाम गतिशील प्रोग्रामिंग

लालची एल्गोरिदम इस अर्थ में गतिशील प्रोग्रामिंग के समान हैं कि वे दोनों अनुकूलन के लिए उपकरण हैं।

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

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