গ্রিডি অ্যালগরিদম (Greedy Algorithms) হলো একটি সমস্যা সমাধানের কৌশল যা একটি স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত নিয়ে সমস্যার সমাধান করে। এই অ্যালগরিদমটি প্রতি পদক্ষেপে সর্বাধিক সুবিধা প্রদানকারী অপশন নির্বাচন করে, যাতে সঠিক সমাধান পাওয়া যায়। গ্রিডি অ্যালগরিদম সাধারণত অপ্টিমাইজেশন সমস্যাগুলোর জন্য ব্যবহৃত হয়।
গ্রিডি অ্যালগরিদমের বৈশিষ্ট্য
- স্থানীয়ভাবে সর্বোত্তম নির্বাচন: প্রতিটি পদক্ষেপে সর্বোত্তম সিদ্ধান্ত নেওয়া হয়, যা পরে গ্লোবাল সমাধানে পৌঁছাতে সহায়ক হয়।
- কৌশলগত পদক্ষেপ: আগের সিদ্ধান্তের উপর নির্ভরশীল না হয়ে প্রতিটি পদক্ষেপে সর্বোত্তম নির্বাচন করা হয়।
- সমাধান অবিলম্বে পাওয়া: প্রতিটি পদক্ষেপের পরে সমস্যা সমাধানে দ্রুত পৌঁছানো যায়।
গ্রিডি অ্যালগরিদমের ব্যবহার
গ্রিডি অ্যালগরিদম কিছু গুরুত্বপূর্ণ সমস্যার সমাধানে কার্যকরী, যেমন:
- মিনিমাম স্প্যানিং ট্রি: উদাহরণস্বরূপ, প্রিমস অ্যালগরিদম এবং ক্রুসকলের অ্যালগরিদম।
- হাফিং কোডিং: তথ্য সংকোচনের জন্য ব্যবহৃত হয়।
- কয়েন চেঞ্জ সমস্যা: সর্বনিম্ন সংখ্যক কয়েন ব্যবহার করে একটি নির্দিষ্ট পরিমাণ অর্থ ফেরত দেওয়া।
- নোকিয়া প্যাকেজিং সমস্যা: বিভিন্ন প্যাকেজের জন্য সর্বনিম্ন আকারের প্যাকেজ ব্যবহার করা।
গ্রিডি অ্যালগরিদমের উদাহরণ: কয়েন চেঞ্জ সমস্যা
কয়েন চেঞ্জ সমস্যায়, আমাদের বিভিন্ন মানের কয়েন দেওয়া হয়েছে এবং আমাদের একটি নির্দিষ্ট পরিমাণ ফেরত দিতে হবে। আমাদের লক্ষ্য হল সর্বনিম্ন সংখ্যক কয়েন ব্যবহার করে সেই পরিমাণ ফেরত দেওয়া।
উদাহরণ (Python):
def coin_change(coins, amount):
coins.sort(reverse=True) # কয়েনগুলোকে উল্টো সাজান (বড় থেকে ছোট)
count = 0
result = []
for coin in coins:
while amount >= coin: # যতক্ষণ পরিমাণটি কয়েনের মানের বেশি
amount -= coin # পরিমাণ কমানো
result.append(coin) # কয়েন যুক্ত করা
count += 1
return count, result
# কয়েন মান এবং পরিমাণ
coins = [1, 5, 10, 25]
amount = 63
count, result = coin_change(coins, amount)
print(f"Minimum coins needed: {count}")
print(f"Coins used: {result}")
আউটপুট:
Minimum coins needed: 6
Coins used: [25, 25, 10, 1, 1, 1]
সীমাবদ্ধতা
গ্রিডি অ্যালগরিদম সবসময় সঠিক বা সর্বোত্তম সমাধান দেয় না। এটি কেবল তখন কার্যকরী হয় যখন স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত গ্লোবাল সমাধানে পৌঁছায়। কিছু সমস্যা যেমন 0/1 ন্যাপকিন সমস্যা বা বৃহত্তম স্ট্রিং সমস্যা গ্রিডি অ্যালগরিদম দ্বারা সঠিকভাবে সমাধান করা যায় না।
উপসংহার
গ্রিডি অ্যালগরিদম একটি গুরুত্বপূর্ণ সমস্যা সমাধানের কৌশল, যা স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত নিয়ে দ্রুত সমাধান খুঁজে বের করে। এটি অপ্টিমাইজেশন সমস্যাগুলোর জন্য কার্যকরী, তবে সব সমস্যার জন্য প্রযোজ্য নয়। সঠিকভাবে ব্যবহৃত হলে গ্রিডি অ্যালগরিদম ডেটা কাঠামো এবং অ্যালগরিদম ডিজাইনিংয়ে গুরুত্বপূর্ণ ভূমিকা পালন করে।
