गतिविधि चयन समस्या: Difference between revisions

From Vigyanwiki
No edit summary
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{short description|Combinatorial optimization problem}}
{{short description|Combinatorial optimization problem}}
'''गतिविधि चयन समस्या''' एक [[संयुक्त अनुकूलन]] समस्या है जो एक निश्चित समय सीमा के भीतर प्रदर्शन करने के लिए गैर-परस्पर विरोधी गतिविधियों के चयन से संबंधित है, जिसमें प्रत्येक गतिविधि को प्रारंभ समय (सी) और समाप्ति समय (फाई) द्वारा चिह्नित किया जाता है। समस्या यह है कि एक व्यक्ति या [[मशीन]] द्वारा की जा सकने वाली अधिकतम गतिविधियों का चयन किया जाए, यह मानते हुए कि एक व्यक्ति एक समय में केवल एक ही गतिविधि पर काम कर सकता है। '''गतिविधि चयन समस्या''' को अंतराल शेड्यूलिंग अधिकतमीकरण समस्या (आईएसएमपी) के रूप में भी जाना जाता है, जो कि अधिक सामान्य अंतराल शेड्यूलिंग समस्या का एक विशेष प्रकार है।
'''गतिविधि चयन समस्या''' एक [[संयुक्त अनुकूलन]] समस्या है जो एक निश्चित समय सीमा के भीतर प्रदर्शन करने के लिए गैर-परस्पर विरोधी गतिविधियों के चयन से संबंधित है, जिसमें प्रत्येक गतिविधि को प्रारंभ समय (s<sub>i</sub>) और समाप्ति समय (f<sub>i</sub>) द्वारा चिह्नित किया जाता है। समस्या यह है कि एक व्यक्ति या [[मशीन]] द्वारा की जा सकने वाली अधिकतम गतिविधियों का चयन किया जाए, यह मानते हुए कि व्यक्ति एक समय में केवल एक ही गतिविधि पर काम कर सकता है। '''गतिविधि चयन समस्या''' को अंतराल शेड्यूलिंग अधिकतमीकरण समस्या (आईएसएमपी) के रूप में भी जाना जाता है, जो कि अधिक सामान्य अंतराल शेड्यूलिंग समस्या का एक विशेष प्रकार है।


इस समस्या का एक उत्कृष्ट अनुप्रयोग कई प्रतिस्पर्धी घटनाओं के लिए एक कमरे को शेड्यूल करना है, जिनमें से प्रत्येक की अपनी समय की आवश्यकताएं (प्रारंभ और समाप्ति समय) होती हैं, और संचालन अनुसंधान के ढांचे के भीतर कई अन्य चीजें उत्पन्न होती हैं।
इस समस्या का उत्कृष्ट अनुप्रयोग कई प्रतिस्पर्धी घटनाओं के लिए कमरे को शेड्यूल करना है, जिनमें से प्रत्येक की अपनी समय की आवश्यकताएं (प्रारंभ और समाप्ति समय) होती हैं, और संचालन अनुसंधान के ढांचे के भीतर कई अन्य चीजें उत्पन्न होती हैं।


