गतिशील प्रोग्रामिंग: विशेषताएं, उदाहरण, फायदे, नुकसान - प्रौद्योगिकी - 2025

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

इस अनुसूची का उपयोग तब किया जाता है जब आपके पास ऐसी समस्याएं होती हैं जिन्हें समान उपप्रकारों में विभाजित किया जा सकता है, ताकि उनके परिणामों का पुन: उपयोग किया जा सके। अधिकांश भाग के लिए, इस अनुसूची का उपयोग अनुकूलन के लिए किया जाता है।

गतिशील प्रोग्रामिंग। फाइबोनैचि अनुक्रम में उपप्रोम्ब्म सुपरपंप किए गए। स्रोत: विकिमीडिया कॉमन्स, en: उपयोगकर्ता: Dcoatzee, उपयोगकर्ता द्वारा पता लगाया: Stannered / सार्वजनिक डोमेन

उपलब्ध उपप्रोग्राम को हल करने से पहले, गतिशील एल्गोरिथ्म पहले हल किए गए उपप्रोम्बल के परिणामों की जांच करने का प्रयास करेगा। सबसे अच्छा समाधान प्राप्त करने के लिए उपप्रकारों का समाधान संयुक्त है।

बार-बार एक ही सबप्रॉब्लम की गणना करने के बजाय, आप अपने समाधान को कुछ मेमोरी में स्टोर कर सकते हैं, जब आप पहली बार इस सबप्रॉफर्म का सामना करते हैं। जब यह फिर से एक और उपप्रोजेम के समाधान के दौरान प्रकट होता है, तो पहले से ही मेमोरी में संग्रहीत समाधान लिया जाएगा।

यह मेमोरी समय को ठीक करने के लिए एक अद्भुत विचार है, जहां अतिरिक्त स्थान का उपयोग करने से समाधान खोजने के लिए आवश्यक समय में सुधार हो सकता है।

गतिशील प्रोग्रामिंग की विशेषताएं

गतिशील प्रोग्रामिंग को लागू करने से पहले आपको निम्नलिखित आवश्यक विशेषताएं बताई गई हैं, जो आपके लिए एक समस्या होनी चाहिए:

इष्टतम उपकला

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

उदाहरण के लिए, एक ग्राफ में एक इष्टतम सबस्ट्रक्चर को सबसे छोटे पथ आर में प्रस्तुत किया जाएगा जो एक शीर्ष से एक शीर्ष पर जाता है:

यही है, इस सबसे छोटे रास्ते में आर किसी भी मध्यवर्ती शिखर मैं लिया जा सकता है। यदि r वास्तव में सबसे छोटा मार्ग है, तो इसे उप-मार्गों r1 (s से i तक) और r2 (i से t) में विभाजित किया जा सकता है, ताकि ये संगत चक्करों के बीच सबसे छोटे मार्गों को मोड़ सकें।

इसलिए, सबसे छोटे रास्तों को खोजने के लिए, समाधान को आसानी से पुनरावर्ती रूप से तैयार किया जा सकता है, जो कि फ्लॉयड-वारशॉल एल्गोरिथ्म करता है।

ओवरलैपिंग उपप्रोब्लेम्स

उपप्रक्रम स्थान छोटा होना चाहिए। यही है, किसी भी पुनरावर्ती एल्गोरिथ्म जो एक समस्या को हल करता है, उसे नए उपप्रोब्स उत्पन्न करने के बजाय बार-बार एक ही उपप्रोमीटर को हल करना होगा।

उदाहरण के लिए, फाइबोनैचि श्रृंखला उत्पन्न करने के लिए, इस पुनरावर्ती सूत्र पर विचार किया जा सकता है: Fn = F (n - 1) + F (n - 2), एक आधार मामले के रूप में लेते हुए कि F1 = F2 = 1. तब हमारे पास होगा: F33 = F32 + F31, और F32 = F31 + F30।

जैसा कि आप देख सकते हैं, F31 को F33 और F32 दोनों के पुनरावर्ती उपप्रकारों में हल किया जा रहा है। यद्यपि उपप्रकारों की कुल संख्या वास्तव में छोटी है, यदि आप इस तरह के एक पुनरावर्ती समाधान को अपनाते हैं तो आप एक ही समस्या को बार-बार हल करेंगे।

