📲 🕔 👏🏼 गतिशील प्रोग्रामिंग या विभाजन और जीत ✊🏻 👆🏻 🎧

यह आलेख एल्गोरिदम समस्याओं को हल करने के लिए दो दृष्टिकोणों के बीच समानता और अंतर पर चर्चा करता है: गतिशील प्रोग्रामिंग (गतिशील प्रोग्रामिंग) और "फूट डालो और जीतो" (फूट डालो और जीतो) के सिद्धांत। हम दो एल्गोरिदम का उपयोग एक उदाहरण के रूप में करेंगे: द्विआधारी खोज (एक क्रमबद्ध सरणी में एक संख्या को जल्दी से कैसे ढूंढा जाए) और लेवेंसहाइट दूरी (संचालन की न्यूनतम संख्या के साथ एक पंक्ति को दूसरी में कैसे परिवर्तित करें)।

मैं तुरंत ध्यान देना चाहता हूं कि यह तुलना और स्पष्टीकरण अत्यंत सही होने का दावा नहीं करता है। और शायद कुछ विश्वविद्यालय के प्रोफेसर भी मुझे निष्कासित करना चाहेंगे :) यह लेख सिर्फ चीजों को छांटने और समझने के लिए मेरा व्यक्तिगत प्रयास है कि गतिशील प्रोग्रामिंग क्या है और "विभाजन और जीत" का सिद्धांत कैसे शामिल है।

तो, चलिए शुरू करते हैं ...

समस्या

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

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

डीपी और डीसी के बीच समानताएं

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

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

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

आइए विवरणों में थोड़ा और गहराई में जाएं ...

गतिशील प्रोग्रामिंग के लिए आवश्यक सीमाएँ और विशेषताएँ

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

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

जैसे ही हम विचार कर रहे समस्या में इन दो विशेषताओं को पा सकते हैं, हम कह सकते हैं कि इसे गतिशील प्रोग्रामिंग का उपयोग करके हल किया जा सकता है।

"फूट डालो और जीतो" के सिद्धांत के विस्तार के रूप में गतिशील प्रोग्रामिंग

डीपी दो तकनीकों ( संस्मरण और सारणीकरण ) की मदद से डीसी का विस्तार करता है, जिसका उद्देश्य उप-नमूनों के समाधान को उनके भविष्य के पुन: उपयोग के लिए सहेजना है। इस प्रकार, समाधान उपप्रकार द्वारा कैश किए जाते हैं, जो एल्गोरिथ्म प्रदर्शन में एक महत्वपूर्ण सुधार की ओर जाता है। उदाहरण के लिए, फिबोनाची फ़ंक्शन के "भोले" पुनरावर्ती कार्यान्वयन की समय जटिलता O(2 ⁿ ) । उसी समय, गतिशील प्रोग्रामिंग पर आधारित एक समाधान को सिर्फ (n) में निष्पादित किया जाता है।

संस्मरण (ऊपर से नीचे तक कैश को भरना) एक कैशिंग तकनीक है जो उपकेंद्रों के लिए नए गणना किए गए समाधान का उपयोग करता है। संस्मरण तकनीक का उपयोग करने वाला फाइबोनैचि फ़ंक्शन इस तरह दिखेगा:

 memFib(n) { if (mem[n] is undefined) if (n < 2) result = n else result = memFib(n-2) + memFib(n-1) mem[n] = result return mem[n] }

सारणीकरण (नीचे से ऊपर से कैश भरना) एक ऐसी ही तकनीक है, लेकिन जो मुख्य रूप से कैश को भरने पर केंद्रित है, और उपप्रकार के समाधान को खोजने पर नहीं। जिन मूल्यों को कैश करने की आवश्यकता है, उनकी गणना इस मामले में पुनरावृत्ति के बजाय, पुनरावृत्तिपूर्वक किया जाना सबसे आसान है। सारणीकरण तकनीक का उपयोग करने वाला फाइबोनैचि फ़ंक्शन इस तरह दिखेगा:

 tabFib(n) { mem[0] = 0 mem[1] = 1 for i = 2...n mem[i] = mem[i-2] + mem[i-1] return mem[n] }