==औपचारिक परिभाषा==
==औपचारिक परिभाषा==
मान लीजिए कि वहाँ ''n'' गतिविधियाँ मौजूद हैं, जिनमें से प्रत्येक को प्रारंभ समय ''s<sub>i</sub>'' और समाप्ति समय ''f<sub>i</sub>'' द्वारा दर्शाया गया है। यदि ''s<sub>i</sub>'' ≥ ''f<sub>j</sub>'' या ''s<sub>j</sub>'' ≥ ''f<sub>i</sub>'' हो तो दो गतिविधियाँ ''i'' और ''j'' गैर-विरोधाभासी कहलाती हैं। गतिविधि चयन समस्या में गैर-परस्पर विरोधी गतिविधियों के अधिकतम समाधान सेट (S) को खोजना शामिल है, या अधिक सटीक रूप से कोई समाधान सेट S' मौजूद नहीं होना चाहिए जैसे कि |S'| > |S| उस स्थिति में जब एकाधिक अधिकतम समाधानों का आकार समान होता है।
मान लीजिए कि जहां ''n'' गतिविधियाँ उपस्थित हैं, जिनमें से प्रत्येक को प्रारंभ समय ''s<sub>i</sub>'' और समाप्ति समय ''f<sub>i</sub>'' द्वारा दर्शाया गया है। यदि ''s<sub>i</sub>'' ≥ ''f<sub>j</sub>'' या ''s<sub>j</sub>'' ≥ ''f<sub>i</sub>'' हो तो दो गतिविधियाँ ''i'' और ''j'' गैर-विरोधाभासी कहलाती हैं। गतिविधि चयन समस्या में गैर-परस्पर विरोधी गतिविधियों के अधिकतम समाधान सेट (S) को खोजना सम्मिलित है, या अधिक सटीक रूप से कोई समाधान सेट S' उपस्थित नहीं होना चाहिए जैसे कि |S'| > |S| उस स्थिति में जब एकाधिक अधिकतम समाधानों का आकार समान होता है।


==इष्टतम समाधान==
==इष्टतम समाधान==
गतिविधि चयन समस्या इस मायने में उल्लेखनीय है कि समाधान खोजने के लिए ग्रीडी एल्गोरिथ्म का उपयोग करने से हमेशा एक इष्टतम समाधान मिलेगा। एल्गोरिदम के पुनरावृत्त संस्करण का एक छद्मकोड स्केच और इसके परिणाम की इष्टतमता का प्रमाण नीचे शामिल है।
गतिविधि चयन समस्या इस मायने में उल्लेखनीय है कि समाधान खोजने के लिए ग्रीडी एल्गोरिथ्म का उपयोग करने से हमेशा इष्टतम समाधान मिलेगा। एल्गोरिदम के पुनरावृत्त संस्करण का छद्मकोड स्केच और इसके परिणाम की इष्टतमता का प्रमाण नीचे सम्मिलित है।


===एल्गोरिदम===
===एल्गोरिदम===
Line 30: Line 30:
==== स्पष्टीकरण ====
==== स्पष्टीकरण ====


पंक्ति 1: इस एल्गोरिदम को ''ग्रीडी-पुनरावृत्ति-गतिविधि-चयनकर्ता'' कहा जाता है, क्योंकि यह सबसे पहले एक ग्रीडी एल्गोरिथ्म है, और फिर यह पुनरावृत्त है। इस ग्रीडी एल्गोरिदम का एक पुनरावर्ती संस्करण भी है।
'''लाइन 1''': इस एल्गोरिदम को ''ग्रीडी-पुनरावृत्ति-गतिविधि-चयनकर्ता'' कहा जाता है, क्योंकि यह सबसे पहले ग्रीडी एल्गोरिथ्म है, और फिर यह पुनरावृत्त है। इस ग्रीडी एल्गोरिदम का एक पुनरावर्ती संस्करण भी है।
*<math>A</math> गतिविधियों से युक्त एक सारणी है।
*<math>A</math> गतिविधियों से युक्त एक ऐरे है।
* <math>s</math> एक सारणी है जिसमें गतिविधियों के प्रारंभ समय शामिल हैं <math>A</math>.
* <math>s</math> एक ऐरे है जिसमें <math>A</math> गतिविधियों के प्रारंभ समय सम्मिलित हैं।
* <math>f</math> एक सारणी है जिसमें गतिविधियों के समापन समय शामिल हैं <math>A</math>.
* <math>f</math> एक ऐरे है जिसमें <math>A</math> गतिविधियों के समापन समय सम्मिलित हैं।


