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