आप यहाँ संस्मरण और सारणीकरण की तुलना के बारे में अधिक पढ़ सकते हैं।

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

तो आखिर डीपी और डीसी में क्या अंतर है

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

आइए कार्रवाई में इन दोनों दृष्टिकोणों को प्रदर्शित करने के लिए डीपी और डीसी का उपयोग करके कुछ समस्याओं को हल करने का प्रयास करें।

विभाजन और जीतना उदाहरण: बाइनरी सर्च

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

उदाहरण

नीचे दिया गया उदाहरण एक सरणी में संख्या 4 के लिए एक द्विआधारी खोज का एक उदाहरण है।

आइए उसी खोज तर्क को चित्रित करते हैं, लेकिन "निर्णय वृक्ष" के रूप में।

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

क्या हम गतिशील प्रोग्रामिंग का उपयोग करके इस समस्या को हल कर सकते हैं? नहीं। इस कार्य के लिए कि इस कार्य में उप-उपप्रकार सम्‍मिलित नहीं है । हर बार जब हम किसी सरणी को भागों में विभाजित करते हैं, तो दोनों भाग पूरी तरह से स्वतंत्र होते हैं और अतिव्यापी नहीं होते हैं। और गतिशील प्रोग्रामिंग की मान्यताओं और सीमाओं के अनुसार, जिसकी हमने ऊपर चर्चा की थी, उपप्रोग्राम किसी न किसी तरह से ओवरलैप होना चाहिए , उन्हें दोहराव होना चाहिए ।

आमतौर पर, जब भी कोई निर्णय वृक्ष बिलकुल एक वृक्ष की तरह दिखता है (और ग्राफ की तरह नहीं ), तो इसका सबसे अधिक संभावना है कि कोई अतिव्यापी उप-प्रकार नहीं है,

एल्गोरिदम कार्यान्वयन

