This chapter will help you to learn about greedy algorithm and its examples in hindi and also give you understanding and knowledge about how to solve greedy algorithm.

Greedy Algorithm Proof and its examples in hindi

एक algorithms डिजाइन में कोई भी 'सिल्वर बुलेट' नहीं है जो सभी गणना समस्याओं का इलाज है। विभिन्न समस्याओं के लिए विभिन्न प्रकार की तकनीकों के उपयोग की आवश्यकता होती है। एक अच्छा प्रोग्रामर इन सभी तकनीकों का उपयोग समस्या के प्रकार के आधार पर करता है। कुछ आमतौर पर इस्तेमाल की जाने वाली तकनीकें हैं:

•     Divide and conquer
•     Randomized algorithms
•     Greedy algorithms (This is not an algorithm, it is a technique.)
•     Dynamic programming

 some advantages and disadvantages in Greedy algorithms

•     एक समस्या के लिए लालची algorithms (या यहां तक ​​कि कई Greedy algorithms) के साथ आना काफी आसान है।

•     Greedy algorithms के लिए रन टाइम का विश्लेषण आम तौर पर अन्य तकनीकों (जैसे डिवाइड और जीत) की तुलना में बहुत आसान होगा। डिवाइड और विजय तकनीक के लिए, यह स्पष्ट नहीं है कि तकनीक तेज या धीमी है। ऐसा इसलिए है क्योंकि iteration के प्रत्येक स्तर पर आकार छोटा हो जाता है और उप-समस्याओं की संख्या बढ़ जाती है।

•     मुश्किल हिस्सा यह है कि Greedy algorithms के लिए आपको शुद्धता के मुद्दों को समझने के लिए बहुत अधिक मेहनत करनी होगी। सही algorithms के साथ भी, यह साबित करना कठिन है कि यह सही क्यों है। यह साबित करना कि एक लालची algorithms सही है, एक विज्ञान की तुलना में एक कला का अधिक है। इसमें बहुत सारी रचनात्मकता शामिल है।

C. एक Greedy algorithms कैसे बनाएँ?

•     सरणी A को गैर-घटते क्रम में सॉर्ट करें।
•     एक-एक करके प्रत्येक आइटम का चयन करें।
•     उस समय को जोड़ें जो उस समय से आइटम को चालू करने में पूरा करेगा।
•     एक नंबर में जोड़ें।

#include <iostream>
    #include <algorithm>

    using namespace std;
    const int MAX = 105;
    int A[MAX];

    int main()
    {
        int T, N, numberOfThings = 0, currentTime = 0;
        cin >> N >> T;
        for(int i = 0;i < N;++i)
            cin >> A[i];
        sort(A, A + N);
        for(int i = 0;i < N;++i)
        {
            currentTime += A[i];
            if(currentTime > T)
                break;
            numberOfThings++;
        }
        cout << numberOfThings << endl;
        return 0;
    }

यह उदाहरण बहुत तुच्छ है और जैसे ही आप समस्या को पढ़ते हैं, यह स्पष्ट है कि आप इसके लिए Greedy algorithms को लागू कर सकते हैं।

अधिक कठिन समस्या पर विचार करें-निर्धारण समस्या।

आपके पास निम्नलिखित हैं:

•      उन सभी कार्यों की सूची, जिन्हें आपको आज पूरा करने की आवश्यकता है
•      प्रत्येक कार्य को पूरा करने के लिए आवश्यक समय
•      प्रत्येक कार्य को प्राथमिकता (या वजन)।

आपको यह निर्धारित करने की आवश्यकता है कि सबसे इष्टतम परिणाम प्राप्त करने के लिए आपको किस क्रम में कार्यों को पूरा करना चाहिए।

इस समस्या को हल करने के लिए आपको अपने इनपुट का विश्लेषण करने की आवश्यकता है। इस समस्या में, आपके इनपुट निम्नानुसार हैं:

•      जितनी नौकरियां आप पूरा करना चाहते हैं, उसके लिए integer N
•      List P: प्राथमिकता (या वजन)
•      List T: वह समय जो किसी कार्य को पूरा करने के लिए आवश्यक है

यह समझने के लिए कि किस मापदंड को अनुकूलित करना है, आपको प्रत्येक कार्य को पूरा करने के लिए आवश्यक कुल समय निर्धारित करना चाहिए।

 C(j) = T[1] + T[2] + .... + T[j] where 1 <= j <= N

ऐसा इसलिए है क्योंकि jth के काम के लिए पहले (j-1) कार्य पूरे होने तक इंतजार करना पड़ता है, जिसके बाद इसे पूरा करने के लिए T [j] समय की आवश्यकता होती है।

