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

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

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

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

मान लीजिए कि वहाँ n गतिविधियाँ मौजूद हैं, जिनमें से प्रत्येक को प्रारंभ समय s_i और समाप्ति समय f_i द्वारा दर्शाया गया है। यदि s_i ≥ f_j या s_j ≥ f_i हो तो दो गतिविधियाँ 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: इस एल्गोरिदम को ग्रीडी-पुनरावृत्ति-गतिविधि-चयनकर्ता कहा जाता है, क्योंकि यह सबसे पहले एक ग्रीडी एल्गोरिथ्म है, और फिर यह पुनरावृत्त है। इस ग्रीडी एल्गोरिदम का एक पुनरावर्ती संस्करण भी है।

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

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

लाइन 3: ऐरे $f$ में संग्रहीत समाप्ति समय का उपयोग करके गतिविधियों की ऐरे $A$ को समापन समय के बढ़ते क्रम में क्रमबद्ध करें। उदाहरण के लिए मर्ज सॉर्ट, हीप सॉर्ट, या क्विक सॉर्ट एल्गोरिदम का उपयोग करके यह ऑपरेशन $O(n\cdot \log n)$ समय में किया जा सकता है।

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

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

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

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

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

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

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

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

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

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

गतिविधि चयन समस्या के सामान्यीकृत संस्करण में गैर-अतिव्यापी गतिविधियों का एक इष्टतम सेट चुनना शामिल है ताकि कुल वजन अधिकतम हो। भार रहित संस्करण के विपरीत, भारित गतिविधि चयन समस्या का कोई ग्रीडी समाधान नहीं है। हालाँकि, निम्नलिखित दृष्टिकोण का उपयोग करके एक गतिशील प्रोग्रामिंग समाधान आसानी से बनाया जा सकता है: गतिविधि युक्त एक इष्टतम समाधान पर विचार करें k. अब हमारे पास बायीं और दायीं ओर गैर-अतिव्यापी गतिविधियाँ हैं k. इष्टतम उप-संरचना के कारण हम इन दो सेटों के लिए पुनरावर्ती समाधान ढूंढ सकते हैं। जैसा कि हम नहीं जानते k, हम प्रत्येक गतिविधि को आज़मा सकते हैं। यह दृष्टिकोण एक की ओर ले जाता है $O(n^{3})$ समाधान। गतिविधियों के प्रत्येक सेट के लिए इसे ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है $(i,j)$यदि हमें इसका समाधान पता होता तो हम इष्टतम समाधान पा सकते हैं $(i,t)$, कहाँ t अंतिम गैर-अतिव्यापी अंतराल है j में $(i,j)$. इससे एक प्राप्त होता है $O(n^{2})$ समाधान। इस तथ्य को ध्यान में रखते हुए इसे और अधिक अनुकूलित किया जा सकता है कि हमें सभी श्रेणियों पर विचार करने की आवश्यकता नहीं है $(i,j)$ लेकिन इसके बजाय बस $(1,j)$. इस प्रकार निम्नलिखित एल्गोरिदम एक परिणाम देता है $O(n\log n)$ समाधान:

<सिंटैक्सहाइलाइट लैंग= सी लाइन= 1 > भारित-गतिविधि-चयन(एस): // एस = गतिविधियों की सूची

   समाप्ति समय के अनुसार S को क्रमबद्ध करें
   opt[0] = 0 // opt[j] S[1,2..,j] के लिए इष्टतम समाधान (चयनित गतिविधियों के भार का योग) का प्रतिनिधित्व करता है
  
   i = 1 से n के लिए:
       t = समाप्ति समय के साथ गतिविधि खोजने के लिए बाइनरी खोज <= i के लिए प्रारंभ समय
           // यदि ऐसी एक से अधिक गतिविधियाँ हैं, तो अंतिम समाप्ति समय वाली एक को चुनें
       ऑप्ट[i] = MAX(ऑप्ट[i-1], ऑप्ट[t] + w(i))
       
   वापसी विकल्प[n]

</सिंटैक्सहाइलाइट>

बाहरी संबंध

• Activity Selection Problem