लालची एल्गोरिथम उदाहरण के साथ: लालची विधि & पहुंच

एक लालची एल्गोरिथ्म क्या है?

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

लालची दृष्टिकोण के आधार पर एक समस्या को हल करने के लिए, दो चरण हैं

1. वस्तुओं की सूची को स्कैन करना
2. अनुकूलन

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

लालची दृष्टिकोण को समझने के लिए, आपको पुनरावृत्ति और संदर्भ स्विचिंग का कार्यसाधक ज्ञान होना चाहिए। यह आपको कोड को ट्रेस करने के तरीके को समझने में मदद करता है। आप अपने स्वयं के आवश्यक और पर्याप्त बयानों के संदर्भ में लालची प्रतिमान को परिभाषित कर सकते हैं।

दो स्थितियां लालची प्रतिमान को परिभाषित करती हैं।

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

प्रमेय जारी रहने के साथ, हम लालची खोज दृष्टिकोण से जुड़े इतिहास का वर्णन करते हैं।

इस लालची एल्गोरिथ्म ट्यूटोरियल में, आप सीखेंगे:

• लालची एल्गोरिदम का इतिहास
• लालची रणनीतियाँ और निर्णय
• लालची दृष्टिकोण के लक्षण
• लालची दृष्टिकोण का उपयोग क्यों करें?
• गतिविधि चयन समस्या को कैसे हल करें
• लालची दृष्टिकोण की वास्तुकला
• लालची एल्गोरिदम का नुकसान

लालची एल्गोरिदम का इतिहास

यहाँ लालची एल्गोरिदम का एक महत्वपूर्ण स्थल है:

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

लालची रणनीतियाँ और निर्णय

अपने सबसे आसान रूप में तर्क को "लालची" या "लालची नहीं" के रूप में उबला गया था। इन कथनों को प्रत्येक एल्गोरिथम चरण में अग्रिम करने के लिए उठाए गए दृष्टिकोण से परिभाषित किया गया था।

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

संक्षेप में, एक एल्गोरिथ्म लालची होना बंद कर देता है यदि किसी भी स्तर पर यह एक ऐसा कदम उठाता है जो स्थानीय रूप से लालची नहीं है। लालची समस्याओं के लालच के आगे कोई गुंजाइश नहीं है।

लालची दृष्टिकोण के लक्षण

लालची विधि एल्गोरिथ्म की महत्वपूर्ण विशेषताएं हैं:

• लागतों या मूल्य विशेषताओं के साथ संसाधनों की एक क्रमबद्ध सूची है। ये एक सिस्टम पर बाधाओं को निर्धारित करते हैं।
• एक बाधा लागू होने में आप संसाधनों की अधिकतम मात्रा लेंगे।
• उदाहरण के लिए, किसी गतिविधि शेड्यूलिंग समस्या में, संसाधन लागत घंटों में होती है, और गतिविधियों को क्रमबद्ध रूप से निष्पादित करने की आवश्यकता होती है।

लालची दृष्टिकोण का उपयोग क्यों करें?

यहाँ लालची दृष्टिकोण का उपयोग करने के कारण हैं:

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

गतिविधि चयन समस्या को कैसे हल करें

गतिविधि शेड्यूलिंग उदाहरण में, प्रत्येक गतिविधि के लिए "प्रारंभ" और "समाप्त" समय है। प्रत्येक गतिविधि को संदर्भ के लिए एक संख्या द्वारा अनुक्रमित किया जाता है। दो गतिविधि श्रेणियां हैं।

1. गतिविधि माना जाता है : वह गतिविधि है, जो वह संदर्भ है जिसमें से एक से अधिक शेष गतिविधि करने की क्षमता का विश्लेषण किया जाता है।
2. शेष गतिविधियाँ: मानी गई गतिविधि के आगे एक या एक से अधिक अनुक्रमित गतिविधियाँ

कुल अवधि गतिविधि प्रदर्शन की लागत देती है। यह (खत्म - शुरू) हमें एक गतिविधि की लागत के रूप में अवधि देता है।

आप सीखेंगे कि लालची सीमा एक शेष गतिविधि की संख्या है जिसे आप एक विचारित गतिविधि के समय में प्रदर्शन कर सकते हैं।

लालची दृष्टिकोण की वास्तुकला

चरण 1)

गतिविधि की लागतों की सूची को स्कैन करें, माना जाता है कि सूचकांक 0 के साथ शुरू होता है।

