একটি গ্রিডি অ্যালগরিদম প্রতিটি ধাপে স্থানীয়ভাবে সর্বোত্তম পছন্দ করে, এটি বিশ্বব্যাপী সর্বোত্তমতার দিকে নিয়ে যাওয়ার আশা করে। এটি সহজ এবং দ্রুত, কিন্তু শুধুমাত্র তখনই সঠিক যখন সমস্যাটির গ্রিডি-চয়েস সম্পত্তি এবং সর্বোত্তম সাবস্ট্রাকচার রয়েছে।
অতীতের পছন্দগুলি পুনর্বিবেচনা করবেন না — সেরা তাৎক্ষণিক বিকল্পে প্রতিশ্রুতিবদ্ধ হন এবং এগিয়ে যান।
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
এটি US কয়েনের জন্য সর্বোত্তম, কিন্তু {1, 3, 4} এর মতো সেটের জন্য ব্যর্থ হয় যেখানে গ্রিডি 6 এর জন্য 4+1+1 দেয় 3+3 এর পরিবর্তে।
যা কাজ করে তার উদাহরণ: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
সাধারণত দ্রুত — প্রায়শই সর্টিংয়ের পরে O(n log n)।
গ্রিডি সর্বদা সঠিক নয়। গ্রিডি-চয়েস সম্পত্তি প্রমাণ করুন বা এটিতে বিশ্বাস করার আগে একটি brute-force/DP বেসলাইনের বিরুদ্ধে পরীক্ষা করুন।
যখন গ্রিডি প্রযোজ্য, এটি DP বা brute force এর চেয়ে অনেক বেশি সহজ এবং দ্রুত।
কখন এটি বৈধ — এবং কখন এটি চুপচাপ ভুল উত্তর দেয় — জানা হল অ্যালগরিদমিক পরিপক্বতার একটি চিহ্ন।
অনেক মূল গ্রাফ অ্যালগরিদম তাদের মূলে গ্রিডি।
বিস্তারিত উত্তরসহ IT ইন্টারভিউ প্রশ্নের একটি লাইব্রেরি — জুনিয়র থেকে সিনিয়র পর্যন্ত।
দান করুন