गतिविधि चयन समस्या के लिए सी कार्यक्रम

गतिविधि चयन समस्या एक ऐसी समस्या है जिसमें हमें गतिविधियों का एक सेट दिया जाता है जिसमें उनके प्रारंभ और समाप्ति समय होते हैं। और हमें उन सभी गतिविधियों को खोजने की जरूरत है जो एक व्यक्ति एक समय में एक ही गतिविधि को निष्पादित कर सकता है।

इस समस्या में अगली गतिविधि का चयन करने के लिए लालची एल्गोरिथ्म नियुक्त किया जाता है जिसे किया जाना है। आइए सबसे पहले लालची एल्गोरिथम को समझते हैं ।

लालची एल्गोरिथम एक एल्गोरिथम है जो चरण दर चरण समाधान ढूंढकर किसी समस्या का समाधान खोजने का प्रयास करता है। अगले चरण का चयन करने के लिए, एल्गोरिथम ने उस चरण का भी चयन किया जो सबसे अधिक आशाजनक प्रतीत होता है अर्थात आराम की तुलना में तुरंत अनुकूलित समाधान की ओर ले जा सकता है। लालची एल्गोरिथम का उपयोग अनुकूलन समस्याओं को हल करने के लिए किया जाता है क्योंकि यह अगले मध्यवर्ती चरण के लिए सबसे अनुकूलित समाधान खोजने की कोशिश करता है जिससे पूरी समस्या का इष्टतम समाधान हो सके।

यद्यपि लालची एल्गोरिदम एक अच्छा समाधान है लेकिन कुछ समस्याएं हैं जिनके साथ इसे लागू नहीं किया जा सकता है। उदाहरण के लिए, 0-1 knapsack को लालची एल्गोरिथम का उपयोग करके हल नहीं किया जा सकता है।

एल्गोरिदम

कुछ मानक लालची एल्गोरिथम है -

1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding

निष्क्रियता चयन समस्या, हमें प्रारंभ और समाप्ति समय के साथ n समस्याएं दी गई हैं। और हमें किसी व्यक्ति द्वारा की जा सकने वाली गतिविधियों की अधिकतम संख्या का चयन करने की आवश्यकता है, यह देखते हुए कि वह एक समय में एक ही गतिविधि कर सकता है।

3 गतिविधियाँ हैं जिन्हें उनके अंतिम समय के क्रम में क्रमबद्ध किया जाता है,

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