इसे डायनेमिक प्रोग्रामिंग द्वारा ध्यान में रखा जाता है, इसलिए यह प्रत्येक उपप्रोग्राम को केवल एक बार हल करता है। इसे दो तरीकों से पूरा किया जा सकता है:

शीर्ष पाद उपागम

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

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

नीचे से ऊपर का दृष्टिकोण

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

यह आम तौर पर तालिका के रूप में भी किया जाता है, छोटे उपप्रकारों के समाधानों का उपयोग करके बड़े और बड़े उपप्रकारों के लिए पुनरावृत्त रूप से जनरेट करने वाले समाधान। उदाहरण के लिए, यदि F31 और F30 के मान पहले से ज्ञात हैं, तो F32 के मूल्य की सीधे गणना की जा सकती है।

अन्य तकनीकों के साथ तुलना

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

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

उदाहरण

1 तक पहुंचने के लिए न्यूनतम कदम

किसी भी सकारात्मक पूर्णांक के लिए "ई" निम्न तीन चरणों में से कोई भी किया जा सकता है।

- संख्या से 1 घटाएं। (ई = ई -1)।

- यदि यह 2 से विभाज्य है, तो इसे 2 से विभाजित किया जाता है (यदि ई% 2 == 0 है, तो ई = ई / 2)।

- यदि यह 3 से विभाज्य है, तो इसे 3 से विभाजित किया जाता है (यदि ई% 3 == 0 है, तो ई = ई / 3)।

उपरोक्त चरणों के आधार पर, इन चरणों की न्यूनतम संख्या ई को 1 में लाना चाहिए। उदाहरण के लिए:

- यदि ई = 1, परिणाम: 0।

- यदि ई = 4, परिणाम: 2 (4/2 = 2/2 = 1)।

- जब e = 7, परिणाम: 3 (7-1 = 6/3 = 2/2 = 1)।

फोकस

कोई हमेशा उस कदम को चुनने के बारे में सोच सकता है जो n को यथासंभव कम बनाता है और जब तक यह 1 तक नहीं पहुंचता तब तक जारी रहता है। हालांकि, यह देखा जा सकता है कि यह रणनीति यहां काम नहीं करती है।

उदाहरण के लिए, यदि e = 10, चरण होंगे: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 चरण)। हालाँकि, इष्टतम रूप है: 10-1 = 9/3 = 3/3 = 1 (3 चरण)। इसलिए, इन संभावितों की न्यूनतम संख्या का चयन करते हुए, n के प्रत्येक मूल्य के लिए किए जाने वाले सभी संभावित कदमों की कोशिश की जानी चाहिए।

यह सब पुनरावृत्ति से शुरू होता है: एफ (ई) = 1 + मिनट {एफ (ई -1), एफ (ई / 2), एफ (ई / 3)} अगर ई> 1, आधार मामले के रूप में ले रहा है: एफ (1) = 0. पुनरावृत्ति समीकरण होने पर, आप पुनरावर्ती कोड करने के लिए प्रारंभ कर सकते हैं।

हालांकि, यह देखा जा सकता है कि इसमें उप-प्रक्रम अतिव्यापी हैं। इसके अलावा, किसी दिए गए इनपुट का इष्टतम समाधान उसके उपप्रकारों के इष्टतम समाधान पर निर्भर करता है।

संस्मरण के रूप में, जहां हल किए गए उपप्रकारों के समाधान बाद में उपयोग के लिए संग्रहीत किए जाते हैं। या डायनेमिक प्रोग्रामिंग के रूप में, आप नीचे दिए गए ई पर अपने तरीके से काम करना शुरू करते हैं। फिर दोनों कोड:

याद

डायनेमिक बॉटम-अप प्रोग्रामिंग

फायदा

डायनेमिक प्रोग्रामिंग का उपयोग करने का एक मुख्य लाभ यह है कि यह प्रसंस्करण को गति देता है, क्योंकि पहले से गणना की गई संदर्भों का उपयोग किया जाता है। जैसा कि यह एक पुनरावर्ती प्रोग्रामिंग तकनीक है, यह प्रोग्राम में कोड की लाइनों को कम करता है।

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

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

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

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

नुकसान

- प्रत्येक उपप्रोजेम के परिकलित परिणाम को संग्रहीत करने के लिए बहुत सारी मेमोरी की आवश्यकता होती है, बिना इस बात की गारंटी के कि संग्रहित मूल्य का उपयोग किया जाएगा या नहीं।

