গ্রিডি প্যাটার্ন বা লোভী পদ্ধতি (Greedy Pattern)

কল্পনা করুন আপনি একটি দাওয়াতে বা বুফেতে আছেন এবং আপনি সবসময় সামনে থাকা সবচেয়ে বড় মাংসের টুকরোটিই তুলে নিচ্ছেন। কখনো কখনো এটি একদম সঠিক কৌশল — শেষ পর্যন্ত আপনিই সবচেয়ে বেশি মাংস খেতে পারেন। কিন্তু কখনো হয়তো দেখা যায় একটি বিশাল টুকরো খুঁজতে গিয়ে আপনার এতটা সময় নষ্ট হলো যে আপনি সেই সময়ে দুটি মাঝারি টুকরো তুলে নিতে পারতেন।

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

গ্রিডি কখন আসলে কাজ করে?

একটি গ্রিডি অ্যালগরিদম কাজ করার নিশ্চয়তা তখনই থাকে যখন সমস্যায় দুটি বৈশিষ্ট্য থাকে:

গ্রিডি-চয়েস প্রপার্টি (Greedy-choice property): সবসময় এমন একটি গ্লোবাল অপ্টিমাল বা চূড়ান্ত সঠিক সমাধান থাকে যার মধ্যে আপনার গৃহীত গ্রিডি চয়েসটি বিদ্যমান। আপনাকে আপনার সিদ্ধান্ত নিয়ে দ্বিতীয়বার ভাবতে হয় না — দেখে যেটা সেরা মনে হচ্ছে সেটি নেওয়া সবসময়ের জন্য নিরাপদ।

অপ্টিমাল সাবস্ট্রাকচার (Optimal substructure): গ্রিডি সিদ্ধান্তটি নেওয়ার পর অবশিষ্ট সমস্যাটির গঠন বা স্ট্রাকচার আগের মতোই থাকে, এবং সেই ক্ষুদ্র অংশের সেরা সমাধানটি আপনার সিদ্ধান্তের সাথে যুক্ত হয়ে চূড়ান্ত সঠিক উত্তর প্রদান করে।

এই দুটি বৈশিষ্ট্য একসাথে থাকলে আপনি পিছন ফিরে না তাকিয়েই সামনে এগিয়ে যেতে পারেন।

দুই ধরনের ন্যাপস্যাকের গল্প

ফ্র্যাকশনাল ন্যাপস্যাক (Fractional Knapsack) (এখানে গ্রিডি কাজ করে): আপনার কাছে সোনার ধুলো, রুপার গুঁড়ো বা তামার ফিলিং আছে। আপনি যেকোনো ভগ্নাংশ পরিমাণ নিতে পারেন। সবসময় প্রতি গ্রামের সবচেয়ে মূল্যবান ধাতুটি আগে নিন। যেহেতু আপনি অবশিষ্ট প্রতি গ্রাম জায়গা সবচেয়ে সেরাটি দিয়ে পূর্ণ করতে পারেন, তাই এখানে গ্রিডি সিদ্ধান্ত সবসময় নিরাপদ।

0/1 ন্যাপস্যাক (0/1 Knapsack) (এখানে গ্রিডি ব্যর্থ হয়): আইটেমগুলো এখানে নিরেট ডাল বা বার হিসেবে থাকে — হয় পুরোটা নিতে হবে নাহলে কিছুই না। সবচেয়ে মূল্যবান বস্তুটি নেওয়ার ফলে আপনার ব্যাগে হয়তো এমন ফাঁকা জায়গা তৈরি হতে পারে যেখানে আর অন্য কিছু ধরে না। অথচ তুলনামূলক সস্তা দুটি বস্তু মিলে হয়তো আরও বেশি মূল্য দিতে পারত। গ্রিডি পদ্ধতি এখানে ফাঁকা জায়গার কাছে হেরে যায়।

প্রমাণ করার পদ্ধতি: এক্সচেঞ্জ আর্গুমেন্ট

গ্রিডি অ্যালগরিদমের সঠিকতা প্রমাণের স্ট্যান্ডার্ড উপায় হলো এক্সচেঞ্জ আর্গুমেন্ট। এটি অনেকটা এমন:

ধরুন সব সেরা সমাধানের একটি সেট OPT প্রথম সিদ্ধান্তেই আপনার গ্রিডি সিদ্ধান্তের চেয়ে আলাদা কিছু নিয়েছে। যেখানে গ্রিডি নিয়েছে G, সেখানে OPT নিয়েছে অন্য কিছু A। এখন প্রমাণ করুন যে A-এর বদলে G বসালেও OPT এর মান কমছে না বা খারাপ হচ্ছে না। এভাবে প্রতিটি অমিল থাকা জায়গায় গ্রিডি সিদ্ধান্ত বসিয়ে দিন। যেহেতু প্রতিটি পরিবর্তনের ফলে ফলাফল খারাপ হয়নি, তাই প্রমাণিত হলো যে গ্রিডি পদ্ধতিও নিখুঁত সমাধান দিতে সক্ষম।

গ্রিডি বনাম ডায়নামিক প্রোগ্রামিং

উভয় পদ্ধতির জন্যই অপ্টিমাল সাবস্ট্রাকচার প্রয়োজন। কিন্তু ডিপি বা ডায়নামিক প্রোগ্রামিং সবগুলো সম্ভাবনা যাচাই করে এবং ছোট ছোট সমাধানগুলো একত্রিত করে — এটি অনেকটা একজন দাবাড়ুর মতো যে ১০ ধাপ আগে থেকে চিন্তা করে। আর গ্রিডি একবার সিদ্ধান্ত নিলে আর পিছনে ফিরে তাকায় না — এটি অনেকটা একজন বিশেষজ্ঞের মতো যে হিসেব না করেই মুহূর্তেই সঠিক চালটি চিনে নিতে পারে।

একটি সহজ নিয়ম: যদি সমস্যায় কোনো নিরবিচ্ছিন্ন সম্পদ বা ন্যাচারাল অর্ডারিং (যেমন শেষ হওয়ার সময়, মূল্যের অনুপাত, ডেডলাইন) থাকে, তবে আগে গ্রিডি চেষ্টা করুন। আর যদি সিদ্ধান্তগুলো জটিল এবং 'সব বা কিছুই না' (all-or-nothing) ধাঁচের হয়, তবে ডিপি ব্যবহার করুন।