কার্যকলাপ নির্বাচন সমস্যা জন্য সি প্রোগ্রাম

অ্যাক্টিভিটি নির্বাচন সমস্যা হল একটি সমস্যা যেখানে আমাদেরকে তাদের শুরু এবং শেষ করার সময় সহ ক্রিয়াকলাপগুলির একটি সেট দেওয়া হয়৷ এবং আমাদের সেই সমস্ত ক্রিয়াকলাপগুলি খুঁজে বের করতে হবে যা একজন ব্যক্তি একবারে একক কার্যকলাপ সম্পাদন করতে পারে।

লোভী অ্যালগরিদম এই সমস্যায় নিযুক্ত করা হয় পরবর্তী কার্যকলাপ নির্বাচন করতে যা সঞ্চালিত হবে। আসুন প্রথমে লোভী অ্যালগরিদম বুঝতে পারি .

লোভী অ্যালগরিদম একটি অ্যালগরিদম যা ধাপে ধাপে সমাধান খুঁজে বের করে সমস্যার সমাধান খুঁজে বের করার চেষ্টা করে। পরবর্তী ধাপ বাছাই করার জন্য, অ্যালগরিদম সেই ধাপটিকেও বেছে নিয়েছে যা সবচেয়ে প্রতিশ্রুতিশীল বলে মনে হয় অর্থাৎ বিশ্রামের তুলনায় অবিলম্বে অপ্টিমাইজ করা সমাধানের দিকে নিয়ে যেতে পারে। লোভী অ্যালগরিদমটি অপ্টিমাইজেশান সমস্যা সমাধানের জন্য ব্যবহার করা হয় কারণ এটি পরবর্তী মধ্যবর্তী ধাপের জন্য সবচেয়ে অপ্টিমাইজ করা সমাধান খুঁজে বের করার চেষ্টা করে যা পুরো সমস্যার একটি সর্বোত্তম সমাধানের দিকে নিয়ে যায়৷

যদিও লোভী অ্যালগরিদম একটি ভাল সমাধান কিন্তু কিছু সমস্যা আছে যার সাথে এটি প্রয়োগ করা যায় না৷ উদাহরণস্বরূপ, লোভী অ্যালগরিদম ব্যবহার করে 0-1 ন্যাপস্যাক সমাধান করা যাবে না৷

অ্যালগরিদম

কিছু স্ট্যান্ডার্ড লোভী অ্যালগরিদম হল −

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