Skip to main content

Knapsack Problem (Branch & Bound method) ।।। ন্যাপস্যাক প্রব্লেম ( ব্রাঞ্চ এন্ড বাউন্ড মেথড )




ন্যাপস্যাক এর এই প্রব্লেম টা বিভিন্ন উপায়ে সল্ভ করা যায় । তার মাঝে আছে -Dynamic programming,greedy method,backtracking -------ইত্যাদি । আমরা এই প্রব্লেম টা branch and bound পদ্ধতিতে সমাধান করবো । প্রথমেই বলে নেই , আমাদের লক্ষ্য হলো সর্বাধিক প্রফিট অর্জন করা । যার মানে হলো , আমাকে একটা ব্যাগ বা থলে দেয়া হয়েছে যেটা কে আমরা ন্যাপ স্যাক বলছি আর সেই সাথে সেই ব্যাগ এর একটা ম্যাক্সিমাম ক্যাপাসিটি বলে দেয়া হয়েছে । অই ক্যাপাসিটি এর উপরে আমরা ব্যাগ এ পণ্য ঢুকাতে পারবো না । মনে করো বাজার থেকে যে চাউলের বস্তা কিনে আনা হয় সেটার গায়ে লিখা থাকে ১০০ কেজি অথবা ৫০ কেজি অথবা ২৫ কেজি । যার মানে হলো অই বস্তার চাউল ধারণ ক্ষমতা সর্বোচ্চ ১০০/৫০/২৫ কেজি । অনুরূপ ভাবেই ন্যাপস্যাক এও যে পণ্য গুলা ঢুকাবো সেগুলার টোটাল ওয়েট কখনোই আমার ক্যাপাসিটি থেকে বেশি হতে পারবে না । উপরের চিত্র টা খেয়াল করলে আমরা দেখতে পাই ,আমাদের কে ৪টা পণ্য দেয়া হয়েছে সেই সাথে তাদের ওয়েট আর প্রফিট ও দেয়া হয়েছে । চিন্তার কোনোই কারণ নেই আমরা ধাপে ধাপে সমাধান এর দিকে এগুবো ... তার আগে কিছু কথা বলে নেয়া প্রয়োজন,লক্ষ্য করিঃ

  1. এই প্রব্লেম সল্ভ করতে গেলে আমাদের আপার বাউন্ড এবং কস্ট বের করার প্রয়োজন পড়বে । সেগুলোকে আমরা যথাক্রমে 'u' এবং 'c' দিয়ে প্রকাশ করবো ।
  2. আপার বাউন্ড(u) এবং কস্ট(c) এর ভ্যালু এর আগে সবসময় মাইনাস (-) সাইন ইউজ হবে ।
  3. আমরা কোনো পণ্যের ই ভগ্নাংশ নিতে পারবো না । নিলে পুরো পণ্য টাই নিতে হবে নতুবা নেয়া যাবে না ।
  4. আমাদের লক্ষ্য হলো লোয়েস্ট কস্ট এ হাইয়েস্ট প্রফিট গেইন করা । এটাকে তাই ম্যাক্সিমাইজেশন প্রব্লেম ও বলা হয়ে থাকে । প্রাইমারি ভাবে আপার নামক একটা ভেরিয়েবল এ আমরা ইনফিনিটি এসাইন করে রাখবো । তারপরে যখনই কোনো নোড এর জন্য কস্ট আর আপার বাউন্ড বের করবো তখন প্রাপ্ত আপার বাউন্ড এর সাথে আগে আপার ভেরিয়েবল এর ভ্যালু কম্পেয়ার হবে এবং যেটা ছোট সেটাই নতুন করে আপার ভেরিয়েবল এ এসাইন করে দিবো । প্রথমে আমরা ফার্স্ট নোড ক্রিয়েট করবো এবং সেটার জন্য কস্ট আর আপার বাউন্ড নির্ণয় করবো ।
  5. চলো শুরু করা যাক-----



