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