ध्यान दें कि इन सरणियों को 1 से शुरू करके संबंधित सरणी की लंबाई तक अनुक्रमित किया जाता है।
ध्यान दें कि इन ऐरे को 1 से प्रारम्भ करके संबंधित ऐरे की लंबाई तक अनुक्रमित किया जाता है।


पंक्ति 3: गतिविधियों की श्रृंखला को ''समाप्ति समय के बढ़ते क्रम'' में क्रमबद्ध करें <math>A</math> सरणी में संग्रहीत समाप्ति समय का उपयोग करके <math>f</math>. यह ऑपरेशन इसमें किया जा सकता है <math>O(n \cdot \log n)</math> समय, उदाहरण के लिए मर्ज सॉर्ट, हीप सॉर्ट, या त्वरित सॉर्ट एल्गोरिदम का उपयोग करना।
'''लाइन 3:''' ऐरे <math>f</math> में संग्रहीत समाप्ति समय का उपयोग करके गतिविधियों की ऐरे <math>A</math> को समापन समय के बढ़ते क्रम में क्रमबद्ध करें। उदाहरण के लिए मर्ज सॉर्ट, हीप सॉर्ट, या क्विक सॉर्ट एल्गोरिदम का उपयोग करके यह ऑपरेशन <math>O(n \cdot \log n)</math> समय में किया जा सकता है।
पंक्ति 4: एक सेट बनाएं <math>S</math> चयनित गतिविधियों को संग्रहीत करने के लिए, और इसे गतिविधि के साथ प्रारंभ करने के लिए <math>A[1]</math> जिसका जल्द से जल्द खत्म होने का समय है।


पंक्ति 5: एक वेरिएबल बनाता है <math>k</math> जो अंतिम चयनित गतिविधि के सूचकांक का ट्रैक रखता है।
'''लाइन 4:''' सेट <math>S</math> बनाएं चयनित गतिविधियों को संग्रहीत करने के लिए, और इसे गतिविधि के साथ प्रारंभ करने के लिए <math>A[1]</math> जिसका जल्द से जल्द खत्म होने का समय है।


पंक्ति 9: उस सरणी के दूसरे तत्व से पुनरावृत्ति शुरू होती है <math>A</math> इसके अंतिम तत्व तक.
'''लाइन 5:''' वेरिएबल <math>k</math> बनाता है जो अंतिम चयनित गतिविधि के सूचकांक का ट्रैक रखता है।


पंक्तियाँ 10,11: यदि ''प्रारंभ समय'' <math>s[i]</math> की <math>ith</math> गतिविधि (<math>A[i]</math>) समाप्ति समय से अधिक या उसके बराबर है <math>f[k]</math> अंतिम चयनित गतिविधि का (<math>A[k]</math>), तब <math>A[i]</math> सेट में चयनित गतिविधियों के अनुकूल है <math>S</math>, और इस प्रकार इसे इसमें जोड़ा जा सकता है <math>S</math>.
'''लाइन 9:''' उस सरणी <math>A</math> के दूसरे एलिमेंट से उसके अंतिम एलिमेंट तक पुनरावृति प्रारम्भ करता है।


पंक्ति 12: अंतिम चयनित गतिविधि का सूचकांक अभी जोड़ी गई गतिविधि में अद्यतन किया जाता है <math>A[i]</math>.
'''लाइन 10,11:''' यदि <math>ith</math> गतिविधि <math>A[i]</math> का ''प्रारंभ समय'' <math>s[i]</math> अंतिम चयनित गतिविधि <math>A[k]</math> के समापन समय <math>f[k]</math> से अधिक या बराबर है, तब <math>A[i]</math>सेट <math>S</math> में चयनित गतिविधियों के अनुकूल है, और इस प्रकार इसे <math>S</math> में जोड़ा जा सकता है।
 
'''लाइन 12:''' अंतिम चयनित गतिविधि का सूचकांक अभी जोड़ी गई गतिविधि <math>A[i]</math> में अद्यतन किया जाता है।