উপরে প্রথম নোড এর জন্য কস্ট এবং আপার বাউন্ড বের করেছি আমরা । প্রথমে লক্ষ্য করি , প্রথম ৩টা অবজেক্ট বা পণ্য আমরা আমাদের ন্যাপস্যাক এ রাখার পরে আমরা দেখলাম আমাদের ওয়েট অলরেডি ২+৪+৬=১২ হয়ে গেছে ! আর আমাদের ক্যাপাসিটি দেয়া আছে ১৫ এবং ৪ নাম্বার অবজেক্ট এর ওয়েট ৯! এখন যদি আমরা সেটাও ঢুকাতে চাই আমাদের ন্যাপস্যাক এ তাহলে টোটাল ওয়েট হয় ২+৪+৬+৯=২১ !! যা কিনা আমাদের ক্যাপাসিটি কে ওভার ফ্লো করে । এজন্য আমরা ৩টা অবজেক্ট নিয়ে থেমে যাবো আর দেখবো ন্যাপস্যাক পুরা করতে আর কত ওয়েট প্রয়োজন । সেই কাজ তো পানির মতো সোজা ! আমরা দেখলাম ১৫-১২=৩ , মানে একক হিসেবে যদি "কেজি" ধরি তাহলে বাকি থাকে ৩ কেজি । তারমানে আরো ৩ কেজি পণ্য ন্যাপস্যাক এ রাখা যাবে । তো আমরা এখন আগের বের করা টোটাল কস্ট এর সাথে ৪ নাম্বার অবজেক্ট এর [ (প্রফিট/ওয়েট ) X ৩] যোগ করবো । তারপর, আমাদের টোটাল কস্ট বের হয়ে যাবে । আর এটা কীভাবে বের হলো ? অবশ্যই ফ্র্যাকশনাল ভ্যালু যোগ করেই বের করলাম আমরা ,যেটা কিনা আগেই চিত্রে বলে দিয়েছি । এখন বলো তো আপার বাউন্ড কীভাবে বের করবো ??? সেটা তো আরো সোজা কাজ !! সেটাও এখান থেকেই বের করবো শুধুমাত্র ফ্র্যাকশনাল অংশ টুকু বাদ দিয়ে যোগ করলে যেটা হয় সেটাই আমাদের আপার বাউন্ড । তারমানে ১০+১০+১২=৩২ এটাই আমাদের আপার বাউন্ড । সোজা না !! এখন আরেকটা জিনিশ লক্ষ্য করি , আগে আপার এর মান আমরা এসাইন করে দিয়েছিলাম "ইনফিনিটি" কিন্তু এখন তো আপার বাউন্ড এর মান পেয়েছি "-৩২" আর এই ২টা কম্পেয়ার করে দেখলাম " ইনফিনিটি " বড় আর "-৩২" ছোট । তাঁর মানে আমরা "আপার" এর মান এখন আপডেট করে সেখানে "-৩২" রাখবো । এমন টাই বলে রাখা হয়েছিলো উপরে । যদি ভুলে গিয়ে থাকো তাহলে একবার আবার উপরে চোখ বুলিয়ে আসো । মূলত এভাবেই আমরা প্রতিটা নোড এর জন্য ভ্যালু বের করবো , তবে সব নোড এর লেফট চাইল্ড এর জন্য "আপার বাউন্ড " আর "কস্ট" এর ভ্যালু একই থাকবে । তারমানে হলো , একদম শুরু তে প্রথম নোড এর জন্য যে ভ্যালু বের করেছিলাম সেগুলাই থাকবে (লেফট চাইল্ডে প্যারেন্ট নোডের ডিফল্ট ভ্যালু থাকবে "আপার বাউন্ড" আর "কস্ট" এর জন্য যেটা বের করা হয়েছিলো ) । অনেক কথা হয়েছে এখন পরের ধাপের দিকে এগুই চলোঃ



