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

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

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

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

मान लीजिए कि वहाँ 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$ इष्टतम समाधान है, जिसे समापन समय के अनुसार भी क्रमबद्ध किया गया है; और A में पहली गतिविधि का सूचकांक $k\neq 1$ है, यानी, यह इष्टतम समाधान ग्रीडी विकल्प से प्रारम्भ नहीं होता है। हम दिखाएंगे कि $B=(A\setminus \{k\})\cup \{1\}$, जो ग्रीडी विकल्प (गतिविधि 1) से प्रारम्भ होता है, एक और इष्टतम समाधान है। चूँकि $f_{1}\leq f_{k}$, और A में गतिविधियाँ परिभाषा के अनुसार असंयुक्त हैं, B में गतिविधियाँ भी असंयुक्त हैं। चूँकि B में A के समान ही गतिविधियाँ हैं, अर्थात $|A|=|B|$, B भी इष्टतम है।

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

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

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

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

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

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]

बाहरी संबंध

• Activity Selection Problem