===इष्टतमता का प्रमाण===
===इष्टतमता का प्रमाण===
होने देना <math>S = \{1, 2, \ldots , n\}</math> समापन समय के अनुसार आदेशित गतिविधियों का समूह बनें। ये मान लीजिए <math>A\subseteq S</math> एक इष्टतम समाधान है, जिसे समापन समय के अनुसार भी आदेश दिया गया है; और में पहली गतिविधि का सूचकांक है <math>k\neq 1</math>, यानी, यह इष्टतम समाधान ग्रीडी विकल्प से शुरू नहीं होता है। हम वो दिखाएंगे <math>B = (A \setminus \{k\}) \cup \{1\}</math>, जो ग्रीडी विकल्प (गतिविधि 1) से शुरू होता है, एक और इष्टतम समाधान है। तब से <math>f_1 \leq f_k</math>, और में गतिविधियाँ परिभाषा के अनुसार [[असंयुक्त सेट]] हैं, बी में गतिविधियाँ भी असंयुक्त हैं। चूँकि B की गतिविधियों की संख्या A के समान है, अर्थात <math>|A| = |B|</math>, बी भी इष्टतम है.
मान लीजिए <math>S = \{1, 2, \ldots , n\}</math>समाप्ति समय के अनुसार गतिविधियों का समूह है। मान लें कि <math>A\subseteq S</math> इष्टतम समाधान है, जिसे समापन समय के अनुसार भी क्रमबद्ध किया गया है; और ''A'' में पहली गतिविधि का सूचकांक <math>k\neq 1</math> है, यानी, यह इष्टतम समाधान ग्रीडी विकल्प से प्रारम्भ नहीं होता है। हम दिखाएंगे कि <math>B = (A \setminus \{k\}) \cup \{1\}</math>, जो ग्रीडी विकल्प (गतिविधि 1) से प्रारम्भ होता है, एक और इष्टतम समाधान है। चूँकि <math>f_1 \leq f_k</math>, और ''A'' में गतिविधियाँ परिभाषा के अनुसार असंयुक्त हैं, ''B'' में गतिविधियाँ भी असंयुक्त हैं। चूँकि ''B'' में ''A'' के समान ही गतिविधियाँ हैं, अर्थात <math>|A| = |B|</math>, ''B'' भी इष्टतम है।


एक बार जब ग्रीडी विकल्प चुन लिया जाता है, तो समस्या उप-समस्या के लिए इष्टतम समाधान खोजने तक सीमित हो जाती है। यदि ग्रीडी विकल्प वाली मूल समस्या एस का इष्टतम समाधान है, तो <math>A^\prime = A \setminus \{1\}</math> गतिविधि-चयन समस्या का एक इष्टतम समाधान है <math>S' = \{i \in S: s_i \geq f_1\}</math>.
एक बार जब ग्रीडी विकल्प चुन लिया जाता है, तो समस्या उप-समस्या के लिए इष्टतम समाधान खोजने तक सिमट कर रह जाती है। यदि ''A'', ग्रीडी विकल्प वाली मूल समस्या ''S'' का इष्टतम समाधान है, तो <math>A^\prime = A \setminus \{1\}</math> गतिविधि-चयन समस्या <math>S' = \{i \in S: s_i \geq f_1\}</math>का इष्टतम समाधान है।


क्यों? यदि ऐसा नहीं होता, तो A' से अधिक गतिविधियों वाला एक समाधान B' से S' चुनें, जिसमें S' के लिए ग्रीडी विकल्प शामिल हो। फिर, B' में 1 जोड़ने से इष्टतमता के विपरीत, A से अधिक गतिविधियों के साथ S से एक व्यवहार्य समाधान B प्राप्त होगा।
क्यों? यदि ऐसा नहीं होता, तो ''A'<nowiki/>'' से अधिक गतिविधियों वाला समाधान ''B'<nowiki/>'' से ''S'<nowiki/>'' चुनें जिसमें ''S''' के लिए ग्रीडी विकल्प हो। फिर, ''B′'' में 1 जोड़ने से इष्टतमता के विपरीत, ''A'' की तुलना में अधिक गतिविधियों के साथ ''S'' से ''S'' का व्यवहार्य समाधान प्राप्त होगा।