उदाहरण के लिए, यदि T = {1, 2, 3}, पूरा होने का समय होगा:

    C (1) = T [1] = 1
    C (2) = T [1] + T [2] = 1 + 2 = 3
    C (3) = T [1] + T [2] + T [3] = 1 + 2 + 3 = 6

आप स्पष्ट रूप से जितना संभव हो उतना कम समय पूरा करना चाहते हैं। लेकिन यह इतना आसान नहीं है।

किसी दिए गए अनुक्रम में, शुरुआत में पंक्तिबद्ध होने वाले Jobs का समय पूरा होने का समय कम हो जाता है और Jobs की समाप्ति की ओर Queued हो जाता है।

कार्यों को पूरा करने का इष्टतम तरीका क्या है?

यह आपके objective function पर निर्भर करता है। जबकि "Scheduling" समस्या में कई function कार्य हैं, आपका objective function एफ पूरा होने के समय का भारित योग है।

F = P[1] * C(1) + P[2] * C(2) + ...... + P[N] * C(N)

इस objective function को कम से कम किया जाना चाहिए।

Special Case

उन Special Case पर विचार करें जो कि optimal बात है कि सबसे optimal चीज क्या है। इन विशेष मामलों को देखने से कुछ प्राकृतिक Greedy algorithms सामने आएंगे, जिसके बाद आपको यह पता लगाना होगा कि कैसे इनको केवल एक उम्मीदवार तक सीमित किया जाए, जिसे आप सही साबित करेंगे।

Two Special Case ForFollows:

    यदि विभिन्न कार्यों को पूरा करने के लिए आवश्यक समय एक ही है यानी T [i] = T [j] जहां 1 <= i, j <= N है, लेकिन उनकी अलग-अलग प्राथमिकताएं हैं तो schedule the jobs करने के लिए किस क्रम में समझदारी होगी?

    यदि विभिन्न कार्यों की प्राथमिकताएं समान हैं यानी P [i] = P [j] जहां 1 <= i, j <= N है, लेकिन उनकी अलग-अलग लंबाई है तो आपको किस क्रम में लगता है कि हमें jobs का समय निर्धारित करना चाहिए?

यदि विभिन्न कार्यों को पूरा करने के लिए आवश्यक समय समान है, तो आपको उच्च प्राथमिकता वाले कार्य को प्राथमिकता देनी चाहिए 

Case 1
 objective function पर विचार करें जिसे आपको कम से कम करने की आवश्यकता है। मान लें कि विभिन्न कार्यों को पूरा करने के लिए आवश्यक समय t है।

T [i] = t जहाँ 1 <= i <= N है

चाहे जो भी अनुक्रम का उपयोग किया जाए, प्रत्येक कार्य के लिए पूरा होने का समय निम्नानुसार होगा:
C(1) = T[1] = t
C(2) = T[1] + T[2] = 2 * t
C(3) = T[1] + T[2] + T[3] = 3 * t
...
C(N) = N * t 

objective function को यथासंभव छोटा बनाने के लिए सर्वोच्च प्राथमिकता को कम से कम समय पूरा करने के साथ जुड़ा होना चाहिए।

Case 2

दूसरे मामले में, यदि विभिन्न कार्यों की प्राथमिकताएं समान हैं, तो आपको उस कार्य का पक्ष लेना होगा जिसे पूरा करने के लिए कम से कम समय की आवश्यकता होती है। मान लें कि विभिन्न कार्यों की प्राथमिकताएं P हैं।

F = P[1] * C(1) + P[2] * C(2) + ...... + P[N] * C(N)
F = p * C(1) + p * C(2) + ...... + p * C(N)
F = p * (C(1) + C(2) + ...... + C(N)) 

F के मूल्य को कम करने के लिए, आपको कम से कम (C (1) + C (2) + ...... + C (N)) करना होगा, जो यदि आप उन कार्यों पर काम करना शुरू कर सकते हैं जिनमें सबसे कम समय की आवश्यकता होती है पूरा करना।

दो नियम हैं। उन कार्यों को प्राथमिकता दें जो:

•     एक उच्च प्राथमिकता है
•     पूरा करने के लिए कम समय लें

अगला कदम विशेष मामलों से परे, सामान्य मामले में जाना है। इस मामले में, प्राथमिकताएं और प्रत्येक कार्य के लिए आवश्यक समय अलग-अलग हैं।