এখন আমরা প্রথম অবজেক্ট ইনক্লুড করবো । এজন্য ২ নাম্বার নোডে " আপার বাউন্ড " আর " কস্ট " একই থাকবে । কিন্তু ৩ নাম্বার নোডে যখন " আপার বাউন্ড " আর " কস্ট " ক্যালকুলেশন করবো তখন আমরা প্রথম অবজেক্ট এর ভ্যালু গুলা (প্রফিট আর ওয়েট ) বাদ দিয়ে বাকি গুলো কাউন্ট করবো । এবার ক্যালকুলেশন এর প্রসেস আগের মতোই । অহ, এখন আরেক টা কথা বলার সময় এসেছে । সেটা হলো, প্রত্যেকটা নোডের কস্ট বের করার পরেই সেটা উপরের আপার ভেরিয়েবল এ যে ভ্যালু রাখা আছে সেটার সাথে কম্পেয়ার করে দেখবো । যদি ওইটার চাইতে বড় কোনো ভ্যালু পাই তাইলে বর্তমান নোড টা ***কিল*** করে দিবো । যার মানে হলো ক্রস করে দিবো ,সেটা আর এক্টিভ থাকবে না । কারণ আমাদের লক্ষ্য তো লোয়েস্ট কস্টে হাইয়েস্ট প্রফিট পাওয়া । তো এখানে যদি দেখি কস্ট আগের চাইতে বেড়ে গেসে তাইলে সে রাস্তা তে কন্টিনিউ না করাই বেটার । আশা করি বুঝাতে পারলাম । এখনো বুঝতে না পারলে আরো কয়েক বার পড়ে নিতে পারো প্যারা টা । এখানে ২ আর ৩ নাম্বার নোডে দেখা গেলো কস্ট এর মান -৩৮ এবং -৩২ । যেটা কিনা উপরের " আপার " ভেরিয়েবল এর -৩২ এর চাইতে একটা বড় আর অন্য টা সমান সমান । তাঁর মানে চেঞ্জ এর প্রয়োজন নেই । এখন নতুন আরেকটা প্রশ্ন আসতে পারে , সেটা হলো ... আমাদের নেক্সট স্টেপ কি হবে ??? এখন কি আমরা ৩ নাম্বার নোড ধরেই এগুবো নাকি ২ নাম্বার ! কোন টা তে এক্সপ্লোর করবো ? কারণ ২টাই যে খালি ! এটার সহজ সমাধান হলো যার " কস্ট " কম তার কাছেই যাবো । দেখা যাচ্ছে ২ নাম্বার নোড এর কস্ট কম ,তাহলে সেখান থেকেই নেক্সট স্টেপ শুরু হবে । আমরা এখন ২ নাম্বার অবজেক্ট ইনক্লউড করবো ।



এখানে আমরা যখন ২ নাম্বার অবজেক্ট ঢুকাবো তখন ৪ নাম্বার নোডে " আপার " এবং " কস্ট " এর ভ্যালু আগের টাই থাকবে । তারপরে আমরা যাবো ৫ নাম্বার নোডে যেখানে ২ নাম্বার অবজেক্ট কে বাদ দিয়ে "আপার বাউন্ড" এবং " কস্ট " এর ভ্যালু সেই আগের মতোই বের করবো ।



