एक्टिविटी सिलेक्शन प्रॉब्लम एक ऐसी समस्या है जिसमें हमें गतिविधियों का एक सेट दिया जाता है जिसमें उनके प्रारंभ और समाप्ति समय होते हैं। और हमें उन सभी गतिविधियों को ढूंढना होता है जो एक व्यक्ति एक समय में एक गतिविधि करके कर सकता है।
इस समस्या में अगली गतिविधि का चयन करने के लिए लालची एल्गोरिदम (Greedy Algorithm) नियुक्त किया जाता है। आइए पहले लालची एल्गोरिदम को समझते हैं।
लालची एल्गोरिदम एक ऐसा एल्गोरिदम है जो चरण दर चरण समाधान ढूंढकर किसी समस्या का समाधान खोजने का प्रयास करता है। अगले चरण का चयन करने के लिए, एल्गोरिदम उस चरण का चयन भी करता है जो सबसे आशाजनक लगता है यानी बाकी की तुलना में तुरंत अनुकूलित समाधान की ओर ले जा सकता है। लालची एल्गोरिदम का उपयोग अनुकूलन समस्याओं को हल करने के लिए किया जाता है क्योंकि यह पूरे समस्या के इष्टतम समाधान की ओर ले जाने वाले अगले मध्यवर्ती चरण के लिए सबसे अनुकूलित समाधान खोजने का प्रयास करता है।
हालांकि लालची एल्गोरिदम एक अच्छा समाधान है लेकिन कुछ समस्याएं हैं जिनके साथ इसे लागू नहीं किया जा सकता। उदाहरण के लिए, 0-1 नैपसैक को लालची एल्गोरिदम का उपयोग करके हल नहीं किया जा सकता।
एल्गोरिदम
कुछ मानक लालची एल्गोरिदम हैं -
1) डिज्क्स्ट्रा का सबसे छोटा पथ
2) न्यूनतम स्पैनिंग ट्री (MST) {प्रिम का और क्रुस्कल का}
3) हफमैन कोडिंग
एक्टिविटी सिलेक्शन प्रॉब्लम में, हमें n समस्याएं दी जाती हैं जिनके प्रारंभ और समाप्ति समय होते हैं। और हमें उन अधिकतम गतिविधियों का चयन करना होता है जिन्हें एक व्यक्ति द्वारा किया जा सकता है, यह देखते हुए कि वह एक समय में एक ही गतिविधि कर सकता है।
तीन गतिविधियाँ हैं जो उनके समाप्ति समय के क्रम में क्रमबद्ध हैं,
Start = [1, 5, 12] End = [10, 13, 23]
यहां, व्यक्ति अधिकतम दो गतिविधियाँ कर सकेगा। निष्पादित की जा सकने वाली गतिविधियाँ [0, 2] हैं।
उदाहरण
#include <stdio.h>
int main() {
int start[] = {1, 5, 12};
int finish[] = {10, 13, 23};
int activities = sizeof(start) / sizeof(start[0]);
int i, j;
printf("Following activities are selected \t");
i = 0;
printf("%d\t", i);
for (j = 1; j < activities; j++) {
if (start[j] >= finish[i]) {
printf("%d ", j);
i = j;
}
}
return 0;
}
आउटपुट
Following activities are selected 0 2