यदि आपके पास 2 कार्य हैं और ये दोनों नियम आपको एक ही सलाह देते हैं, तो जिस कार्य की प्राथमिकता अधिक है और पूरा होने में कम समय लगता है, वह कार्य स्पष्ट रूप से पहले पूरा किया जाना चाहिए। लेकिन क्या होगा अगर ये दोनों नियम आपको परस्पर विरोधी सलाह दें? 

यदि आपके पास ऐसे कार्यों की एक जोड़ी है जहाँ उनमें से एक की प्राथमिकता अधिक है और दूसरे को पूरा करने के लिए अधिक समय की आवश्यकता है? (यानी P [i]> P [j] लेकिन T [i]> T [j])। आपको पहले कौन सा पूरा करना चाहिए?

क्या आप इन 2 मापदंडों (समय और प्राथमिकता) को एक अंक में जोड़ सकते हैं जैसे कि यदि आप उच्च स्कोर से निचले स्कोर तक की नौकरियों को छांटते हैं तो आपको हमेशा एक इष्टतम समाधान मिलेगा?

2 नियम याद रखें।

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

आप एक साधारण गणितीय फ़ंक्शन का उपयोग कर सकते हैं, जो इनपुट के रूप में 2 नंबर (प्राथमिकता और आवश्यक समय) लेता है और इन दो गुणों को पूरा करते हुए आउटपुट के रूप में एक नंबर (स्कोर) देता है। (इस तरह के कार्यों की अनंत संख्या है।)

सबसे सरल कार्यों में से दो लेते हैं जिनमें ये गुण हैं

    Algorithm # 1:decreasing value of ( P[i] - T[i] ) नौकरियों का आदेश दें
     Algorithm # 2: decreasing value of ( P[i] / T[i] ) नौकरियों का आदेश दें

सादगी के लिए हम मान रहे हैं कि कोई संबंध नहीं है।

अब आपके पास दो Algorithm हैं और उनमें से कम से कम एक गलत है। एल्गोरिथ्म को नियम दें जो सही काम नहीं करता है।

T = {5, 2} और P = {3, 1}Algorithm के अनुसार # 1 ( P[1] - T[1] ) < ( P[2] - T[2] ), इसलिए, दूसरा कार्य पहले पूरा किया जाना चाहिए और आपका उद्देश्य कार्य होगा:
F = P[1] * C(1) + P[2] * C(2) = 1 * 2 + 3 * 7 = 23 

Algorithm # 2 (P [1] / T [1])> (P [2] / T [2]) के अनुसार, इसलिए, पहला कार्य पहले पूरा किया जाना चाहिए और आपका उद्देश्य कार्य होगा:

F = P [1] * C (1) + P [2] * C (2) = 3 * 5 + 1 * 7 = 22Algorithm # 1 आपको इष्टतम उत्तर नहीं देगा और इसलिए, Algorithm # 1 सही (हमेशा) सही नहीं है।

नोट: याद रखें कि Greedy Algorithm अक्सर गलत होते हैं। सिर्फ इसलिए कि एल्गोरिथ्म # 1 सही नहीं है, इसका अर्थ यह नहीं है कि एल्गोरिथम # 2 के सही होने की गारंटी है। हालांकि, यह पता चलता है कि इस मामले में एल्गोरिथ्म # 2 हमेशा सही होता है।

इसलिए, अंतिम Algorithm जो objective function का optimal मान लौटाता है: 

Algorithm (P, T, N)
    {
        let S be an array of pairs ( C++ STL pair ) to store the scores and their indices
        , C be the completion times and F be the objective function
        for i from 1 to N:
            S[i] = ( P[i] / T[i], i )            // Algorithm #2
        sort(S)
        C = 0
        F = 0
        for i from 1 to N:                // Greedily choose the best choice
            C = C + T[S[i].second]
            F = F + P[S[i].second]*C
        return F
    }

Greedy Algorithm Time Complexity

Sorting Funcation Time complexity : O(N * logN)
overall time complexity is O(2 * N + N * logN) = O(N * logN)

यह साबित करने के लिए कि Algorithm # 2 सही है, विरोधाभास द्वारा सबूत का उपयोग करें। यह मान लें कि आप जो साबित करने की कोशिश कर रहे हैं वह झूठा है और उस चीज़ से कुछ हासिल करें जो जाहिर तौर पर झूठी है।

इसलिए, मान लें कि यह Greedy Algorithm एक इष्टतम समाधान का उत्पादन नहीं करता है और Greedy Algorithm की तुलना में एक और समाधान है (Greedy Algorithm द्वारा आउटपुट नहीं)।

