অ্যাক্টিভিটি সিলেকশন প্রোব্লেম (Activity Selection Problem) হল এমন একটি সমস্যা যেখানে আমাদের কিছু অ্যাক্টিভিটি দেওয়া থাকে তাদের স্টার্টিং (starting) এবং ফিনিশিং (finishing) টাইমসহ। এবং আমাদের সেই সব অ্যাক্টিভিটি খুঁজে বের করতে হবে যা একজন ব্যক্তি একবারে একটি অ্যাক্টিভিটি করেই সম্পাদন করতে পারে।
এই সমস্যাটি সমাধান করতে গ্রিডি অ্যালগরিদম (Greedy Algorithm) নিয়োগ করা হয় যাতে পরবর্তী কোন অ্যাক্টিভিটি করা উচিত তা সিলেক্ট করা যায়। প্রথমে গ্রিডি অ্যালগরিদম বুঝে নেই।
গ্রিডি অ্যালগরيدম (Greedy Algorithm) হল এমন একটি অ্যালগরিদম যা ধাপে ধাপে সমাধান খুঁজে বের করে একটি সমস্যার সমাধান। পরবর্তী ধাপ সিলেক্ট করার জন্য অ্যালগরিদমটি সেই ধাপটি সিলেক্ট করে যা সবচেয়ে আশাজনক (promising) লাগে, অর্থাৎ অন্যদের তুলনায় সেটি অবিলম্বে অপ্টিমাইজড সমাধানের দিকে নিয়ে যায়। গ্রিডি অ্যালগরিদম অপ্টিমাইজেশন প্রোব্লেম সমাধান করতে ব্যবহৃত হয় কারণ এটি প্রতিটি ইন্টারমিডিয়েট ধাপের জন্য সবচেয়ে অপ্টিমাইজড সমাধান খুঁজে বের করার চেষ্টা করে যা পুরো সমস্যার জন্য অপ্টিমাল সমাধান দেয়।
যদিও গ্রিডি অ্যালগরিদম একটি ভালো সমাধান, কিন্তু কিছু সমস্যা আছে যেগুলোর সাথে এটি প্রয়োগ করা যায় না। উদাহরণস্বরূপ, ০-১ ন্যাপস্যাক (0-1 knapsack) গ্রিডি অ্যালগরিদম দিয়ে সমাধান করা যায় না।
আলগরিদম (Algorithm)
কিছু স্ট্যান্ডার্ড গ্রিডি অ্যালগরিদম:
১) ডিকস্ট্রার শর্টেস্ট পাথ (Dijkstra's Shortest Path)
২) মিনিমাম স্প্যানিং ট্রি (MST) {প্রিমস (Prim's) এবং ক্রাস্কালস (Kruskal's)}
৩) হাফম্যান কোডিং (Huffman coding)
অ্যাক্টিভিটি সিলেকশন প্রোব্লেমে, আমাদের nটি অ্যাক্টিভিটি দেওয়া থাকে তাদের স্টার্টিং এবং ফিনিশিং টাইমসহ। এবং আমাদের Максимаাম সংখ্যক অ্যাক্টিভিটি সিলেক্ট করতে হবে যা একটি ব্যক্তি করাতে পারবেন যদি সে একবারে একটি অ্যাক্টিভিটি করতে পারে।
৩টি অ্যাক্টিভিটি আছে যেগুলো তাদের ফিনিশিং টাইম অনুযায়ী সোর্টেড:
Start = [1, 5, 12] End = [10, 13, 23]
এখানে, ব্যক্তিটি সর্বোচ্চ দুটি অ্যাক্টিভিটি করতে পারবেন। এক্সিকিউট করা যাবে অ্যাক্টিভিটি [0, 2]।
উদাহরণ (C প্রোগ্রাম)
#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: ");
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
ব্যাখ্যা: অ্যাক্টিভিটিগুলো ইতিমধ্যে ফিনিশ টাইম অনুযায়ী সোর্টেড ধরে নেওয়া হয়েছে। প্রথম অ্যাক্টিভিটি (ইন্ডেক্স ০) সবসময় সিলেক্ট হয়। তারপর যেই অ্যাক্টিভিটির স্টার্ট টাইম আগের সিলেক্টেড অ্যাক্টিভিটির ফিনিশ টাইমের চেয়ে বড় বা সমান, সেটি সিলেক্ট করা হয়। এটি অপ্টিমাল সমাধান দেয়।