===भारित गतिविधि चयन समस्या===
===भारित गतिविधि चयन समस्या===
गतिविधि चयन समस्या के सामान्यीकृत संस्करण में गैर-अतिव्यापी गतिविधियों का एक इष्टतम सेट चुनना शामिल है ताकि कुल वजन अधिकतम हो। भार रहित संस्करण के विपरीत, भारित गतिविधि चयन समस्या का कोई ग्रीडी समाधान नहीं है। हालाँकि, निम्नलिखित दृष्टिकोण का उपयोग करके एक [[गतिशील प्रोग्रामिंग]] समाधान आसानी से बनाया जा सकता है:<ref>[http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf Dynamic Programming with introduction to Weighted Activity Selection]</ref>
गतिविधि चयन समस्या के सामान्यीकृत संस्करण में गैर-अतिव्यापी गतिविधियों के इष्टतम सेट का चयन करना सम्मिलित है ताकि कुल वजन अधिकतम हो। बिना भारित संस्करण के विपरीत, भारित गतिविधि चयन समस्या का कोई लालची समाधान नहीं है। हालाँकि, डायनामिक प्रोग्रामिंग समाधान निम्नलिखित दृष्टिकोण का उपयोग करके आसानी से बनाया जा सकता है:<ref>[http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf Dynamic Programming with introduction to Weighted Activity Selection]</ref>
गतिविधि युक्त एक इष्टतम समाधान पर विचार करें {{mvar|k}}. अब हमारे पास बायीं और दायीं ओर गैर-अतिव्यापी गतिविधियाँ हैं {{mvar|k}}. इष्टतम उप-संरचना के कारण हम इन दो सेटों के लिए पुनरावर्ती समाधान ढूंढ सकते हैं। जैसा कि हम नहीं जानते {{mvar|k}}, हम प्रत्येक गतिविधि को आज़मा सकते हैं। यह दृष्टिकोण एक की ओर ले जाता है <math>O(n^3)</math> समाधान। गतिविधियों के प्रत्येक सेट के लिए इसे ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है <math>(i, j)</math>यदि हमें इसका समाधान पता होता तो हम इष्टतम समाधान पा सकते हैं <math>(i, t)</math>, कहाँ {{mvar|t}} अंतिम गैर-अतिव्यापी अंतराल है {{mvar|j}} में <math>(i, j)</math>. इससे एक प्राप्त होता है <math>O(n^2)</math> समाधान। इस तथ्य को ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है कि हमें सभी श्रेणियों पर विचार करने की आवश्यकता नहीं है <math>(i, j)</math> लेकिन इसके बजाय बस <math>(1, j)</math>. इस प्रकार निम्नलिखित एल्गोरिदम एक परिणाम देता है <math>O(n \log n)</math> समाधान:


