लालची एल्गोरिथ्म उदाहरण सहित: क्या है, विधि और दृष्टिकोण

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

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

• प्रत्येक चरणबद्ध समाधान को समस्या को उसके सर्वोत्तम स्वीकार्य समाधान की दिशा में संरचित करना चाहिए।
• यह पर्याप्त है यदि समस्या की संरचना सीमित संख्या में लालची चरणों में रुक सकती है।

सिद्धांत-निर्माण को जारी रखते हुए, आइए हम लालची खोज दृष्टिकोण से जुड़े इतिहास का वर्णन करें।

लालच का इतिहास Algorithms

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

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

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

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

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

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

लालची एल्गोरिथ्म की विशेषताएं

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

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

लालची दृष्टिकोण क्यों अपनाएं?

लालची दृष्टिकोण अपनाने के कारण इस प्रकार हैं:

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

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

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

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

कुल अवधि गतिविधि करने की लागत बताती है। यानी (समाप्त - आरंभ) हमें गतिविधि की लागत के रूप में अवधि बताती है।

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

Archiलालची दृष्टिकोण की व्याख्या

चरण 1) गतिविधि लागतों की सूची को स्कैन करें, सूचकांक 0 को विचारित सूचकांक के रूप में मानकर शुरू करें।

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

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

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

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

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

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

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

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

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

1. स्ट्रीमिंग संचालन के लिए नामस्थान.
2. TIME के ​​लिए एक वर्ग परिभाषा
3. एक घंटे का टाइमस्टैम्प.
4. TIME डिफ़ॉल्ट कन्स्ट्रक्टर
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. माना गया इंडेक्स वह इंडेक्स है जिसे मान द्वारा बुलाया जाता है। लालची_विस्तार माना गया इंडेक्स के ठीक बाद आरंभीकृत इंडेक्स है।

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 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

लालची तकनीक की सीमाएँ

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

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

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

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

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

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

लालची के उदाहरण Algorithms

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

• प्राइम का न्यूनतम स्पैनिंग ट्री एल्गोरिदम
• ट्रैवलिंग सेल्समैन की समस्या
• ग्राफ़ – मानचित्र रंग
• क्रुस्कल का न्यूनतम फैलाव वृक्ष एल्गोरिथ्म
• डिज्कस्ट्रा का न्यूनतम स्पैनिंग ट्री एल्गोरिदम
• ग्राफ – वर्टेक्स कवर
• बस्ता समस्या
• नौकरी निर्धारण समस्या

सारांश

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