A = Greedy अनुसूची (जो एक Optimal कार्यक्रम नहीं है)
B = Optimal अनुसूची (सबसे अच्छा शेड्यूल जो आप बना सकते हैं)

Assumption # 1: सभी (पी [i] / T [i]) अलग हैं।
Assumption # 2: (सिर्फ सादगी के लिए, सामान्यता को प्रभावित नहीं करेगा) (P [1] / T [1])> (P [2] / T [2])> ....> (P [N] / टी [एन])

Assumption # 2 की धारणा के कारण, Greedy अनुसूची ए = (1, 2, 3, ....., एन) होगी। चूँकि A Optimal नहीं है (जैसा कि हमने ऊपर माना है) और A, B के बराबर नहीं है (क्योंकि B इष्टतम है), आप दावा कर सकते हैं कि B में दो लगातार नौकरियां होनी चाहिए (i, j) जैसे कि उन 2 लगातार नौकरियों में से पहले की है एक बड़ा सूचकांक (i> j)। यह सच है क्योंकि एकमात्र अनुसूची जिसमें संपत्ति है, जिसमें केवल सूचकांक ऊपर जाते हैं, ए = (1, 2, 3, ...., एन) है।

इसलिए, बी = (1, 2, ..., आई, जे, ..., एन) जहां मैं> जे।

आपको यह भी सोचना होगा कि इन 2 नौकरियों को स्वैप करने पर लाभ या हानि प्रभाव क्या है। निम्नलिखित के पूरा होने पर इस स्वैप के प्रभाव के बारे में सोचें:

1.     I और j के अलावा अन्य k पर काम करें
2.     मैं पर काम
3.     J पर काम करें

K के लिए, 2 मामले होंगे:

जब k, B के i और j के बाईं ओर है, यदि आप i और j को स्वैप करते हैं, तो k के पूरा होने के समय पर कोई प्रभाव नहीं पड़ेगा।

जब k बी स्वैपिंग के बाद i और j के दाईं ओर होता है, तो k का पूरा होने का समय C (k) = T [1] + T [2] + .. + T [j] + T [i] + होता है। .टी [के], के ही रहेगा।

I पूर्ण समय के लिए: स्वैप करने से पहले C (i) = T [1] + T [2] + ... + T [i] स्वैपिंग के बाद C (i) = T [1] + T [2] + होता है ... + टी [जे] + टी [मैं]

स्पष्ट रूप से, i के लिए पूरा होने का समय T [j] तक जाता है और j के लिए पूरा होने का समय T [i] से कम हो जाता है।

Loss due to the swap is (P[i] * T[j])
Profit due to the swap is (P[j] * T[i])

# 2 का उपयोग करते हुए, i> j का तात्पर्य है कि (P [i] / T [i]) <(P [j] / T [j])। इसलिए (P [i] * T [j]) <(P [j] * T [i]) जिसका अर्थ है Mean Lose < Profit। इसका मतलब है कि स्वैप बी को बेहतर बनाता है लेकिन यह एक विरोधाभास है क्योंकि हमने मान लिया है कि बी इष्टतम कार्यक्रम है। इससे हमारा प्रमाण पूरा होता है।Greedy Algorithm का उपयोग कहां करें?

एक समस्या को काम करने के लिए एक Greedy Algorithm के लिए इन दो घटकों को शामिल करना चाहिए:

    इसमें इष्टतम सबस्ट्रक्चर हैं। समस्या के लिए Optimal समाधान में उप-समस्याओं का इष्टतम समाधान होता है।

    इसके पास एक Greedy संपत्ति है (इसकी शुद्धता साबित करने के लिए कठिन!)। यदि आप एक ऐसा विकल्प बनाते हैं जो इस समय सबसे अच्छा लगता है और शेष उप-समस्याओं को बाद में हल करता है, तो आप अभी भी एक इष्टतम समाधान तक पहुंच सकते हैं। आपको अपने पहले के विकल्पों पर पुनर्विचार नहीं करना होगा।

उदाहरण के लिए:

    Activity Selection problem
    Fractional Knapsack problem
    Scheduling problem

उदाहरण

Greedy विधि काफी शक्तिशाली है और समस्याओं की एक विस्तृत श्रृंखला के लिए अच्छी तरह से काम करती है। कई एल्गोरिदम को  Greedy Algorithm के अनुप्रयोगों के रूप में देखा जा सकता है, जैसे (शामिल है लेकिन यह सीमित नहीं है):

    Minimum Spanning Tree
    Dijkstra’s algorithm for shortest paths from a single source
    Huffman codes ( data-compression codes )