dynamic-programming
भारित गतिविधि चयन

भारित नौकरी निर्धारण एल्गोरिथम

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

समस्या यह है कि, कुछ नौकरियों को उनके प्रारंभ समय और समाप्ति समय के साथ दिया जाता है, और जब आप नौकरी समाप्त करते हैं तो एक लाभ, आप अधिकतम दो लाभ क्या दे सकते हैं जो समानांतर रूप से निष्पादित नहीं किए जा सकते हैं?

यह एक लालची एल्गोरिथ्म का उपयोग करते हुए गतिविधि चयन जैसा दिखता है, लेकिन इसमें एक अतिरिक्त ट्विस्ट है। अर्थात्, समाप्त नौकरियों की संख्या को अधिकतम करने के बजाय, हम अधिकतम लाभ कमाने पर ध्यान केंद्रित करते हैं। प्रदर्शन की संख्या यहाँ काम नहीं करती है।

आइए एक उदाहरण देखें:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    A    |    B    |    C    |    D    |    E    |    F    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (2,5)  |  (6,7)  |  (7,9)  |  (1,3)  |  (5,8)  |  (4,6)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    6    |    4    |    2    |    5    |    11   |    5    |
+-------------------------+---------+---------+---------+---------+---------+---------+

नौकरियों को एक नाम, उनकी शुरुआत और समय और लाभ के साथ निरूपित किया जाता है। कुछ पुनरावृत्तियों के बाद, हम यह पता लगा सकते हैं कि क्या हम जॉब-ए और जॉब-ई का प्रदर्शन करते हैं, हम 17 का अधिकतम लाभ प्राप्त कर सकते हैं। अब एक एल्गोरिथ्म का उपयोग करके यह कैसे पता करें?

पहली बात जो हम करते हैं वह गैर-घटते क्रम में उनके परिष्करण समय के अनुसार नौकरियों को क्रमबद्ध करना है। हम ऐसा क्यों करते हैं? ऐसा इसलिए है क्योंकि यदि हम एक ऐसी नौकरी का चयन करते हैं जिसे समाप्त करने में कम समय लगता है, तो हम अन्य नौकरियों को चुनने के लिए सबसे अधिक समय छोड़ देते हैं। हमारे पास है:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

हमारे पास अतिरिक्त अस्थायी सरणी Acc_Prof का आकार n (यहाँ, n नौकरियों की कुल संख्या को दर्शाता है)। इसमें नौकरियों के प्रदर्शन का अधिकतम संचित लाभ होगा। नहीं मिलता है? रुको और देखो। हम प्रत्येक कार्य के लाभ के साथ सरणी के मान को आरंभीकृत करेंगे। इसका मतलब है, Acc_Prof [i] पहले i-th नौकरी करने के लाभ को धारण करेगा।

+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब आइए i के साथ स्थिति 2 को निरूपित करें, और स्थिति 1 को j के साथ निरूपित किया जाएगा। हमारी रणनीति i-1 1 से पुनरावृति j करने होंगे और प्रत्येक यात्रा के बाद, हम, 1 से मैं भी वृद्धि होगी जब तक मैं n + 1 हो जाता है।

                               j        i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यदि जॉब [i] और जॉब [j] ओवरलैप होता है, तो हम जांचते हैं, कि अगर जॉब का पूरा समय [j] जॉब [i] के स्टार्ट टाइम से ज्यादा है, तो ये दोनों जॉब्स एक साथ नहीं किए जा सकते। हालाँकि, यदि वे ओवरलैप नहीं करते हैं, तो हम जाँचेंगे कि Acc_Prof [j] + लाभ [i]> Acc_Prof [i] । अगर ऐसा है, तो हम Acc_Prof [i] = Acc_Prof [j] + Profit [i] को अपडेट करेंगे। अर्थात्:

if Job[j].finish_time <= Job[i].start_time
    if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
        Acc_Prof[i] = Acc_Prof[j] + Profit[i]
    endif
endif

यहाँ Acc_Prof [j] + Profit [i] इन दो नौकरियों को करने के संचित लाभ का प्रतिनिधित्व करता है। आइए इसे हमारे उदाहरण के लिए देखें:

यहाँ जॉब [j] जॉब के साथ ओवरलैप होता है [i] । इसलिए इन्हें एक साथ नहीं किया जा सकता है। चूँकि हमारा j i-1 के बराबर है, हम i से i + 1 का मान बढ़ाते हैं जो कि 3 है । और हम j = 1 बनाते हैं।

                               j                   i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब नौकरी [j] और नौकरी [i] ओवरलैप नहीं है। इन दोनों नौकरियों को उठाकर हम जितना लाभ कमा सकते हैं, वह है: Acc_Prof [j] + Profit [i] = 5 + 5 = 10 जो Acc_Prof [i] से अधिक है। इसलिए हम Acc_Prof [i] = 10 को अपडेट करते हैं । हम यह भी 1. द्वारा वेतन वृद्धि जे हम मिलता है,

                                         j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यहाँ, नौकरी [j] नौकरी [i] के साथ ओवरलैप होती है और j भी i-1 के बराबर है। इसलिए हम i को 1 से बढ़ाते हैं, और j = 1 बनाते हैं। हमें मिला,

                               j                             i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब, नौकरी [j] और नौकरी [i] ओवरलैप नहीं करते हैं, हमें संचित लाभ 5 + 4 = 9 मिलता है , जो Acc_Prof [i] से अधिक है। हम Acc_Prof [i] = 9 और increment j को 1 से अपडेट करते हैं ।

                                         j                   i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    9    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

फिर से नौकरी [j] और नौकरी [i] ओवरलैप नहीं है। संचित लाभ है: 6 + 4 = 10 , जो Acc_Prof [i] से अधिक है। हम फिर से Acc_Prof [i] = 10 को अपडेट करते हैं । 1. द्वारा हम वेतन वृद्धि जे हम पाते हैं:

                                                   j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    10   |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यदि हम इस प्रक्रिया को जारी रखते हैं, तो i का उपयोग करके पूरी तालिका के माध्यम से पुनरावृत्ति करने के बाद, हमारी तालिका अंततः दिखाई देगी:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    14   |    17   |    8    |
+-------------------------+---------+---------+---------+---------+---------+---------+

_{* दस्तावेज़ को छोटा बनाने के लिए कुछ चरणों को छोड़ दिया गया है।}

यदि हम सरणी Acc_Prof के माध्यम से पुनरावृति करते हैं , तो हम अधिकतम लाभ 17 होने का पता लगा सकते हैं! छद्म कोड:

Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
    for j -> 1 to i-1
        if Job[j].finish_time <= Job[i].start_time
            if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
                Acc_Prof[i] = Acc_Prof[j] + Profit[i]
            endif
        endif
    endfor
endfor

maxProfit = 0
for i -> 1 to n
    if maxProfit < Acc_Prof[i]
        maxProfit = Acc_Prof[i]
return maxProfit

Acc_Prof सरणी को पॉप्युलेट करने की जटिलता O (n ² ) है। सरणी ट्रैवर्सल O (n) लेता है। तो इस एल्गोरिथ्म की कुल जटिलता O (n ² ) है।

अब, यदि हम यह जानना चाहते हैं कि अधिकतम लाभ प्राप्त करने के लिए कौन से काम किए गए थे, तो हमें सरणी को उल्टे क्रम में पार करने की आवश्यकता है और यदि Acc_Prof मैक्सप्रोफिट से मेल खाता है, तो हम एक स्टैक में नौकरी के नाम को आगे बढ़ाएंगे और लाभ का लाभ देंगे। अधिकतम नौकरी से वह नौकरी। हम ऐसा तब तक करेंगे जब तक हमारा मैक्सप्रोफिट> 0 या हम Acc_Prof सरणी के शुरुआती बिंदु तक नहीं पहुंच जाते। छद्म कोड की तरह दिखेगा:

Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
    if maxProfit is equal to Acc_Prof[i]
        S.push(Job[i].name
        maxProfit = maxProfit - Job[i].profit
    endif
endfor

इस प्रक्रिया की जटिलता है: O (n) ।

एक बात याद रखें, यदि कई कार्य शेड्यूल हैं जो हमें अधिकतम लाभ दे सकते हैं, तो हम इस प्रक्रिया के माध्यम से केवल एक नौकरी अनुसूची पा सकते हैं।