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