Best-fit bin packing
বেস্ট-ফিট হল বিন প্যাকিংয়ের জন্য একটি অনলাইন অ্যালগরিদম। এর ইনপুট হল বিভিন্ন আকারের আইটেমের একটি তালিকা। এর আউটপুট হল একটি প্যাকিং-নির্দিষ্ট ক্ষমতার বিনগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি বিন-এ আইটেমগুলির আকারের যোগফল সর্বাধিক ক্ষমতা হয়। আদর্শভাবে, আমরা যতটা সম্ভব কম বিন ব্যবহার করতে চাই, তবে বিনগুলির সংখ্যা হ্রাস করা একটি এনপি-হার্ড সমস্যা। সেরা-ফিট অ্যালগরিদম নিম্নলিখিত অনুসন্ধানমূলক ব্যবহার করেঃ এটি খোলা বিনগুলির একটি তালিকা রাখে, যা প্রাথমিকভাবে খালি থাকে। যখন কোনও জিনিস আসে, তখন এটি সর্বাধিক লোড সহ বিনটি খুঁজে পায় যার মধ্যে আইটেমটি ফিট করতে পারে, যদি থাকে। যদি এই ধরনের একটি বিন পাওয়া যায়, তাহলে নতুন জিনিসটি তার ভিতরে রাখা হয়। অন্যথায়, একটি নতুন বিন খোলা হয় এবং আগত জিনিসটি তার ভিতরে রাখা হয়। আনুমানিক অনুপাত বিএফ (এল) দ্বারা বেস্ট-ফিট দ্বারা ব্যবহৃত বিনগুলির সংখ্যা এবং ওপিটি (এল) দ্বারা তালিকা এল-এর জন্য সম্ভাব্য বিনগুলির সর্বোত্তম সংখ্যা নির্দেশ করে। বিএফ (এল)-এর বিশ্লেষণ বেশ কয়েকটি ধাপে করা হয়েছিল। 1971 সালে উলম্যান প্রথম আপার বাউন্ড প্রমাণ করেন। গ্যারি, গ্রাহাম এবং উলম্যান, জনসন এবং ডেমার্স একটি উন্নত আপার বাউন্ড প্রমাণ করেছিলেন। পরে, গ্যারি, গ্রাহাম, জনসন, উলম্যান, ইয়াও এবং চি-চিহ এর উন্নতি করেন। অবশেষে ডোসা এবং সিগাল এই সীমারেখার উন্নতি ঘটান। তারা একটি উদাহরণ ইনপুট তালিকাও উপস্থাপন করে, যার জন্য এই সীমার সাথে মেলে। সবচেয়ে খারাপ-ফিট সবচেয়ে ভাল-ফিট করার জন্য একটি "দ্বৈত" অ্যালগরিদমঃ এটি পরবর্তী আইটেমটিকে ন্যূনতম লোড সহ বিনটিতে রাখার চেষ্টা করে। এই অ্যালগরিদমটি নেক্সট-ফিটের মতো খারাপ আচরণ করতে পারে এবং এর জন্য সবচেয়ে খারাপ-কেস তালিকায় এটি করবে। উপরন্তু, এটি ধরে রাখে। যেহেতু সবচেয়ে খারাপ-ফিট একটি এনিফিট-অ্যালগরিদম, তাই এমন একটি এনিফিট-অ্যালগরিদম রয়েছে। রেফারেন্স বিন প্যাকিং