<सिंटैक्सहाइलाइट लैंग= सी लाइन= 1 >
गतिविधि {{mvar|k}} वाले इष्टतम समाधान पर विचार करें। अब हमारे पास {{mvar|k}} के बायीं और दायीं ओर गैर-अतिव्यापी गतिविधियां हैं। इष्टतम उप-संरचना के कारण हम इन दोनों सेटों के लिए पुनरावर्ती रूप से समाधान ढूंढ सकते हैं। चूँकि हमें {{mvar|k}} पता नहीं है, हम प्रत्येक गतिविधि को आज़मा सकते हैं। यह दृष्टिकोण <math>O(n^3)</math> समाधान की ओर ले जाता है। इसे इस बात पर विचार करते हुए और अधिक अनुकूलित किया जा सकता है कि <math>(i, j)</math> में गतिविधियों के प्रत्येक सेट के लिए, हम इष्टतम समाधान पा सकते हैं यदि हमें <math>(i, t)</math> का समाधान पता था, जहां {{mvar|t}}, {{mvar|j}} के साथ अंतिम गैर-अतिव्यापी अंतराल है <math>(i, j)</math> इससे <math>O(n^2)</math> समाधान प्राप्त होता है. इस तथ्य को ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है कि हमें सभी श्रेणियों <math>(i, j)</math> पर विचार करने की आवश्यकता नहीं है, बल्कि इसके बजाय केवल <math>(1, j)</math> पर विचार करना है। इस प्रकार निम्नलिखित एल्गोरिथ्म l<math>O(n \log n)</math> समाधान उत्पन्न करता है:<syntaxhighlight lang="c++">
भारित-गतिविधि-चयन(एस): // एस = गतिविधियों की सूची
Weighted-Activity-Selection(S): // S = list of activities


     समाप्ति समय के अनुसार S को क्रमबद्ध करें
     sort S by finish time
     opt[0] = 0 // opt[j] S[1,2..,j] के लिए इष्टतम समाधान (चयनित गतिविधियों के भार का योग) का प्रतिनिधित्व करता है
     opt[0] = 0 // opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j]
    
    
     i = 1 से n के लिए:
     for i = 1 to n:
         t = समाप्ति समय के साथ गतिविधि खोजने के लिए बाइनरी खोज <= i के लिए प्रारंभ समय
         t = binary search to find activity with finish time <= start time for i
             // यदि ऐसी एक से अधिक गतिविधियाँ हैं, तो अंतिम समाप्ति समय वाली एक को चुनें
             // if there are more than one such activities, choose the one with last finish time
         ऑप्ट[i] = MAX(ऑप्ट[i-1], ऑप्ट[t] + w(i))
         opt[i] = MAX(opt[i-1], opt[t] + w(i))
          
          
     वापसी विकल्प[n]
     return opt[n]
</सिंटैक्सहाइलाइट>
</syntaxhighlight>


==संदर्भ==
==संदर्भ==
{{Reflist}}
{{Reflist}}
==बाहरी संबंध==
==बाहरी संबंध==
* [http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm Activity Selection Problem]
* [http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm Activity Selection Problem]
[[Category: इष्टतम शेड्यूलिंग]] [[Category: प्रमाण युक्त लेख]]


[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:इष्टतम शेड्यूलिंग]]
[[Category:प्रमाण युक्त लेख]]

Latest revision as of 17:02, 21 August 2023

गतिविधि चयन समस्या एक संयुक्त अनुकूलन समस्या है जो एक निश्चित समय सीमा के भीतर प्रदर्शन करने के लिए गैर-परस्पर विरोधी गतिविधियों के चयन से संबंधित है, जिसमें प्रत्येक गतिविधि को प्रारंभ समय (si) और समाप्ति समय (fi) द्वारा चिह्नित किया जाता है। समस्या यह है कि एक व्यक्ति या मशीन द्वारा की जा सकने वाली अधिकतम गतिविधियों का चयन किया जाए, यह मानते हुए कि व्यक्ति एक समय में केवल एक ही गतिविधि पर काम कर सकता है। गतिविधि चयन समस्या को अंतराल शेड्यूलिंग अधिकतमीकरण समस्या (आईएसएमपी) के रूप में भी जाना जाता है, जो कि अधिक सामान्य अंतराल शेड्यूलिंग समस्या का एक विशेष प्रकार है।

इस समस्या का उत्कृष्ट अनुप्रयोग कई प्रतिस्पर्धी घटनाओं के लिए कमरे को शेड्यूल करना है, जिनमें से प्रत्येक की अपनी समय की आवश्यकताएं (प्रारंभ और समाप्ति समय) होती हैं, और संचालन अनुसंधान के ढांचे के भीतर कई अन्य चीजें उत्पन्न होती हैं।

