डायनामिक प्रोग्रामिंग को समझना ताकि आप इसका प्रभावी ढंग से उपयोग कर सकें

यह आलेख उत्पादन विकास से संबंधित नहीं है, लेकिन यह प्रोग्रामिंग से संबंधित है। मैं डायनेमिक प्रोग्रामिंग (डीपी) और पिछले गणना अनुभव का प्रभावी ढंग से उपयोग कैसे करें पर चर्चा करूंगा। मुझे आशा है कि आपको यह दिलचस्प लगेगा।

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

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

डीपी जिस प्रकार की समस्याओं का समाधान कर सकता है, उसे दो मानदंडों को पूरा करना होगा:

1. इष्टतम उपसंरचना । गतिशील प्रोग्रामिंग का अर्थ है कि छोटी उप-समस्याओं के समाधान का उपयोग प्रारंभिक समस्या को हल करने के लिए किया जा सकता है। इष्टतम उपसंरचना "फूट डालो और राज करो" प्रतिमान की मुख्य विशेषता है।

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

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

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

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

1. मेमोइज़ेशन (ऊपर से नीचे का दृष्टिकोण) रिकर्सन के माध्यम से कार्यान्वित किया जाता है। किसी कार्य को छोटी-छोटी उप-समस्याओं में विभाजित किया जाता है, उनके परिणामों को मेमोरी में फीड किया जाता है और बार-बार उपयोग के माध्यम से मूल समस्या को हल करने के लिए संयोजित किया जाता है।

• विपक्ष: यह दृष्टिकोण पुनरावर्ती विधि कॉल के माध्यम से स्टैक मेमोरी का उपयोग करता है
• पेशेवर: डीपी कार्यों के प्रति लचीलापन।

2. सारणीकरण (नीचे से ऊपर दृष्टिकोण) को पुनरावृत्तीय विधि का उपयोग करके कार्यान्वित किया जाता है। सबसे छोटी से आरंभिक तक की उप-समस्याओं की गणना क्रमिक रूप से, पुनरावृत्त रूप से की जाती है।

• विपक्ष: आवेदन की सीमित सीमा। इस दृष्टिकोण के लिए उप-समस्याओं के संपूर्ण अनुक्रम की प्रारंभिक समझ की आवश्यकता होती है। लेकिन कुछ समस्याओं में यह संभव नहीं है.
• पेशेवर: कुशल मेमोरी उपयोग, क्योंकि सब कुछ एक ही फ़ंक्शन के भीतर चलता है।

सिद्धांत थकाऊ और समझ से परे लग सकता है - आइए कुछ उदाहरण देखें।

समस्या: फाइबोनैचि अनुक्रम

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

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

इस कार्य के लिए, हम तीन मामलों को देखेंगे:

1. सीधा दृष्टिकोण: नुकसान क्या हैं?
2. मेमोइज़ेशन का उपयोग करके एक अनुकूलित समाधान
3. सारणीकरण का उपयोग करके एक अनुकूलित समाधान

सीधा/पाशविक दृष्टिकोण

पहली चीज़ जो आप सोच सकते हैं वह है रिकर्सन दर्ज करना, दो पूर्ववर्ती तत्वों का योग करना और उनका परिणाम देना।

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

नीचे दी गई स्क्रीन पर, आप अनुक्रम में पांचवें तत्व की गणना करने के लिए फ़ंक्शन कॉल का ढेर देख सकते हैं।

ध्यान दें कि फ़ंक्शन fib(1) पांच बार और fib(2) तीन बार कहा जाता है। एक ही हस्ताक्षर के साथ, एक ही पैरामीटर के साथ फ़ंक्शन बार-बार लॉन्च किए जाते हैं, और एक ही काम करते हैं। जब एन संख्या बढ़ाई जाती है, तो पेड़ बढ़ता है, रैखिक रूप से नहीं, बल्कि तेजी से, जिससे गणनाओं का भारी दोहराव होता है।

गणित विश्लेषण:

समय जटिलता: O(2n),

अंतरिक्ष जटिलता: O(n) -> पुनरावर्ती वृक्ष की अधिकतम गहराई के अनुपात में, क्योंकि यह उन तत्वों की अधिकतम संख्या है जो अंतर्निहित फ़ंक्शन कॉल के ढेर में मौजूद हो सकते हैं।

परिणाम: यह दृष्टिकोण अत्यंत अप्रभावी है। उदाहरण के लिए, 30वें तत्व की गणना के लिए 1,073,741,824 ऑपरेशन की आवश्यकता होती है।

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

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

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

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

आइए फ़ंक्शन कॉल स्टैक पर फिर से ध्यान केंद्रित करें:

• मेमो में परिणाम लिखने वाला पहला पूरा किया गया फ़ंक्शन हाइलाइट किया गया fib(2) है। यह हाइलाइट किए गए fib(3) पर नियंत्रण लौटाता है।
• हाइलाइट किया गया fib(3) fib(2) और fib(1) कॉल के परिणामों को सारांशित करने के बाद अपना मूल्य पाता है, मेमो में अपना समाधान दर्ज करता है और fib(4) पर नियंत्रण लौटाता है।
• हम पहले के अनुभव का पुन: उपयोग करने के चरण में पहुंच गए हैं - जब नियंत्रण fib(4) पर वापस आ जाता है, तो fib(2) कॉल इसमें अपनी बारी का इंतजार करती है। fib(2) बदले में, ( fib(1) + fib(0) ) को कॉल करने के बजाय, मेमो से पूरे तैयार समाधान का उपयोग करता है, और इसे सीधे वापस कर देता है।
• fib(4) की गणना की जाती है और नियंत्रण fib(5) पर लौटाया जाता है, जिसे केवल fib(3) लॉन्च करना होता है। अंतिम सादृश्य में, fib(3) बिना गणना के तुरंत मेमो से एक मान लौटाता है।

हम फ़ंक्शन कॉल और गणनाओं की संख्या में कमी देख सकते हैं। इसके अलावा, जब एन बढ़ाया जाता है, तो तेजी से कम कटौती होगी।

गणित विश्लेषण:

समय जटिलता: O(n)

अंतरिक्ष जटिलता: O(n)

परिणाम: स्पर्शोन्मुख जटिलता में स्पष्ट अंतर है। इस दृष्टिकोण ने इसे आदिम समाधान की तुलना में समय में रैखिक बना दिया है, और इसकी स्मृति में वृद्धि नहीं की है।

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

जैसा कि ऊपर उल्लेख किया गया है, इस दृष्टिकोण में छोटी से लेकर बड़ी उप-समस्या तक पुनरावृत्तीय गणना शामिल है। फाइबोनैचि के मामले में, सबसे छोटी "उप-समस्याएँ" क्रम में क्रमशः 0 और 1 के पहले और दूसरे तत्व हैं।

हम अच्छी तरह से जानते हैं कि तत्व एक-दूसरे से कैसे संबंधित हैं, जिसे सूत्र में व्यक्त किया गया है: fib(n) = fib(n-1) + fib(n-2) क्योंकि हम पिछले तत्वों को जानते हैं, हम आसानी से अगले तत्व, उसके बाद वाले तत्व, इत्यादि पर आसानी से काम कर सकते हैं।

जिन मूल्यों से हम अवगत हैं, उनका योग करके हम अगला तत्व पा सकते हैं। हम इस ऑपरेशन को चक्रीय रूप से तब तक लागू करते हैं जब तक हमें वांछित मूल्य नहीं मिल जाता।

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

गणित विश्लेषण:

समय जटिलता: O(n)

अंतरिक्ष जटिलता: O(1)

परिणाम: यह दृष्टिकोण गति के मामले में मेमोइज़ेशन जितना ही प्रभावी है, लेकिन यह निरंतर मात्रा में मेमोरी का उपयोग करता है।

समस्या: अद्वितीय बाइनरी पेड़

आइए एक अधिक जटिल समस्या को देखें: हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी पेड़ों की संख्या ज्ञात करने की आवश्यकता है जो एन नोड्स से बनाए जा सकते हैं।

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

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

इस कार्य का श्रेय कॉम्बिनेटरिक्स को दिया जा सकता है। आइए पता लगाएं कि कौन से संयोजन बन सकते हैं, और हम उनके गठन के लिए एक पैटर्न कैसे पा सकते हैं।

1. प्रत्येक पेड़ शीर्ष नोड (पेड़ के शीर्ष) से शुरू होता है। फिर वृक्ष गहराई में फैलता जाता है।
2. प्रत्येक नोड एक नए चाइल्ड ट्री (सबट्री) की शुरुआत है, जैसा कि स्क्रीन पर दिखाया गया है। बायां उपवृक्ष हरे रंग का है, और दायां उपवृक्ष लाल है। प्रत्येक का अपना शीर्ष है।

आइए एक कार्य का उदाहरण देखें, जहां वैचारिक स्तर पर एन = 6 है। हम अपने गणना फ़ंक्शन को numOfUniqueTrees(n: Int) कहेंगे।

हमारे उदाहरण में, 6 नोड दिए गए हैं, जिनमें से एक, पहले बताए गए सिद्धांत के अनुसार, पेड़ का शीर्ष बनाता है, और अन्य 5 - शेष।

अब से, हम शेष नोड्स के साथ बातचीत करते हैं। यह विभिन्न तरीकों से किया जा सकता है. उदाहरण के लिए, बाएं सबट्री को बनाने के लिए सभी पांच नोड्स का उपयोग करके या सभी पांचों को दाएं सबट्री में भेजकर। या नोड्स को दो में विभाजित करके - 2 बाईं ओर और 3 दाईं ओर (नीचे स्क्रीन देखें), हमारे पास ऐसे वेरिएंट की सीमित संख्या है।

परिणाम numOfUniqueTrees(6) प्राप्त करने के लिए, हमें अपने नोड्स को वितरित करने के लिए सभी प्रकारों पर विचार करने की आवश्यकता है। उन्हें तालिका में दिखाया गया है:

तालिका नोड्स के 6 अलग-अलग वितरण दिखाती है। यदि हम यह पता लगा लें कि प्रत्येक वितरण के लिए कितने अनूठे पेड़ तैयार किए जा सकते हैं और इनका योग करें, तो हम अपना अंतिम परिणाम प्राप्त कर लेंगे।

वितरण के लिए अद्वितीय पेड़ों की संख्या कैसे पता करें?

हमारे पास दो पैरामीटर हैं: बाएँ नोड्स और दाएँ नोड्स (तालिका में बाएँ और दाएँ कॉलम)।

परिणाम इसके बराबर होगा: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) ।

क्यों? बाईं ओर, हमारे पास X अद्वितीय पेड़ होंगे, और प्रत्येक के लिए, हम दाईं ओर Y अद्वितीय प्रकार के पेड़ लगाने में सक्षम होंगे। परिणाम प्राप्त करने के लिए हम इन्हें गुणा करते हैं।

तो आइए पहले वितरण के लिए विविधताएँ खोजें (5 बाएँ, 0 दाएँ)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , क्योंकि हमारे पास दाईं ओर कोई नोड नहीं है। परिणाम numOfUniqueTrees(5) है - बाईं ओर निरंतर दाईं ओर अद्वितीय उपवृक्षों की संख्या।

numOfUniqueTrees(5) की गणना।

अब हमारे पास सबसे छोटी उप-समस्या है। हम इसके साथ वैसे ही काम करेंगे जैसे हमने बड़े के साथ किया था। इस स्तर पर, डीपी कार्यों की विशेषता स्पष्ट है - इष्टतम उपसंरचना, पुनरावर्ती व्यवहार।

एक नोड (हरा नोड) शीर्ष पर भेजा जाता है। हम शेष (चार) नोड्स को पिछले अनुभव (4:0), (3:1), (2:2), (1:3), (0:4) के अनुरूप वितरित करते हैं।

हम पहले वितरण (4:0) की गणना करते हैं। यह पहले के अनुरूप numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) के बराबर है।

numOfUniqueTrees(4) की गणना। यदि हम शीर्ष पर एक नोड आवंटित करते हैं, तो हमारे पास 3 शेष रहते हैं।

वितरण (3:0), (2:1), (1:2), (0:3)।

2 नोड्स के लिए केवल दो अद्वितीय बाइनरी ट्री हैं, 1 के लिए - एक। पहले हम पहले ही उल्लेख कर चुके हैं कि तीन नोड्स के लिए अद्वितीय बाइनरी ट्री की 5 विविधताएँ हैं।

परिणामस्वरूप - वितरण (3:0), (0:3) 5, (2:1), (1:2) - 2 के बराबर हैं। यदि हम 5 + 2 + 2 + 5 का योग करते हैं, तो हमें 14 मिलता है . numOfUniqueTrees(4) = 14.

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

आइए गणना (5:0) पर वापस जाएँ, जो वितरण (4:0), (3:1), (2:2), (1:3), (0:4) के योग के बराबर है। हम जानते हैं कि (4:0) = 14। आइए मेमो की ओर मुड़ें, (3:1) = 5, (2:2) = 4 (बाईं ओर 2 बदलाव * दाईं ओर 2), (1:3) = 5, (0:4) = 14। यदि हम इन्हें जोड़ते हैं, तो हमें 42 मिलता है, numOfUniqueTrees(5) = 42।

आइए numOfUniqueTrees(6) की गणना पर वापस लौटें, जो वितरण के योग के बराबर है।

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 बाएँ * 2 दाएँ), (2:3) = 10, (1:4) = 14, (0: 5) = 42। यदि हम इनका योग करें, तो हमें 132, numOfUniqueTrees(5) = 132 प्राप्त होता है।

कार्य हल हो गया!

परिणाम: आइए समाधान में ओवरलैपिंग उप-समस्याओं पर ध्यान दें जहां N = 6. सीधे समाधान में, numOfUniqueTrees(3) 18 बार कॉल किया जाएगा (नीचे स्क्रीन)। एन बढ़ने के साथ, समान गणना की पुनरावृत्ति कहीं अधिक होगी।

मैं इस बात पर प्रकाश डालता हूँ कि (5 बाएँ, 0 दाएँ) और (0 बाएँ, 5 दाएँ) के लिए अद्वितीय पेड़ों की संख्या समान होगी। केवल एक मामले में वे बाईं ओर होंगे, और दूसरे में दाईं ओर। यह (4 बाएँ, 1 दाएँ) और (1 बाएँ, 4 दाएँ) के लिए भी काम करता है।

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

कार्यान्वयन

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

निष्कर्ष

कुछ मामलों में, डायनेमिक प्रोग्रामिंग के माध्यम से कार्यों को हल करने से बड़ी मात्रा में समय बचाया जा सकता है और एल्गोरिदम अधिकतम दक्षता के साथ काम कर सकता है।

इस लेख को अंत तक पढ़ने के लिए धन्यवाद. मुझे आपके प्रश्नों का उत्तर देने में खुशी होगी।