- कई बार, निष्पादन के दौरान निम्नलिखित उपप्रकारों में उपयोग किए बिना आउटपुट मान संग्रहीत किया जाता है। इससे अनावश्यक मेमोरी का उपयोग होता है।

- डायनेमिक प्रोग्रामिंग में, फ़ंक्शन को पुनरावर्ती कहा जाता है। इससे स्टैक मेमोरी लगातार बढ़ती रहती है।

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

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

यदि आप चाहते हैं कि प्रोग्राम तेजी से चले और स्मृति प्रतिबंध न हों, तो गतिशील प्रोग्रामिंग का उपयोग करना बेहतर होगा।

अनुप्रयोग

डायनेमिक प्रोग्रामिंग समस्याओं को हल करने का एक प्रभावी तरीका है जो अन्यथा समय की उचित मात्रा में हल करना बहुत मुश्किल लग सकता है।

डायनामिक प्रोग्रामिंग प्रतिमान के आधार पर एल्गोरिदम का उपयोग विज्ञान के कई क्षेत्रों में किया जाता है, जिसमें कृत्रिम बुद्धिमत्ता में कई उदाहरण शामिल हैं, समस्या समाधान से लेकर भाषण मान्यता तक।

डायनेमिक प्रोग्रामिंग के आधार पर एल्गोरिदम

डायनेमिक प्रोग्रामिंग काफी प्रभावी है और समस्याओं की एक विस्तृत श्रृंखला के लिए बहुत अच्छी तरह से काम करती है। कई एल्गोरिदम को लालची एल्गोरिथ्म अनुप्रयोगों के रूप में देखा जा सकता है, जैसे:

- फाइबोनैचि संख्या श्रृंखला।

- हनोई के टावर।

- फ्लोयड-वारशॉल के माध्यम से छोटे मार्गों के सभी जोड़े।

- बैकपैक समस्या।

- परियोजना समयबद्धन।

- दिज्कस्त्र के माध्यम से सबसे छोटा रास्ता।

- उड़ान नियंत्रण और रोबोटिक्स नियंत्रण।

- गणितीय अनुकूलन समस्याओं।

- टाइमशेयर: सीपीयू के उपयोग को अधिकतम करने के लिए कार्य को शेड्यूल करें।

फाइबोनैचि संख्या श्रृंखला

फाइबोनैचि संख्याएँ निम्नलिखित अनुक्रम में पाई जाने वाली संख्याएँ हैं: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, आदि।

गणितीय शब्दावली में, फाइबोनैचि संख्याओं के अनुक्रम को पुनरावृत्ति सूत्र द्वारा परिभाषित किया गया है: एफ (एन) = एफ (एन -1) + एफ (एन -2), जहां एफ (0) = 0 और एफ (1) = 1।

शीर्ष पाद उपागम

इस उदाहरण में, सभी प्रारंभिक मानों वाला एक खोज सरणी -1 के साथ आरंभिक है। जब भी किसी उपप्रोमीटर के समाधान की आवश्यकता होती है, तो यह खोज मैट्रिक्स पहले खोजा जाएगा।

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

नीचे से ऊपर का दृष्टिकोण

इस मामले में, एक ही फाइबोनैचि श्रृंखला के लिए, f (0) की गणना पहले की जाती है, फिर f (1), f (2), f (3), और इसी तरह। इस प्रकार, उपप्रकारों का समाधान नीचे से ऊपर तक किया जा रहा है।

संदर्भ

1. विनीत चौधरी (2020)। डायनामिक प्रोग्रामिंग का परिचय। डेवलपर अंदरूनी सूत्र। से लिया गया: developerinsider.co।
2. एलेक्स एलेन (2020)। C ++ में डायनामिक प्रोग्रामिंग। सी प्रोग्रामिंग। से लिया गया: cprogramming.com
3. अकादमी (2020) के बाद। डायनामिक प्रोग्रामिंग का आइडिया। से लिया गया: afteracademy.com
4. अनिरुद्ध चौधरी (2019)। गतिशील प्रोग्रामिंग और पुनरावृत्ति - अंतर, उदाहरण के साथ लाभ। सीएसई स्टैक। से लिया गया: csestack.org।
5. कोड बावर्ची (2020)। डायनामिक प्रोग्रामिंग के लिए ट्यूटोरियल। से लिया गया: codechef.com
6. प्रोग्रामिज़ (2020)। गतिशील प्रोग्रामिंग। से लिया गया: programiz.com।