औपचारिक परिभाषा

मान लीजिए कि जहां n गतिविधियाँ उपस्थित हैं, जिनमें से प्रत्येक को प्रारंभ समय si और समाप्ति समय fi द्वारा दर्शाया गया है। यदि sifj या sjfi हो तो दो गतिविधियाँ i और j गैर-विरोधाभासी कहलाती हैं। गतिविधि चयन समस्या में गैर-परस्पर विरोधी गतिविधियों के अधिकतम समाधान सेट (S) को खोजना सम्मिलित है, या अधिक सटीक रूप से कोई समाधान सेट S' उपस्थित नहीं होना चाहिए जैसे कि |S'| > |S| उस स्थिति में जब एकाधिक अधिकतम समाधानों का आकार समान होता है।

इष्टतम समाधान

गतिविधि चयन समस्या इस मायने में उल्लेखनीय है कि समाधान खोजने के लिए ग्रीडी एल्गोरिथ्म का उपयोग करने से हमेशा इष्टतम समाधान मिलेगा। एल्गोरिदम के पुनरावृत्त संस्करण का छद्मकोड स्केच और इसके परिणाम की इष्टतमता का प्रमाण नीचे सम्मिलित है।

एल्गोरिदम

Greedy-Iterative-Activity-Selector(A, s, f): 

    Sort A by finish times stored in f
    S = {A[1]} 
    k = 1
    
    n = A.length
    
    for i = 2 to n:
        if s[i]  f[k]: 
            S = S U {A[i]}
            k = i
    
    return S

स्पष्टीकरण

लाइन 1: इस एल्गोरिदम को ग्रीडी-पुनरावृत्ति-गतिविधि-चयनकर्ता कहा जाता है, क्योंकि यह सबसे पहले ग्रीडी एल्गोरिथ्म है, और फिर यह पुनरावृत्त है। इस ग्रीडी एल्गोरिदम का एक पुनरावर्ती संस्करण भी है।

  • गतिविधियों से युक्त एक ऐरे है।
  • एक ऐरे है जिसमें गतिविधियों के प्रारंभ समय सम्मिलित हैं।
  • एक ऐरे है जिसमें गतिविधियों के समापन समय सम्मिलित हैं।

ध्यान दें कि इन ऐरे को 1 से प्रारम्भ करके संबंधित ऐरे की लंबाई तक अनुक्रमित किया जाता है।

लाइन 3: ऐरे में संग्रहीत समाप्ति समय का उपयोग करके गतिविधियों की ऐरे को समापन समय के बढ़ते क्रम में क्रमबद्ध करें। उदाहरण के लिए मर्ज सॉर्ट, हीप सॉर्ट, या क्विक सॉर्ट एल्गोरिदम का उपयोग करके यह ऑपरेशन समय में किया जा सकता है।

लाइन 4: सेट बनाएं चयनित गतिविधियों को संग्रहीत करने के लिए, और इसे गतिविधि के साथ प्रारंभ करने के लिए जिसका जल्द से जल्द खत्म होने का समय है।

लाइन 5: वेरिएबल बनाता है जो अंतिम चयनित गतिविधि के सूचकांक का ट्रैक रखता है।

लाइन 9: उस सरणी के दूसरे एलिमेंट से उसके अंतिम एलिमेंट तक पुनरावृति प्रारम्भ करता है।

लाइन 10,11: यदि गतिविधि का प्रारंभ समय अंतिम चयनित गतिविधि के समापन समय से अधिक या बराबर है, तब सेट में चयनित गतिविधियों के अनुकूल है, और इस प्रकार इसे में जोड़ा जा सकता है।