चरण 2)

जब अधिक गतिविधियां समय के साथ समाप्त हो सकती हैं, तो माना गतिविधि समाप्त हो जाती है, एक या अधिक शेष गतिविधियों की खोज करना शुरू करें।

चरण 3)

यदि कोई और शेष गतिविधियाँ नहीं हैं, तो वर्तमान शेष गतिविधि अगली विचारित गतिविधि बन जाती है। नई विचार गतिविधि के साथ चरण 1 और चरण 2 को दोहराएं। यदि कोई शेष गतिविधियां नहीं बची हैं, तो चरण 4 पर जाएं।

चरण 4 )

माना सूचकांकों का संघ लौटाएं। ये गतिविधि सूचकांक हैं जिनका उपयोग थ्रूपुट को अधिकतम करने के लिए किया जाएगा।

कोड स्पष्टीकरण

#include#include#include#define MAX_ACTIVITIES 12

कोड की व्याख्या:

1. शामिल हैडर फ़ाइलें / कक्षाएं
2. उपयोगकर्ता द्वारा प्रदान की जाने वाली गतिविधियों की अधिकतम संख्या।

using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};

कोड की व्याख्या:

1. स्ट्रीमिंग संचालन के लिए नामस्थान।
2. TIME के ​​लिए एक वर्ग परिभाषा
3. एक घंटे का टाइमस्टैम्प।
4. एक डिफ़ॉल्ट डिफ़ॉल्ट निर्माता
5. घंटे चर।

class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

कोड की व्याख्या:

1. गतिविधि से एक वर्ग परिभाषा
2. एक अवधि को परिभाषित करने वाले टाइमस्टैम्प
3. सभी टाइमस्टैम्प को डिफ़ॉल्ट कंस्ट्रक्टर में 0 से प्रारंभ किया जाता है

class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;

कोड की व्याख्या:

1. शेड्यूलर वर्ग परिभाषा का भाग 1।
2. माना सूचकांक, सरणी को स्कैन करने के लिए प्रारंभिक बिंदु है।
3. आरंभीकरण सूचकांक का उपयोग यादृच्छिक टाइमस्टैम्प को असाइन करने के लिए किया जाता है।
4. नए ऑब्जेक्ट का उपयोग करके ऑब्जेक्ट ऑब्जेक्ट की एक सरणी को गतिशील रूप से आवंटित किया जाता है।
5. अनुसूचित सूचक लालच के लिए वर्तमान आधार स्थान को परिभाषित करता है।

Scheduler(){considered_index = 0;scheduled = NULL;… … 

कोड की व्याख्या:

1. अनुसूचक रचनाकार - अनुसूचक वर्ग परिभाषा का भाग 2।
2. माना गया सूचकांक वर्तमान स्कैन की वर्तमान शुरुआत को परिभाषित करता है।
3. वर्तमान लालची सीमा शुरुआत में अपरिभाषित है।

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++){current_activities[init_index].start.hours =rand() % 12;current_activities[init_index].finish.hours =current_activities[init_index].start.hours +(rand() % 2);printf("\nSTART:%d END %d\n",current_activities[init_index].start.hours,current_activities[init_index].finish.hours);}… … 

कोड की व्याख्या:

1. लूप के लिए वर्तमान में निर्धारित गतिविधियों में से प्रत्येक के शुरू होने के घंटे और अंत के घंटे शुरू करें।
2. प्रारंभ समय प्रारंभ।
3. अंत समय आरंभीकरण हमेशा शुरुआत घंटे के बाद या बिल्कुल।
4. आबंटित अवधि का प्रिंट आउट करने के लिए डिबग स्टेटमेंट।

public:Activity * activity_select(int);};

कोड की व्याख्या:

1. भाग 4 - अनुसूचक वर्ग परिभाषा का अंतिम भाग।
2. गतिविधि का चयन समारोह आधार के रूप में एक प्रारंभिक बिंदु सूचकांक लेता है और लालची खोज को लालची उपप्रकारों में विभाजित करता है।

Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… … 

1. गुंजाइश रिज़ॉल्यूशन ऑपरेटर (: :) का उपयोग करके, फ़ंक्शन परिभाषा प्रदान की जाती है।
2. माना गया सूचकांक मूल्य द्वारा बुलाया गया सूचकांक है। माना सूचकांक के बाद greedy_extent केवल एक सूचकांक है।

