Introduction

আমরা এতদিন যাবত যে সকল অ্যালগরিদম নিয়ে আলোচনা করেছিলাম, প্রতিটাই অপটিমাল সল্যুশন এর জন্য ডিজাইন করা। এসব অ্যালগরিদমের উদ্দেশ্যই ছিল সবচাইতে অপটিমাল সল্যুশন বের করা। কিন্তু এমন অনেক সিচুয়েশন আসবে যখন আমরা পুরো প্রব্লেমের সমস্ত স্টেপ শেষ হওয়ার পর কি সল্যুশন আসবে সেটার জন্য বসে থাকতে পারবো না। আমাদের আপাতদৃষ্টিতে বেস্ট চয়েসটা নিতে হবে। সেই বেস্ট চয়েসটা হয়তো অপটিমাল নাও হতে পারে। আবার হতেও পারে। যে অ্যালগরিদম আমাদের এই কাজ করতে সাহায্য করে তার নাম Greedy Algorithms। যখনই আমাদের গ্রিডি অ্যালগরিদম একটা সল্যুশন খুঁজে পাবে, তখন আমাদের নির্ধারণ করতে হবে এটা অপটিমাল সল্যুশন কিনা। আমরা এবার কিছু প্রব্লেম দেখবো যেগুলো গ্রিডি অ্যালগরিদম দ্বারা সলভ করা যায়।

Change Making Problem

Greedy algorithm এর কনসেপ্ট বুঝার জন্য আমরা ক্যাশিয়ারস অ্যালগরিদম বেছে নিলাম। এটা Change making problem এর জন্য ব্যবহার করা হয়। ধরেন আপনি একটা দোকানের মালিক। কাস্টমার আপনার কাছে জিনিস কিনতে আসলো। সে ২৩ টাকার জিনিস কিনলো। আপনাকে ১০০ টাকা দিলো। এখন আপনি তাকে বাকি ৭৭ টাকা ফেরত দেয়ার জন্য একটা ৫০ টাকার নোট, ১টা ২০ টাকার নোট, ১টা ৫ টাকার নোট এবং ১টা দুই টাকার নোট দিলেন। অর্থাৎ প্রথমে সবচেয়ে বড় নোট দিইয়ে শুরু করে পর্যায়ক্রমে কমতে কমতে সবচেয়ে কম নোট ব্যবহার করে আপনি তাকে তার বাকি টাকা ফেরত দিলেন। এটা হলো অপটিমাল সল্যুশন। এখন ধরেন আপনার কাছে ৫০ টাকার নোট নেই। ২০ টাকার নোটও নেই। কিন্তু ১০ টাকার নোট আছে অনেক। তখন আপনাকে ৭টা ১০ টাকার নোট, ১টা ৫ টাকার নোট এবং ১টা ২ টাকার নোট দিয়ে তার টাকা ফেরত দেয়া লাগবে। সেক্ষেত্রে আপনার মোট নোটের সংখ্যা হবে ৯টা। এবং এটাই ঐ মুহূর্তের জন্য অপটিমাল সল্যুশন। অর্থাৎ আমাদের কিভাবে সল্যুশন সবচাইতে অপটিমাল হবে সেদিকে নজর না দিয়ে যা আছে তাই দিয়েই অপটিমাল সল্যুশন বের করে নিতে হবে। যদি আমরা অপটিমাল সল্যুশনের জন্য অপেক্ষা করতাম, কাস্টমার রেগেমেগে তুলকালাম করে দিতো। তাই অনেক সময় অপটিমাল সল্যুশন না পেলেও টাইম লিমিটের কারণে বর্তমান সল্যুশনটাকেই অপটিমাল বলে ধরে নেয়া হয়। আমরা এই অ্যালগরিদমের সুডোকোডটা লিখে ফেলি।

procedure change(c1, c2,… , cr: values of denominations of coins, where
    c1 > c2 > ⋯ > cr; n: a positive integer)
for i := 1 to r
    di := 0 {di counts the coins of denomination ci used}
    while n ≥ ci
        di := di + 1 {add a coin of denomination ci}
        n := n − ci
{di is the number of coins of denomination ci in the change for i = 1, 2, … , r}

Activity Selection Problem

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

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

Criteria - 01 (Sorted by earliest starting time)

আমাদের সেমিনারগুলো শিডিউল নিম্নরূপঃ

• ১ম সেমিনার শুরু হবে সকাল ৮টায়, শেষ হবে দুপুর ১২টায়।
• ২য় সেমিনার শুরু হবে সকাল ৯টায়, শেষ হবে সকাল ১০টায়।
• ৩য় সেমিনার শুরু হবে সকাল ১১টায়, শেষ হবে দুপুর ১২টায়।

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

Criteria - 02 (Sorted by shortest length)

এবার ধরি আমাদের সেমিনারের শিডিউল নিচের মতো -

• ১ম সেমিনার শুরু হবে সকাল ৮টায়, শেষ হবে সোয়া ৯টায়।
• ২য় সেমিনার শুরু হবে সকাল ৯টায়, শেষ হবে ১০টায়।
• ৩য় সেমিনার শুরু হবে সকাল পৌনে ১০টায়, শেষ হবে ১১টায়।

এবার যদি আমরা সবচেয়ে কম দৈর্ঘ্যের সেমিনার সিলেক্ট করি তাহলে দেখবো ২য় সেমিনার সবচেয়ে কম দৈর্ঘ্যের। কিন্তু এটাও অপটিমাল না। কারণ ২য় সেমিনার সিলেক্ট করলে আমরা আর কোনো সেমিনারে অ্যাটেন্ড করতে পারবো না। কিন্তু ২য় সেমিনার সিলেক্ট না করে আমরা ১ম ও ৩য় সেমিনার সিলেক্ট করতে পারতাম। সেক্ষেত্রে কোনো ওভারল্যাপিং ছাড়া আমরা ২টা সেমিনারে অ্যাটেন্ড করতে পারতাম।

Criteria - 03 (Sorted by earliest ending time)

ক্রাইটেরিয়া ২ এর সেমিনার শিডিউল অনুযায়ী যদি আমরা সবচেয়ে আগে যেটা শেষ হবে সেটা সিলেক্ট করি তবে দেখবো সবচেয়ে আগে শেষ হচ্ছে ১ম সেমিনার। এরপরের সেমিনার শেষ হবে ১০ টায়, কিন্তু সেটা শুরু হবে ৯টায় সুতরাং সেটাতে অ্যাটেন্ড করা যাবে না। এরপরেরটা শেষ হবে ১১টায় এবং শুরু হবে পৌনে ১০টায়। যেটাতে আমরা অ্যাটেন্ড করতে পারবো।

সেরকম ক্রাইটেরিয়া ১ এর শিডিউল অনুসারে যদি আমরা প্রথমে সিলেক্ট করবো ২য় সেমিনার, কারণ এটা সবার আগে শেষ হবে। এরপর বাকি দুইটা সেমিনারই শেষ হবে দুপুর ১২টায়। কিন্তু ১ম সেমিনার ৮টায় শুরু হওয়ায় আমরা সেটাতে অ্যাটেন্ড করতে পারবো না। কিন্তু ৩য় সেমিনার ১১টায় শুরু হওয়ায় সেটাতে আমরা অ্যাটেন্ড করতে পারবো।

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