Greedy Algorithm
গ্রিডি অ্যালগরিদম
প্রতিটা ধাপে locally সবচেয়ে লাভজনক পছন্দটা নিয়ে আর পিছনে না তাকানো strategy — greedy choice property থাকলে global optimum-ও মেলে।
also: greedy, greedy choice
সবসময় optimal নয়; coin change-এই পার্থক্য দেখা যায়:
coins {25, 10, 5, 1}, amount 30: greedy 25+5 ✓ optimal
coins {4, 3, 1} , amount 6 : greedy 4+1+1 (৩) ✗ 3+3 (২)Provable-optimal ক্লাসিক: MST-র Kruskal/Prim (cut property), Huffman coding, activity selection (earliest finish first), fractional knapsack।
Greedy ব্যর্থ হলে প্রায়ই DP উত্তর দেয় — exchange হলো speed বনাম optimality guarantee। Greedy choice property (একটা পছন্দ নিরাপদে ফিক্স করা যায়) আর optimal substructure prove করতে পারলেই greedy নিরাপদ।