Activity * Scheduler :: activity_select(int considered_index){while( (greedy_extent < MAX_ACTIVITIES ) &&((this->current_activities[greedy_extent]).start.hours <(this->current_activities[considered_index]).finish.hours )){printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",(this->current_activities[greedy_extent]).start.hours,(this->current_activities[greedy_extent]).finish.hours,greedy_extent + 1);greedy_extent++;}… … 

कोड की व्याख्या:

1. मुख्य तर्क- लालच हद तक गतिविधियों की संख्या तक सीमित है ।
2. वर्तमान गतिविधि के प्रारंभ घंटों को माना गतिविधि (माना सूचकांक द्वारा दिया गया) समाप्त होने से पहले समय-सारिणी के रूप में जाँच की जाती है।
3. जब तक यह संभव है, एक वैकल्पिक डिबग स्टेटमेंट मुद्रित किया जाता है।
4. गतिविधि सरणी पर अगली अनुक्रमणिका के लिए अग्रिम

… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}

कोड की व्याख्या:

1. सशर्त जाँच करता है कि क्या सभी गतिविधियों को कवर किया गया है।
2. यदि नहीं, तो आप वर्तमान बिंदु के रूप में माना सूचकांक के साथ अपने लालची को पुनः आरंभ कर सकते हैं। यह एक पुनरावर्ती कदम है जो समस्या के बयान को लालच से विभाजित करता है।
3. यदि हाँ, यह लालच फैलाने के लिए कोई गुंजाइश नहीं के साथ फोन करने वाले के लिए वापस आ जाता है।

int main(){Scheduler *activity_sched = new Scheduler();activity_sched->scheduled = activity_sched->activity_select(activity_sched->considered_index);return 0;}

कोड की व्याख्या:

1. मुख्य कार्य अनुसूचक का आह्वान करने के लिए किया जाता है।
2. एक नया समयबद्धक त्वरित है।
3. एक्टिविटी सिलेक्ट फंक्शन, जो टाइपिंग एक्टिविटी के एक पॉइंटर को लौटाता है, लालची सर्च खत्म होने के बाद वापस कॉलर के पास आता है।

आउटपुट:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

लालची एल्गोरिदम का नुकसान

यह लालची समस्याओं के लिए उपयुक्त नहीं है जहां हर उपप्रकार के लिए हल की तरह एक समाधान की आवश्यकता होती है।

इस तरह के लालची एल्गोरिथ्म में समस्याएं आती हैं, लालची विधि गलत हो सकती है; सबसे खराब स्थिति में भी एक गैर-इष्टतम समाधान के लिए नेतृत्व।

इसलिए लालची एल्गोरिदम का नुकसान यह जानने का उपयोग कर रहा है कि वर्तमान लालची राज्य से आगे क्या है।

नीचे लालची विधि के नुकसान का चित्रण है:

एक पेड़ (उच्च मूल्य उच्च लालच) के रूप में यहां दिखाए गए लालची स्कैन में, मूल्य: 40 पर एक एल्गोरिथ्म राज्य, अगले मूल्य के रूप में 29 लेने की संभावना है। इसके अलावा, इसकी खोज 12 पर समाप्त होती है।

हालांकि, अगर एल्गोरिथ्म ने एक उप-इष्टतम पथ लिया या एक जीत की रणनीति अपनाई। उसके बाद 25 को 40 के बाद, और कुल लागत में सुधार 65 होगा, जो कि एक उप-अपनाने के निर्णय के रूप में 24 अंक अधिक है।

लालची एल्गोरिदम के उदाहरण

अधिकांश नेटवर्किंग एल्गोरिदम लालची दृष्टिकोण का उपयोग करते हैं। यहाँ कुछ लालची एल्गोरिथ्म उदाहरणों की एक सूची दी गई है:

• प्राइम की मिनिमल स्पैनिंग ट्री एल्गोरिथम
• ट्रैवलिंग सेल्समैन की समस्या
• ग्राफ - नक्शा रंग
• क्रुस्कल की मिनिमल स्पैनिंग ट्री एलगोरिदम
• दिज्क्स्ट्रा का मिनिमल स्पैनिंग ट्री एलगोरिदम
• ग्राफ - वर्टेक्स कवर
• क्लेश समस्या
• नौकरी निर्धारण समस्या

सारांश:

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