याद रखना गतिशील प्रोग्रामिंग पर आधारित एक तकनीक है जिसका उपयोग पुनरावर्ती एल्गोरिदम के प्रदर्शन को बेहतर बनाने के लिए किया जाता है ताकि यह सुनिश्चित किया जा सके कि प्रदान किए गए इनपुट के परिणामों का रिकॉर्ड रखकर विधि एक से अधिक बार इनपुट के एक ही सेट के लिए नहीं चलती है। एक सरणी। रिकर्सिव विधि के टॉप डाउन दृष्टिकोण को लागू करके याद किया जा सकता है।
आइए इस परिदृश्य को बुनियादी फिबोनाची उदाहरण की मदद से समझते हैं
1-डी याद रखना
हम केवल एक गैर स्थिर पैरामीटर के साथ एक पुनरावर्ती एल्गोरिदम पर विचार करेंगे (केवल एक पैरामीटर अपना मान बदलता है) इसलिए इस विधि को 1-डी मेमोराइजेशन कहा जाता है। निम्नलिखित कोड फाइबोनैचि श्रृंखला में N'th (N तक के सभी पदों) को खोजने के लिए है।
उदाहरण
पब्लिक इंट फाइबोनैचि (इंट एन) { अगर (एन ==0) रिटर्न 0; अगर (एन ==1) वापसी 1; System.out.println ("इसके लिए फाइबोनैचि संख्या की गणना:" + n); वापसी (फाइबोनैचि (एन -1) + फाइबोनैचि (एन - 2));} आउटपुट
यदि हम उपरोक्त कोड को n=5 के साथ चलाते हैं, तो यह निम्न आउटपुट उत्पन्न करेगा।
इसके लिए फाइबोनैचि संख्या की गणना करना:5 इसके लिए फाइबोनैचि संख्या की गणना करना:4 इसके लिए फाइबोनैचि संख्या की गणना करना:3 इसके लिए फाइबोनैचि संख्या की गणना करना:2 इसके लिए फाइबोनैचि संख्या की गणना करना:2 इसके लिए फाइबोनैचि संख्या की गणना करना:3 के लिए फाइबोनैचि संख्या की गणना करना:2
n=5:5 के लिए फाइबोनैचि मान
यह देखा गया है कि 2 और 3 के लिए फाइबोनैचि संख्या की गणना एक से अधिक बार की जाती है। आइए हम उपरोक्त स्थिति की फाइबोनैचि श्रृंखला के लिए एक पुनरावर्ती पेड़ को खींचकर बेहतर ढंग से समझते हैं अर्थात n=5।
यहां नोड के दो बच्चे इसके द्वारा किए जाने वाले पुनरावर्ती कॉल का प्रतिनिधित्व करेंगे। जैसा कि देखा जा सकता है F(3) और F(2) की गणना एक से अधिक बार की जाती है और प्रत्येक चरण के बाद परिणामों को संचित करने से बचा जा सकता है।
हम परिणाम को कैशिंग करने के लिए एक आवृत्ति चर memoize सेट का उपयोग करेंगे। यह पहले जांचा जाता है कि क्या n पहले से ही मेमोइज़ सेट में मौजूद है, यदि हाँ मान वापस कर दिया गया है, और यदि मान की गणना नहीं की जाती है और सेट में जोड़ा जाता है।
उदाहरण
आयात करें // ओ (1) पब्लिक इंट फ़ाइबमेमोइज़ (इंट इनपुट) { अगर (इनपुट ==0) रिटर्न 0; अगर (इनपुट ==1) वापसी 1; if (this.memoizeSet.containsKey(input)) { System.out.println ("+ इनपुट के लिए परिकलित परिणाम से मान प्राप्त करना); इसे वापस करें। memoizeSet.get (इनपुट); } इंट परिणाम =फ़ाइबमेमोइज़ (इनपुट -1) + फ़ाइबमेमोइज़ (इनपुट - 2); System.out.println ("+ इनपुट के लिए कैश में परिणाम डालना); this.memoizeSet.put (इनपुट, परिणाम); वापसी परिणाम; } पब्लिक इंट फाइबोनैचि (इंट एन) { अगर (एन ==0) रिटर्न 0; अगर (एन ==1) वापसी 1; System.out.println ("इसके लिए फाइबोनैचि संख्या की गणना:" + n); वापसी (फाइबोनैचि (एन -1) + फाइबोनैचि (एन - 2)); } सार्वजनिक स्थैतिक शून्य मुख्य (स्ट्रिंग [] args) { TutorialPoint TutorialPoint =new TutorialPoint (); System.out.println ("एन =5 के लिए फाइबोनैचि मान:" + tutorialPoint.fibMemoize(5)); }}आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
memoize में परिणाम जोड़ना 2 के लिए सेट करें memoize में परिणाम जोड़ें 3 के लिए सेट करें 2 के लिए परिकलित परिणाम से मान प्राप्त करना memoize में परिणाम जोड़ना 3 के लिए परिकलित परिणाम से मान प्राप्त करना memoize में परिणाम जोड़ना 5 के लिए सेट करें
n=5:5 के लिए फाइबोनैचि मान
जैसा कि देखा जा सकता है कि 2 और 3 के लिए फाइबोनैचि संख्या की गणना फिर से नहीं की जाती है। यहां हम एक हैश मैप पेश करते हैं जो उन मानों को संग्रहीत करने के लिए याद रखता है जो सेट में प्रत्येक फाइबोनैचि गणना की जांच से पहले ही गणना की जाती हैं, यदि इनपुट के लिए मूल्य की गणना की गई है और यदि विशेष इनपुट के मूल्य को सेट में जोड़ा नहीं गया है।
2-डी याद रखना
उपरोक्त कार्यक्रम में हमारे पास केवल एक गैर स्थिर पैरामीटर था। नीचे दिए गए कार्यक्रम में हम दो मापदंडों वाले एक पुनरावर्ती कार्यक्रम का एक उदाहरण लेंगे जो प्रत्येक पुनरावर्ती कॉल के बाद अपना मूल्य बदलता है, और हम इसे अनुकूलित करने के लिए दो गैर-स्थिर मापदंडों पर संस्मरण को लागू करेंगे। इसे 2-डी मेमोराइजेशन कहा जाता है।
उदाहरण के लिए:-हम मानक सबसे लंबे समय तक सामान्य बाद को लागू करने जा रहे हैं(LCS) .यदि अनुक्रमों का एक सेट दिया जाता है, तो सबसे लंबी सामान्य अनुवर्ती समस्या सभी अनुक्रमों का एक सामान्य बाद का पता लगाना है जो कि अधिकतम लंबाई का है। संभावित संयोजन 2 बजे होंगे।
उदाहरण
क्लास टीपी {स्थिर इंट कंप्यूटमैक्स (इंट ए, इंट बी) {रिटर्न (ए> बी)? ए:बी; } स्थिर int longComSs (स्ट्रिंग एक्स, स्ट्रिंग वाई, इंट एम, इंट एन) { अगर (एम ==0 || एन ==0) वापसी 0; अगर (X.charAt(m-1) ==Y.charAt(n-1)) रिटर्न 1 + सबसे लंबे समय तकComSs(X, Y, m-1, n-1); अन्य रिटर्न कंप्यूटमैक्स (सबसे लंबा कॉमएस (एक्स, वाई, एम, एन -1), सबसे लंबा कॉमएस (एक्स, वाई, एम -1, एन)); } सार्वजनिक स्थैतिक शून्य मुख्य (स्ट्रिंग [] तर्क) {स्ट्रिंग शब्द_1 ="एजीजीटीएबी"; स्ट्रिंग शब्द_2 ="GXTXAYB"; System.out.print ("एलसीएस की लंबाई" + सबसे लंबी कॉमएस (वर्ड_1, वर्ड_2, वर्ड_1.लेंथ (), वर्ड_2.लेंथ ())); }} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है
उपरोक्त आधे रास्ते के रिकर्सन ट्री में, lcs("AXY", "AYZ") को एक से अधिक बार हल किया जाता है।
इस समस्या की ओवरलैपिंग सबस्ट्रक्चर संपत्ति के परिणामस्वरूप, मेमोराइजेशन या टेबुलेशन का उपयोग करके समान उप-समस्याओं की पूर्व गणना से बचा जा सकता है।
रिकर्सिव कोड का मेमोराइज़ेशन दृष्टिकोण निम्नानुसार कार्यान्वित किया जाता है।
उदाहरण
import java.io.*;import java.lang.*;class testClass { final static int maxSize =1000; सार्वजनिक स्थैतिक int गिरफ्तारी [] [] =नया int [अधिकतम आकार] [अधिकतम आकार]; सार्वजनिक स्थैतिक int गणना (स्ट्रिंग str_1, स्ट्रिंग str_2, int m, int n) {if (m ==0 || n ==0) वापसी 0; अगर (गिरफ्तारी [एम -1] [एन -1]! =-1) वापसी गिरफ्तारी [एम -1] [एन -1]; अगर (str_1.charAt(m-1) ==str_2.charAt(n-1)) { arr[m - 1][n-1] =1 + कैलकुलेटlcs(str_1, str_2, m-1, n-1); वापसी गिरफ्तारी [एम -1] [एन -1]; } और { इंट ए =कैलकुलेटएलसी (str_1, str_2, m, n - 1); इंट बी =कैलकुलेटएलसी (str_1, str_2, m - 1, n); इंट मैक्स =(ए> बी)? ए:बी; एआर [एम -1] [एन -1] =अधिकतम; वापसी गिरफ्तारी [एम -1] [एन -1]; } } सार्वजनिक स्थैतिक शून्य मुख्य (स्ट्रिंग [] args) { के लिए (int i =0; i <1000; i ++) { के लिए (int j =0; j <1000; j ++) {arr [i] [j] =- 1; } } स्ट्रिंग str_1 ="AGGTAB"; स्ट्रिंग str_2 ="GXTXAYB"; System.out.println ("एलसीएस की लंबाई है" + गणना एलसीएस (str_1, str_2, str_1.length (), str_2.length ())); }} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है
दृष्टिकोण
यह देखा गया है कि मेथड (कैल्कुटेल्स) में 4 तर्क होते हैं जिनमें 2 स्थिरांक (जो याद रखने को प्रभावित नहीं करते) और 2 गैर-स्थिर तर्क (m और n) होते हैं। जो प्रत्येक पुनरावर्ती विधि कॉलिंग में अपना मान बदलता है। इसलिए संस्मरण प्राप्त करने के लिए हम एलसीएस (एम, एन) के गणना मूल्यों को एआर [एम -1] [एन -1] पर संग्रहीत करने के लिए 2-डी सरणी पेश करते हैं। हम कोई और पुनरावर्ती कॉल नहीं करते हैं और वापसी एआर [एम -1] [एन -1] जब भी एक ही तर्क एम और एन के साथ फ़ंक्शन को फिर से कहा जाता है, क्योंकि एलसीएस (एम, एन) की पिछली गणना पहले ही की जा चुकी है arr[m-1][n-1] में संग्रहीत, इस प्रकार पुनरावर्ती कॉल की संख्या को कम करता है।
3-डी याद रखना
यह 3 गैर-स्थिर तर्क वाले पुनरावर्ती कार्यक्रम के लिए संस्मरण प्राप्त करने का एक तरीका है। यहां हम तीन स्ट्रिंग्स के लिए LCS की लंबाई की गणना करने का उदाहरण ले रहे हैं।
यहां दृष्टिकोण दिए गए स्ट्रिंग्स के लिए सभी संभावित अनुवर्ती (कुल संभावित अनुवर्ती 3ⁿ) उत्पन्न करना है और उनमें से सबसे लंबे सामान्य अनुक्रम के लिए मिलान करना है।
हम गणना किए गए मानों को संग्रहीत करने के लिए एक 3-डी तालिका पेश करेंगे। परवर्ती को ध्यान में रखते हुए।
-
ए1[1...i] मैं <एन
-
ए2[1...जे] जे <एम
-
A3[1...k] k
यदि हमें एक सामान्य वर्ण (X[i]==Y[j]==Z[k]) मिलता है, तो हमें शेष वर्णों की पुनरावृत्ति करनी होगी। अन्यथा हम निम्नलिखित मामलों में से अधिकतम की गणना करेंगे
-
दूसरों के लिए X[i] की पुनरावृत्ति छोड़ें
-
दूसरों के लिए Y[j] की पुनरावृत्ति छोड़ें
-
दूसरों के लिए Z[k] पुनरावृत्ति छोड़ें
इसलिए, यदि हम उपरोक्त विचार को हमारे रिकर्सन फ़ंक्शन में तैयार करते हैं तो
f(N,M,K)={1+f(N-1,M-1,K-1)if (X[N]==Y[M]==Z[K]maximum(f(N-) 1, एम, के), एफ (एन, एम -1, के), एफ (एन, एम, के -1))}
-
f(N-1,M,K) =छोड़ दें X[i] दूसरों के लिए पुनरावृत्ति करें
-
f(N,M-1,K) =Y[j] को दूसरों के लिए फिर से आने दें
-
f(N,M,K-1) =दूसरों के लिए Z[k] की पुनरावृत्ति छोड़ें
उदाहरण
आयात करें स्थिर इंट कैलकुलेट (स्ट्रिंग str_1, स्ट्रिंग str_2, स्ट्रिंग str_3, int m, int n, int o) { के लिए (int i =0; i <=m; i++) { के लिए (int j =0; j <=n; जे ++) {गिरफ्तारी [i] [जे] [0] =0; } } के लिए (int i =0; i <=n; i++) { for (int j =0; j <=o; j++) {arr[0][i][j] =0; } } के लिए (int i =0; i <=m; i++) { for (int j =0; j <=o; j++) {arr[i][0][j] =0; } } के लिए (int i =1; i <=m; i++) { for (int j =1; j <=n; j++) { for (int k =1; k <=o; k++) { if (str_1 .charAt(i - 1) ==str_2.charAt(j-1) &&str_2.charAt(j1) ==str_3.charAt(k-1)) { arr[i][j][k] =1 + arr [i - 1] [j - 1] [k - 1]; } और { एआर [i] [जे] [के] =कैलकुलेटमैक्स (गिरफ्तारी [आई -1] [जे] [के], एआर [आई] [जे -1] [के], एआर [आई] [जे] [जे] के - 1]); } } } } वापसी गिरफ्तारी [एम] [एन] [ओ]; } स्टैटिक इंट कैलकुलेट मैक्स (इंट ए, इंट बी, इंट सी) { अगर (ए> बी &&ए> सी) रिटर्न ए; अगर (बी> सी) वापसी बी; वापसी सी; } सार्वजनिक स्थैतिक शून्य मुख्य (स्ट्रिंग [] args) {स्ट्रिंग str_1 ="क्लूड"; स्ट्रिंग str_2 ="अनजान"; स्ट्रिंग str_3 ="xcxclueing"; इंट एम =str_1.लंबाई (); इंट एन =str_2.लंबाई (); इंट ओ =str_3.length (); System.out.print ("एलसीएस की लंबाई है" + गणना एलसीएस (str_1, str_2, str_3, m, n, o)); }}आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
LCS की लंबाई 4 है