এভাবেই সেইম প্রসেস অনুযায়ী ৬ আর ৭ নাম্বার নোড পর্যন্ত যাবো । তারপরে আমাদের আটকে যেতে হবে । কিন্তু কেন ??? দেখো , নোড নাম্বার ৬ পর্যন্ত যখন আমরা এসেছি ততক্ষণে ৩টা অবজেক্ট ঢুকানো হয়ে গেছে ন্যাপস্যাক এর ভেতর । আর ৪ নাম্বার অবজেক্ট যদি ঢুকাই তাহলে ম্যাক্সিমাম ক্যাপাসিটি ওভার ফ্লো করবে । কারণ, তখন ওয়েট হয়ে যাবে ২+৪+৬+৯=২১ ! কিন্তু আমাদের ক্যাপাসিটি তো মাত্র ১৫ !!! সো আর আগানো যাবে না । এখানেই ইতি টানতে হবে । এবার নজর দেয়া যাক ৭ নাম্বার নোডের দিকে । আগে বলো তো একটু উপরের চিত্র টা দেখে , আমরা ৭ নাম্বার নোডে কীভাবে এসেছি ??? প্রথমে ১ তারপরে ২, ৪ তারপরে ৭ নাম্বার নোডে এসেছি । আবার এর মাঝেও এই ফ্লো তে ৩ নাম্বার অবজেক্ট ঢুকাই নি । তারমানে প্রথম ২টা অবজেক্ট এর জন্য ওয়েট ২+৪=৬ হয়েছে মাত্র !!! আমরা চাইলেই ৪ নাম্বার অবজেক্ট অনায়াসেই ঢুকাতে পারি । আর সেটা ক্যালকুলেশন করেও দেখলাম ২+৪+৯=১৫ ই হয় !!!! তবে আর বাধা কোথায় ??? আমাদের ম্যাক্সিমাম ক্যাপাসিটি ও তো ১৫ ই । তো আমরা প্রথমে ৭ নাম্বার নোডের লেফট চাইল্ড ড্র করলাম । আর সেটার ডিফল্ট "আপার বাউন্ড" এবং "কস্ট" এর ভ্যালু অবশ্যই হবে তার প্যারেন্ট নোড ৭ এর ভ্যালু গুলা ! এবার আমরা রাইট চাইল্ড নোড মানে ৯ নাম্বার নোডের দিকে যাই । সেখানে অবশ্যই ৪ নাম্বার অবজেক্ট ঢুকানো যাবে না । সেটা আগেই বলেছি । তো এখন যা করবো সেটা হলো ১,২,৪,৭,৯ এই নোড গুলা পাড়ি দিয়ে আসতে আমি যতগুলা অবজেক্ট বাদ দিয়েছি সেগুলা বাদ দিয়েই ক্যালকুলেশন করে "আপার বাউন্ড" আর "কস্ট" এর মান বের করতে হবে । আমাদের মান বের হয়েছে "-২০" যেটা কিনা আমার উপরের আপার ভেরিয়েবল এ রাখা মান "-৩৮" থেকে বড় ! সো এটার লাইফ স্টোরি এখানেই ইতি টানতে হবে । আবার মাঝে আমারা " আপার " ভেরিয়েবল এর মান ও আপডেট করেছি সময়ের প্রয়োজন এ । আর একে একে ৩,৫,৬,৯ নাম্বার নোড এর লাইফ স্টোরির ইতি টেনেছি । যাকে *কিল করা বলে । একদম শেষে এসে দেখা গেলো বেচে আছে শুধু ৮ নাম্বার নোড !! আর দেখো ৮ নাম্বার নোড এর কস্ট ই সবার চাইতে লোয়েস্ট । আবার আমরা যখন ৮ নাম্বার নোডে এসে পৌঁছেছি তখন লাস্ট নাম্বার অবজেক্ট নিয়ে নিয়েছি । তাহলে এটাই আমাদের ফাইনাল নোড ।

Written By -

          

Quote :

Only I can change my life. No one can do it for me || The past cannot be changed. The future is yet in your power. || Where there is a will, there is a way. If there is a chance in a million that you can do something, anything, to keep what you want from ending, do it. Pry the door open or, if need be, wedge your foot in that door and keep it open. || ... Do not wait; the time will never be ‘just right.’ Start where you stand, and work with whatever tools you may have at your command, and better tools will be found as you go along....|| Press forward. Do not stop, do not linger in your journey, but strive for the mark set before you...