यहां आप परीक्षण और स्पष्टीकरण के साथ बाइनरी खोज एल्गोरिदम का पूर्ण स्रोत कोड पा सकते हैं।

 function binarySearch(sortedArray, seekElement) { let startIndex = 0; let endIndex = sortedArray.length - 1; while (startIndex <= endIndex) { const middleIndex = startIndex + Math.floor((endIndex - startIndex) / 2); // If we've found the element just return its position. if (sortedArray[middleIndex] === seekElement)) { return middleIndex; } // Decide which half to choose: left or right one. if (sortedArray[middleIndex] < seekElement)) { // Go to the right half of the array. startIndex = middleIndex + 1; } else { // Go to the left half of the array. endIndex = middleIndex - 1; } } return -1; }

डायनामिक प्रोग्रामिंग उदाहरण: एडिटिंग डिस्टेंस

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

दो पंक्तियों के बीच संपादन दूरी (या लेवेंसहिन दूरी) एक वर्ण को सम्मिलित करने के लिए, एक वर्ण को हटाने और एक वर्ण को दूसरे के साथ बदलने के लिए आवश्यक है, एक पंक्ति को दूसरी में बदलने के लिए आवश्यक है।

उदाहरण

उदाहरण के लिए, "बिल्ली का बच्चा" और "बैठे" शब्दों के बीच संपादन दूरी 3 है, क्योंकि आपको एक पंक्ति को दूसरी में बदलने के लिए तीन संपादन कार्य (दो प्रतिस्थापन और एक सम्मिलित) करने की आवश्यकता है। और कम संचालन के साथ तेजी से रूपांतरण विकल्प खोजना असंभव है:

बिल्ली का बच्चा → sitten ("k" को "s" से बदलना)
sitten → sittin ("i" के साथ "i" की जगह)
sittin → बैठा (पूरी तरह से "g" डालें)।

एल्गोरिथ्म आवेदन

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

एक समस्या की गणितीय परिभाषा

गणितीय रूप से, दो रेखाओं के बीच की लेवेनस्टीन की दूरी a, b (लंबाई के साथ | | | | | | |b| क्रमशः) फ़ंक्शन function lev(|a|, |b|) द्वारा निर्धारित की जाती है function lev(|a|, |b|) , जहाँ:

कृपया ध्यान दें कि min फ़ंक्शन में पहली लाइन डिलीट ऑपरेशन से मेल खाती है, दूसरी लाइन इंसर्ट ऑपरेशन से मेल खाती है और तीसरी लाइन रिप्लेसमेंट ऑपरेशन से मेल खाती है (यदि अक्षर समान नहीं हैं)।

व्याख्या

आइए यह जानने की कोशिश करें कि यह सूत्र हमें क्या बताता है। ME और MY लाइनों के बीच न्यूनतम संपादन दूरी खोजने का एक सरल उदाहरण लें। सहज रूप से, आप पहले से ही जानते हैं कि न्यूनतम संपादन दूरी एक ( 1 ) प्रतिस्थापन ऑपरेशन ("ई" को "वाई" के साथ बदलें) है। लेकिन आइए हमारे समाधान को औपचारिक रूप दें और इसे एल्गोरिथम रूप में बदल दें, ताकि इस समस्या के अधिक जटिल संस्करणों को हल करने में सक्षम हो, जैसे कि शनिवार को रविवार में बदलना।

परिवर्तन के सूत्र को लागू करने के लिए ME → MY, हमें पहले ME → M, M → MY और M → M के बीच न्यूनतम संपादन दूरी ज्ञात करनी होगी। इसके बाद, हमें न्यूनतम तीन दूरियों को चुनना होगा और उसमें परिवर्तन E → Y के एक ऑपरेशन (+1) को जोड़ना होगा।

इसलिए, हम पहले से ही इस समाधान की पुनरावर्ती प्रकृति देख सकते हैं: न्यूनतम संपादन दूरी एमई → एमई की गणना तीन पिछले संभावित परिवर्तनों के आधार पर की जाती है। इस प्रकार, हम पहले से ही कह सकते हैं कि यह एक विभाजन है और एल्गोरिथ्म को जीतना है।

एल्गोरिथ्म को आगे समझाने के लिए, आइए अपनी दो पंक्तियों को एक मैट्रिक्स में रखें:

सेल (0,1) में लाल नंबर 1 होता है। इसका मतलब है कि एम को खाली स्ट्रिंग में बदलने के लिए हमें 1 ऑपरेशन करना होगा - एम। डिलीट करें। इसलिए, हमने इस नंबर को लाल रंग में चिह्नित किया है।

सेल (0,2) में एक लाल नंबर 2 होता है। इसका मतलब है कि स्ट्रिंग 2 को खाली स्ट्रिंग में बदलने के लिए हमें 2 ऑपरेशन करने की आवश्यकता है - ई हटाएं, एम हटाएं।

सेल (1,0) में एक ग्रीन नंबर होता है। 1. इसका मतलब है कि हमें खाली स्ट्रिंग को एम - पेस्ट एम में बदलने के लिए 1 ऑपरेशन की आवश्यकता है। हमने हरे रंग में सम्मिलित ऑपरेशन को चिह्नित किया।

सेल (2,0) में एक हरे रंग की संख्या 2 होती है। इसका मतलब है कि एक खाली स्ट्रिंग को स्ट्रिंग MY में सम्मिलित करने के लिए हमें 2 ऑपरेशन करने की आवश्यकता है - एम डालें, वाई डालें, एम डालें।

सेल (1,1) में नंबर 0. है। इसका मतलब है कि स्ट्रिंग एम को एम में परिवर्तित करने के लिए हमें कोई ऑपरेशन करने की आवश्यकता नहीं है।

सेल (1,2) में लाल नंबर 1 होता है। इसका मतलब है कि हमें स्ट्रिंग को एम में बदलने के लिए 1 ऑपरेशन करना होगा - ई हटाएं।

और इसी तरह…

यह हमारे (केवल 3x3) जैसे छोटे मैट्रिस के लिए मुश्किल नहीं है। लेकिन हम बड़े मेट्रिसेस के लिए सभी कोशिकाओं के मूल्यों की गणना कैसे कर सकते हैं (उदाहरण के लिए, शनिवार → रविवार में 9x7 मैट्रिक्स के लिए)?

अच्छी खबर यह है कि, सूत्र के अनुसार, हम सभी को निर्देशांक के साथ किसी भी सेल के मूल्य की गणना करने की आवश्यकता है (i,j) सिर्फ 3 पड़ोसी कोशिकाओं (i-1,j) , (i-1,j-1) , और (i,j-1) । हमें केवल तीन पड़ोसी कोशिकाओं का न्यूनतम मूल्य ज्ञात करना है और इस मूल्य में एक (+1) जोड़ना है अगर हमारे पास i-th पंक्ति और j-th कॉलम में अलग-अलग अक्षर हैं।

तो फिर, आप इस कार्य के पुनरावर्ती स्वभाव को स्पष्ट रूप से देख सकते हैं।

हमने यह भी देखा कि हम एक विभाजित और विजय कार्य के साथ काम कर रहे थे। लेकिन, क्या हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग लागू कर सकते हैं? क्या यह कार्य "उल्लिखित समस्याओं " और " इष्टतम उपग्रहों " की शर्तों को पूरा करता है? हां। चलो एक निर्णय पेड़ का निर्माण करें।

सबसे पहले, आप देख सकते हैं कि हमारा निर्णय पेड़ के बजाय निर्णय ग्राफ की तरह दिखता है। आप कई ओवरलैपिंग सबटुक भी देख सकते हैं। यह भी देखा जाता है कि उन तीनों पड़ोसी कोशिकाओं (उप-समस्याओं) से संचालन की संख्या को कम करना और इसे संचालन की संख्या से छोटा करना असंभव है।

आप यह भी देख सकते हैं कि प्रत्येक सेल में मूल्य की गणना पिछले मूल्यों के आधार पर की जाती है। इस प्रकार, इस मामले में, सारणीकरण तकनीक का उपयोग किया जाता है (नीचे-दिशा में कैश को भरना)। आप इसे नीचे दिए कोड उदाहरण में देखेंगे।

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

कोड उदाहरण

यहां आप परीक्षण और स्पष्टीकरण के साथ न्यूनतम संपादन दूरी खोजने के लिए एक संपूर्ण समाधान पा सकते हैं:

 function levenshteinDistance(a, b) { const distanceMatrix = Array(b.length + 1) .fill(null) .map( () => Array(a.length + 1).fill(null) ); for (let i = 0; i <= a.length; i += 1) { distanceMatrix[0][i] = i; } for (let j = 0; j <= b.length; j += 1) { distanceMatrix[j][0] = j; } for (let j = 1; j <= b.length; j += 1) { for (let i = 1; i <= a.length; i += 1) { const indicator = a[i - 1] === b[j - 1] ? 0 : 1; distanceMatrix[j][i] = Math.min( distanceMatrix[j][i - 1] + 1, // deletion distanceMatrix[j - 1][i] + 1, // insertion distanceMatrix[j - 1][i - 1] + indicator, // substitution ); } } return distanceMatrix[b.length][a.length]; }

निष्कर्ष

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

मुझे उम्मीद है कि इस लेख ने आप में से उन लोगों के लिए स्थिति को जटिल करने के बजाय स्पष्ट किया जो गतिशील प्रोग्रामिंग और "विभाजित और जीत" जैसी महत्वपूर्ण अवधारणाओं से निपटने की कोशिश कर रहे थे :)

आप जावास्क्रिप्ट एल्गोरिथ्म और डेटा स्ट्रक्चर्स रिपॉजिटरी में परीक्षण और स्पष्टीकरण के साथ गतिशील प्रोग्रामिंग का उपयोग करके अधिक एल्गोरिदमिक उदाहरण पा सकते हैं।

सफल कोडिंग!

गतिशील प्रोग्रामिंग या विभाजन और जीत