लाइन 12: अंतिम चयनित गतिविधि का सूचकांक अभी जोड़ी गई गतिविधि में अद्यतन किया जाता है।

इष्टतमता का प्रमाण

मान लीजिए समाप्ति समय के अनुसार गतिविधियों का समूह है। मान लें कि इष्टतम समाधान है, जिसे समापन समय के अनुसार भी क्रमबद्ध किया गया है; और A में पहली गतिविधि का सूचकांक है, यानी, यह इष्टतम समाधान ग्रीडी विकल्प से प्रारम्भ नहीं होता है। हम दिखाएंगे कि , जो ग्रीडी विकल्प (गतिविधि 1) से प्रारम्भ होता है, एक और इष्टतम समाधान है। चूँकि , और A में गतिविधियाँ परिभाषा के अनुसार असंयुक्त हैं, B में गतिविधियाँ भी असंयुक्त हैं। चूँकि B में A के समान ही गतिविधियाँ हैं, अर्थात , B भी इष्टतम है।

एक बार जब ग्रीडी विकल्प चुन लिया जाता है, तो समस्या उप-समस्या के लिए इष्टतम समाधान खोजने तक सिमट कर रह जाती है। यदि A, ग्रीडी विकल्प वाली मूल समस्या S का इष्टतम समाधान है, तो गतिविधि-चयन समस्या का इष्टतम समाधान है।

क्यों? यदि ऐसा नहीं होता, तो A' से अधिक गतिविधियों वाला समाधान B' से S' चुनें जिसमें S' के लिए ग्रीडी विकल्प हो। फिर, B′ में 1 जोड़ने से इष्टतमता के विपरीत, A की तुलना में अधिक गतिविधियों के साथ S से S का व्यवहार्य समाधान प्राप्त होगा।

भारित गतिविधि चयन समस्या

गतिविधि चयन समस्या के सामान्यीकृत संस्करण में गैर-अतिव्यापी गतिविधियों के इष्टतम सेट का चयन करना सम्मिलित है ताकि कुल वजन अधिकतम हो। बिना भारित संस्करण के विपरीत, भारित गतिविधि चयन समस्या का कोई लालची समाधान नहीं है। हालाँकि, डायनामिक प्रोग्रामिंग समाधान निम्नलिखित दृष्टिकोण का उपयोग करके आसानी से बनाया जा सकता है:[1]

गतिविधि k वाले इष्टतम समाधान पर विचार करें। अब हमारे पास k के बायीं और दायीं ओर गैर-अतिव्यापी गतिविधियां हैं। इष्टतम उप-संरचना के कारण हम इन दोनों सेटों के लिए पुनरावर्ती रूप से समाधान ढूंढ सकते हैं। चूँकि हमें k पता नहीं है, हम प्रत्येक गतिविधि को आज़मा सकते हैं। यह दृष्टिकोण समाधान की ओर ले जाता है। इसे इस बात पर विचार करते हुए और अधिक अनुकूलित किया जा सकता है कि में गतिविधियों के प्रत्येक सेट के लिए, हम इष्टतम समाधान पा सकते हैं यदि हमें का समाधान पता था, जहां t, j के साथ अंतिम गैर-अतिव्यापी अंतराल है इससे समाधान प्राप्त होता है. इस तथ्य को ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है कि हमें सभी श्रेणियों पर विचार करने की आवश्यकता नहीं है, बल्कि इसके बजाय केवल पर विचार करना है। इस प्रकार निम्नलिखित एल्गोरिथ्म l समाधान उत्पन्न करता है:

Weighted-Activity-Selection(S):  // S = list of activities

    sort S by finish time
    opt[0] = 0  // opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j]
   
    for i = 1 to n:
        t = binary search to find activity with finish time <= start time for i
            // if there are more than one such activities, choose the one with last finish time
        opt[i] = MAX(opt[i-1], opt[t] + w(i))
        
    return opt[n]

संदर्भ

बाहरी संबंध