Next-fit bin packing
नेक्स्ट-फिट बिन पैकिंग के लिए एक ऑनलाइन एल्गोरिदम है। इसका निवेश विभिन्न आकारों की वस्तुओं की एक सूची है। इसका उत्पादन एक पैकिंग है-वस्तुओं का एक निश्चित क्षमता के डिब्बे में विभाजन, जैसे कि प्रत्येक बिन में वस्तुओं के आकार का योग अधिकतम क्षमता पर हो। आदर्श रूप से, हम जितना संभव हो उतना कम डिब्बे का उपयोग करना चाहेंगे, लेकिन डिब्बे की संख्या को कम करना एक एन. पी.-कठिन समस्या है। नेक्स्ट-फिट एल्गोरिथ्म निम्नलिखित ह्यूरिस्टिक का उपयोग करता हैः यह एक वर्तमान बिन रखता है, जो शुरू में खाली होता है। जब कोई वस्तु आती है, तो यह जांचती है कि वह वस्तु वर्तमान बिन में फिट बैठती है या नहीं। यदि यह फिट बैठता है, तो इसे इसके अंदर रखा जाता है। अन्यथा, वर्तमान बिन को बंद कर दिया जाता है, एक नया बिन खोला जाता है और आने वाली वस्तु को इस नए बिन के अंदर रखा जाता है। नेक्स्ट-फिट एक बाउंडेड स्पेस एल्गोरिदम है-इसे किसी भी समय खोलने के लिए केवल एक आंशिक रूप से भरे हुए बिन की आवश्यकता होती है। एल्गोरिथम का अध्ययन डेविड एस. जॉनसन ने 1973 में अपने डॉक्टरेट थीसिस में किया था। रन टाइम नेक्स्टफिट के चलने के समय को इस बात से सीमित किया जा सकता है कि सूची में वस्तुओं की संख्या कहाँ है। सन्निकटन अनुपात एन. एफ. (एल) द्वारा नेक्स्टफिट द्वारा उपयोग किए जाने वाले डिब्बों की संख्या और ओ. पी. टी. (एल) द्वारा सूची एल. के लिए संभव डिब्बों की इष्टतम संख्या को दर्शाता है। प्रमाण के लिए अंतर्ज्ञान निम्नलिखित है। इस एल्गोरिथ्म द्वारा उपयोग किए जाने वाले डिब्बों की संख्या डिब्बों की इष्टतम संख्या से दोगुनी से अधिक नहीं है। दूसरे शब्दों में, 2 डिब्बों का अधिक से अधिक आधा भरा होना असंभव है क्योंकि इस तरह की संभावना का तात्पर्य है कि किसी समय, ठीक एक डिब्बे में अधिक से अधिक आधा भरा हुआ था और एक नया खोला गया था ताकि अधिक से अधिक आकार की वस्तु को समायोजित किया जा सके। लेकिन चूंकि पहले वाले में कम से कम एक जगह है, इसलिए एल्गोरिथ्म किसी भी वस्तु के लिए एक नया बिन नहीं खोलेगा जिसका आकार अधिक से अधिक है। बिन से अधिक भरने के बाद या यदि उससे बड़े आकार की कोई वस्तु आती है, तो एल्गोरिथ्म एक नया बिन खोल सकता है। इस प्रकार अगर हमारे पास डिब्बे हैं, तो कम से कम डिब्बे आधे से अधिक भरे होते हैं। इसलिए,। क्योंकि इष्टतम मूल्य की एक निचली सीमा है, हम इसे प्राप्त करते हैं और इसलिए। लोअर बाउंड प्रत्येक के लिए, एक सूची मौजूद है जैसे कि और। सूचियों का परिवार जिसके लिए यह रखता है जो के साथ दिया जाता है। इस सूची के लिए इष्टतम समाधान में आकार के साथ दो वस्तुओं वाले डिब्बे और आकार के साथ वस्तुओं के साथ एक डिब्बे (यानी कुल डिब्बे) होते हैं, जबकि एन. एफ. द्वारा उत्पन्न समाधान में आकार की एक वस्तु और आकार के साथ एक वस्तु के साथ डिब्बे होते हैं। सीमित वस्तु का आकार यदि किसी वस्तु का अधिकतम आकार है, तो एसिम्प्टोटिक सन्निकटन अनुपात सभी के लिए संतुष्ट करता है। अन्य गुण नेक्स्ट-फिट एक सूची और उसके व्युत्क्रम को समान संख्या में डिब्बे में पैक करता है। नेक्स्ट-के-फिट (एनकेएफ) नेक्स्ट-के-फिट नेक्स्ट-फिट का एक प्रकार है, लेकिन केवल एक डिब्बे को खुला रखने के बजाय, एल्गोरिथ्म अंतिम डिब्बे को खुला रखता है और पहले डिब्बे को चुनता है जिसमें वस्तु फिट होती है। के लिए, एन. के. एफ. ऐसे परिणाम प्रदान करता है जो एन. एफ. के परिणामों की तुलना में बेहतर होते हैं, हालांकि, स्थिर मानों में वृद्धि से एल्गोरिथ्म में सुधार होता है और इसके सबसे खराब स्थिति में व्यवहार नहीं होता है। यदि एल्गोरिथ्म एक लगभग एनीफिट-एल्गोरिथ्म है और फिर। नेक्स्ट-फिट-डीक्रीज़िंग (एन. एफ. डी.) नेक्स्ट-फिट का ऑफ़लाइन संस्करण हैः यह सभी इनपुट वस्तुओं को स्वीकार करता है, उन्हें अवरोही आकार से ऑर्डर करता है, और नेक्स्ट-फिट कॉल करता है। इसका असिम्प्टोटिक सन्निकटन अनुपात बहुत बेहतर हैः 2 के बजाय 1.7 से कम। संदर्भ बिन पैकिंग