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

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

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

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

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

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

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

पंक्तियाँ 10,11: यदि प्रारंभ समय $s[i]$ की $ith$ गतिविधि ($A[i]$) समाप्ति समय से अधिक या उसके बराबर है $f[k]$ अंतिम चयनित गतिविधि का ($A[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