Greedy বা লোভী অ্যালগরিদম

greedy অ্যালগরিদম জিনিসটা আসলে কি জানার জন্য স্বাভাবিকভাবেই প্রথমে গুগলে সার্চ করি। কিন্তু উইকিপিডিয়া পেজটা দেখে খুব ঘাবড়ে যাই।
কি না কি সব লেখা। তারপর বাংলায় গ্রিডি নিয়ে লেখা খুঁজি। কিন্তু পাই না। এত কমন একটা জিনিস নিয়ে কেউ লেখেনি কেন বুঝতে পারি না। পরে যখন ঘাটাঘাটি করে greedy জিনিসটা বুঝতে পারি তখন বুঝতে পারি কেন লেখে নি। আসলে জিনিসটা খুব সিম্পল। তাই হয়ত কেউ লেখার প্রয়োজন মনে করে নি। তবে আমি নিজে যা বুঝলাম লিখে রাখলাম।

প্রথমেই আমরা greedy approach এ একটা প্রবলেম সলভ করি তাহলেই বুঝতে সুবিধা হবে।
কয়েন চেঞ্জ বা বাংলায় 'ভাংতি' সমস্যাটা খুব কমন। কেনাকাটার পরে কাউকে ভাংতি দিতে হবে। কারো বিল  আসলো ২২ টাকা। সে একশ টাকার নোট দিল। তাকে ফেরত দিতে হবে ৭৮ টাকা। আমাদের বের করতে সর্বনিম্ন কতটি ছোট নোটে তাকে ভাংতি ফেরত দেয়া যাবে। আমাদের কাছে নোট আছে ৫০,২০,১০,৫,২,১ টাকার (ধরে নেই প্রত্যেকটা নোট আসীম সংখ্যাক আছে।)

তাহলে আমরা প্রথমেই বড় নোট দিয়ে শুরু করব। যেহেতু সর্বনিম্ন সংখ্যক নোট দিয়ে ভাংতি দিতে হবে প্রথমে ৫০ টাকার একটা নোট দেব। তাহলে বাকি থাকে ৩৮ টাকা। তাহলে ৫০ টাকার নোট আর দেয়া যাবে না। এবার তার থেকে ছোটটা মানে ২০ দেব।  এভাবে যতক্ষণ টাকা বাকি থাকবে আমরা নোট দিয়ে যাব।

কোডঃ

এখন দেখুন যখন লোকটাকে ৫০ টাকার নোট  দিয়ে দিলাম তখন সে আর ৩৮ টাকা পায়। প্রবেলেমটা ছোট অংশে ভাগ হয়ে গেল। এখন তাকে আবার ৩৮ টাকা ভাংতি দিতে হবে। এবং এই ছোট অংশটা স্বাধীন। এই ৩৮ টাকা ভাংতি দিতে আর কয়টা নোট লাগবে তা কিন্তু মোট কত ভাংতি দিলাম তার উপর নির্ভর করবে না। তাই আগে যতটা লাগছে তার সাথে যোগ করে দিলেই পেয়ে যাব মোট কয়টা নোট লাগছে।

greedy কোন নির্দিষ্ট অ্যালগরিদম না। এটা একটা টেকনিক বা অ্যাপ্রোচ। এতক্ষণ আমরা যেটা দেখলাম এটাই greedy অ্যাপ্রোচ। এখানে প্রত্যেকটা ছোট  স্টেপে সবচেয়ে ভাল সমাধান নিলেই (লোভীর মত) পুরো সমস্যার সবচেয়ে ভাল সমাধান পাওয়া যাবে। এখন কোন সমস্যাকে যদি এমন ছোট অংশে ভাগ করা যায় যে প্রত্যেক অংশে অন্য অংশের কথা চিন্তা না করে সবচেয়ে ভাল সমাধান নিলেই পুরো সমস্যার সবচেয়ে ভাল সমাধান পাওয়া যায় তাহলেই ওই সমস্যা গ্রিডি অ্যাপ্রোচে সলভ করা যাবে।

এখন এমন একটা সমস্যা দেখি যেটা এইভাবে সলভ করা যাবে না। শাফায়েত ভায়ের ব্লগ থেকে কোট করে দেইঃ

কোনো এক রাতে তুমি চুরি করতে বের হলে!! বন্ধুর বাসায় জানালা দিয়ে ঢুকে দেখলে প্রচুর জিনিসপত্র,কিন্তু তোমার চুরি করার থলেতে জায়গা আছে মাত্র ১০ইউনিট,এর বেশি নিলে থলে ছিড়ে যাবে। প্রতিটা জিনিসের ভর আছে আর একেক জিনিসের মুল্যও একেকরকম।

১. মানিব্যাগ: ১ইউনিট,১২০টাকা

২. কোরম্যানের-বই ভর: ৭ইউনিট,৪০০টাকা

৩. ডিভিডি-কালেকশন ভর: ৪ইউনিট,২৮০ টাকা

৪. ফেলুদা-সমগ্র: ৩ইউনিট,১৫০টাকা

৫. ফুটবল: ভর: ৪ইউনিট,২০০টাকা

কোনো জিনিস নিলে পুরোটাই নিতে হবে,৪টি ডিভিডির ২টি তুমি নিতে পারবেনা,ফেলুদা সমগ্রের অর্ধেক ছিড়ে আনতে পারবেনা। প্রথমদিন চুরি করতে গিয়েছো এই জন্য কিছু না ভেবেই তুমি ফটাফট দামি জিনিসগুলো ভরতে থাকলে। প্রথমেই তুমি ৪০০টাকার কোরম্যানের বই নিয়ে নিলে,তারপর ১৫০টাকার ফেলুদা সমগ্র নিয়ে বাসায় ফিরে আসলে,তোমার লাভ হলো ৫৫০ টাকা।

বাসায় এসে হিসাব করে দেখলে তুমি যদি লোভীর মতো (greedy) দামী জিনিসগুলো আগে না নিয়ে একটু ভেবে-চিন্তে নিতে তাহলে ২৮০টাকার ডিভিডি,২০০টাকার ফুটবল আর ১২০টাকার মানিব্যাগ নিয়ে ফিরতে পারতে,তোমার লাভ হতো ৬০০টাকা।

এখানে প্রত্যেক স্টেপের জন্য সবচেয়ে ভাল সমাধান নিলেই পুরো সমস্যার সবচেয়ে ভাল সমাধান পাওয়া নাও যেতে পারে।

অ্যালগরিদম নিয়ে এইটা আমার প্রথম লেখা। পরামর্শ/মতামত পেলে ভবিষ্যতে লেখার অনুপ্রেরণা পাব। হ্যাপি কোডিং :(