First-fit bin packing
फर्स्ट-फिट (एफ. एफ.) बिन पैकिंग के लिए एक ऑनलाइन एल्गोरिदम है। इसका निवेश विभिन्न आकारों की वस्तुओं की एक सूची है। इसका उत्पादन एक पैकिंग है-वस्तुओं का एक निश्चित क्षमता के डिब्बे में विभाजन, जैसे कि प्रत्येक बिन में वस्तुओं के आकार का योग अधिकतम क्षमता पर हो। आदर्श रूप से, हम जितना संभव हो उतना कम डिब्बे का उपयोग करना चाहेंगे, लेकिन डिब्बे की संख्या को कम करना एक एन. पी.-कठिन समस्या है। फर्स्ट-फिट एल्गोरिथ्म निम्नलिखित शोध का उपयोग करता हैः यह खुले डिब्बे की एक सूची रखता है, जो शुरू में खाली होता है। जब कोई वस्तु आती है, तो पहले बिन को ढूंढें जिसमें वस्तु फिट हो सकती है, यदि कोई हो। यदि ऐसा बिन पाया जाता है, तो नई वस्तु को उसके अंदर रखा जाता है। अन्यथा, एक नया बिन खोला जाता है और आने वाली वस्तु को उसके अंदर रखा जाता है। सन्निकटन अनुपात एफ. एफ. (एल) द्वारा प्रथम-फिट द्वारा उपयोग किए जाने वाले डिब्बों की संख्या को दर्शाता है, और ओ. पी. टी. (एल) द्वारा सूची एल के लिए संभव डिब्बों की इष्टतम संख्या। एफ. एफ. (एल) का विश्लेषण कई चरणों में किया गया था। एफ. एफ. के लिए पहली ऊपरी सीमा 1971 में उलमैन द्वारा साबित की गई थी। 1972 में, इस ऊपरी सीमा में गैरी, ग्राहम और उलमैन, जॉनसन और डेमर्स द्वारा सुधार किया गया था। 1976 में, गैरी, ग्राहम, जॉनसन, याओ और ची-चिह द्वारा इसमें सुधार किया गया था, जो और की अभिन्नता के कारण इसके बराबर है। 2010 में ज़िया और टैन द्वारा किए गए अगले सुधार ने सीमा को कम कर दिया। अंत में, 2013 में, डोसा और स्गल द्वारा इस सीमा में सुधार किया गया था। वे एक उदाहरण इनपुट सूची भी प्रस्तुत करते हैं, जिसके लिए यह सीमा मेल खाती है। नीचे हम प्रमाण विचार की व्याख्या करते हैं। एसिम्प्टोटिक अनुपात अधिकतम 2 यहाँ एक प्रमाण है कि एसिम्प्टोटिक अनुपात अधिकतम 2 है। यदि कोई एफ. एफ. बिन है जिसकी राशि 1/2 से कम है, तो शेष सभी वस्तुओं का आकार 1/2 से अधिक है, इसलिए निम्नलिखित सभी डिब्बों का योग 1/2 से अधिक है। इसलिए, अधिकतम एक को छोड़कर सभी एफ. एफ. डिब्बों में कम से कम आधा राशि होती है। सभी इष्टतम डिब्बों में अधिकतम 1 का योग होता है, इसलिए सभी आकारों का योग अधिकतम ओ. पी. टी. होता है। इसलिए, एफ. एफ. डिब्बों की संख्या अधिकतम 1 + ओ. पी. टी./(1/2) = 2 * ओ. पी. टी. + 1 लक्षणहीन अनुपात अधिकतम 1.75 है। यदि एक एफ. एफ. बिन है जिसकी राशि 2/3 से कम है, तो शेष सभी वस्तुओं का आकार 1/3 से अधिक है। चूँकि आकार अधिक से अधिक 1/2 होते हैं, इसलिए निम्नलिखित सभी डिब्बों (शायद अंतिम को छोड़कर) में कम से कम दो वस्तुएँ होती हैं, और योग 2/3 से बड़ा होता है। इसलिए, अधिकतम एक को छोड़कर सभी एफ. एफ. डिब्बों में कम से कम 2/3 का योग होता है, और एफ. एफ. डिब्बों की संख्या अधिकतम 2 + ओ. पी. टी./(2/3) = 3/2 * ओ. पी. टी. + 1 होती है। "समस्याग्रस्त" वस्तुएँ वे हैं जिनका आकार आधा से बड़ा है। इसलिए, विश्लेषण में सुधार करने के लिए, आइए प्रत्येक वस्तु को 1/2 से बड़ा आर का बोनस दें। किसी वस्तु के वजन को उसके आकार और उसके बोनस के रूप में परिभाषित करें। वस्तुओं के एक समूह के वजन को उसकी सामग्री के वजन के योग के रूप में परिभाषित करें। अब, एक वस्तु के साथ प्रत्येक एफ. एफ. बिन का वजन (अधिकतम एक को छोड़कर) कम से कम 1/2 + आर है, और दो या दो से अधिक वस्तुओं के साथ प्रत्येक एफ. एफ. बिन का वजन (अधिकतम एक को छोड़कर) 2/3 है। आर = 1/6 लेने से यह पता चलता है कि सभी एफ. एफ. डिब्बों का वजन कम से कम 2/3 है। दूसरी ओर, इष्टतम पैकिंग में प्रत्येक बिन का वजन अधिक से अधिक 1 + आर = 7/6 होता है, क्योंकि ऐसे प्रत्येक बिन में अधिक से अधिक एक वस्तु 1/2 से बड़ी होती है। इसलिए, सभी वस्तुओं का कुल वजन अधिकतम 7/6 * ओ. पी. टी. है, और एफ. एफ. डिब्बे की संख्या अधिकतम 2 + (7/6 * ओ. पी. टी./(2/3)) = 7/4 * ओ. पी. टी. + 2 है। असिंप्टोटिक अनुपात अधिकतम 1.7 निम्नलिखित प्रमाण से अनुकूलित किया गया है। एक इनपुट वस्तु के वजन को वस्तु के आकार x कुछ बोनस के रूप में परिभाषित करें जिसकी गणना निम्नानुसार की गई हैः एसिम्प्टोटिक सन्निकटन अनुपात दो दावों से मिलता हैः इष्टतम पैकिंग में, प्रत्येक बिन का वजन अधिकतम 17/12 होता है; फर्स्ट-फिट पैकिंग में, प्रत्येक बिन का औसत वजन कम से कम 5/6 = 10/12 होता है। इसलिए, लक्षणहीन रूप से, एफ. एफ. पैकिंग में डिब्बे की संख्या अधिक से अधिक 17/10 * ओ. पी. टी. होनी चाहिए। दावा 1 के लिए, यह साबित करने के लिए पर्याप्त है कि, किसी भी समूह बी के लिए अधिकतम 1 राशि के साथ, बोनस (बी) अधिक से अधिक 5/12 है। वास्तव मेंः यदि बी के पास 1/2 से बड़ी कोई वस्तु नहीं है, तो इसमें 1/6 से बड़ी अधिकतम पाँच वस्तुएँ हैं, और उनमें से प्रत्येक का बोनस अधिकतम 1/12 है; यदि बी के पास 1/2 से बड़ी वस्तु है, लेकिन [1/3,1 2] में कोई वस्तु नहीं है, तो इसमें (1/6,1 3) में अधिकतम दो वस्तुओं के लिए जगह है, और उनके बोनस का योग अधिकतम (1/2/2-1/6) = 1/12 है, इसलिए कुल बोनस 4/12 + 1/12 = 5/12 है। यदि बी के पास 1/2 से बड़ी वस्तु है और [1/3,1 2] में एक वस्तु है, तो इसमें 1/6 से बड़े आकार की वस्तुओं के लिए अधिक जगह नहीं है, इसलिए कुल बोनस फिर से 4/12+1 12 = 5/12 है। इसलिए, बी का वजन अधिकतम 1 + 5/12 = 17/12 है। दावा 2 के लिए, पहले एक ही वस्तु के साथ एक एफ. एफ. बिन बी पर विचार करें। यदि योग (बी) <1/2, तो-जिस तरह से एफएफ काम करता है-बी के बाद संसाधित सभी आइटम 1/2 से बड़े होने चाहिए (अन्यथा उन्हें बी में डाला जाता)। इसलिए, योग <1/2 के साथ अधिक से अधिक एक एफ. एफ. बिन होता है। अब योग (बी)> 1/2 के साथ एक ही वस्तु के साथ अन्य सभी डिब्बे बी पर विचार करें। इन सभी डिब्बों के लिए, वजन (बी)> 1/2+1 3 = 5/6। अब दो या दो से अधिक वस्तुओं के साथ एफ. एफ. डिब्बे बी पर विचार करें। यदि योग (बी) <2/3 है, तो-जिस तरह से एफएफ काम करता है-बी के बाद संसाधित सभी आइटम 1/3 से बड़े होने चाहिए (अन्यथा उन्हें बी में डाला जाता)। इसलिए, दो या दो से अधिक वस्तुओं वाले सभी डिब्बे 2/3 से बड़े होते हैं। इसलिए दो या दो से अधिक वस्तुओं के साथ अधिक से अधिक एक एफ. एफ. बिन होता है और योग <2/3 होता है। अब दो या दो से अधिक वस्तुओं वाले अन्य सभी डिब्बों पर विचार करें और योग> 2/3। उन्हें बी [1], बी [2], बी [के] से चिह्नित करें, जिस क्रम से वे खोले जाते हैं। 1,., k में प्रत्येक i के लिए, हम साबित करते हैं कि B [i] और B [i + 1] के बोनस का योग कम से कम 5/6 हैः योग (B [i]) + बोनस (B [i + 1])> = 5/6। वास्तव में, यदि योग (बी [आई])> = 5/6 है तो असमानता तुच्छ है। अन्यथा, योग (B [i]): = 1-x मान लीजिए। ध्यान दें कि x 1/6 और 2/6 के बीच है, क्योंकि योग (B [i]) 2/3 और 5/6 के बीच है। चूँकि B [i + 1] को B [i] के बाद खोला जाता है, B [i + 1] में कम से कम दो आइटम होते हैं, जैसे कि c1 और c2, जो B [i] में फिट नहीं होते हैं, अर्थात्ः c1, c2> 1-योग (B [i]) = x> 1/6। फिर c1 और c2 में से प्रत्येक का बोनस कम से कम x/2-1/12 है। इसलिए, B [i + 1] का बोनस कम से कम x-1/6 है, इसलिए योग (B [i]) + बोनस (B [i + 1])> = (1-x) + (x-1/6) = 5/6 है। हम उपरोक्त असमानता को क्रमिक जोड़ों पर लागू कर सकते हैं, और प्राप्त कर सकते हैंः योग (बी [1]) + बोनस (बी [2]) + योग (बी [2]) + बोनस (बी [3]) + + योग (बी [के-1]) + बोनस (बी [के])> = 5/6 * (के-1)। इसलिए, सभी एफ. एफ. डिब्बों का कुल वजन कम से कम 5/6 * (एफ. एफ.-3) है (जहां हम योग <1/2 के साथ एकल एक-वस्तु बिन के लिए 3, योग <2/3 के साथ एकल दो-वस्तु बिन, और योग> = 2/3 के साथ दो-वस्तु बिन से के-1 घटाते हैं)। कुल मिलाकर, हमें वह 17/12 * OPT> = 5/6 * (FF-3) मिलता है, इसलिए FF <= 17/10 * OPT + 3। डासा और सिगल एक कड़ा विश्लेषण प्रस्तुत करते हैं जो 3 से छुटकारा दिलाता है, और उस एफ. एफ. <= 17/10 * ओ. पी. टी. को प्राप्त करता है। निम्न सीमा ऐसे उदाहरण हैं जिन पर 1.7OPT का प्रदर्शन सीमा तंग है। निम्नलिखित उदाहरण इस पर आधारित है। बिन क्षमता 101 है, औरः अनुक्रम हैः 6 (x7), 10 (x7), 16 (x3), 34 (x10), 51 (x10)। इष्टतम पैकिंग में 10 डिब्बे होते हैंः [51+34 + 16] (x3), [51+34 + 10+6] (x7)। सभी बिन राशि 101 हैं। फर्स्ट फिट पैकिंग में 17 डिब्बे होते हैंः [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5), [51] (x10)। बिन राशिः 92,68,68 (x5), 51 (x10) हैं। पुरस्कार (101 तक सामान्यीकृत) 0,0,16.8 (x5), 33.7 (x10) हैं। कुल भार (101 तक सामान्यीकृत) 92,68,84.8 (x5), 84.7 (x10) हैं। यह देखा जा सकता है कि लगभग सभी भार 101 * 5/6 = 84.1 के करीब हैं। रिफाइंड फर्स्ट-फिट रिफाइंड-फर्स्ट-फिट (आर. एफ. एफ.) बिन पैकिंग के लिए एक और ऑनलाइन एल्गोरिदम है, जो पहले विकसित एफ. एफ. एल्गोरिदम में सुधार करता है। यह एंड्रयू ची-चिह याओ द्वारा प्रस्तुत किया गया था। एल्गोरिथ्म वस्तुओं को उनके आकार के अनुसार चार वर्गों में वर्गीकृत किया गया है (जहां बिन की क्षमता 1 है):-टुकड़ा-आकार। - टुकड़ा-आकार में। - टुकड़ा-आकार में। - टुकड़ा-आकार में। इसी तरह, डिब्बों को चार वर्गों में वर्गीकृत किया गया हैः 1,2,3 और 4। माना कि यह एक निश्चित पूर्णांक है। अगली वस्तु को किसी भी पूर्णांक के लिए-कक्षा 1, यदि एक-टुकड़ा है, तो कक्षा 2, यदि एक-टुकड़ा है, तो कक्षा 3, यदि एक-टुकड़ा है, लेकिन अब तक देखा गया th-टुकड़ा नहीं है। कक्षा 1, यदि अब तक देखा गया छठा टुकड़ा है, तो कक्षा 4, यदि एक टुकड़ा है। एक बार जब वस्तु का वर्ग चुना जाता है, तो इसे पहले-फिट बिन पैकिंग का उपयोग करके उस वर्ग के डिब्बे के अंदर रखा जाता है। ध्यान दें कि आर. एफ. एफ. एक एनी-फिट एल्गोरिथ्म नहीं है क्योंकि यह इस तथ्य के बावजूद एक नया बिन खोल सकता है कि वर्तमान वस्तु एक खुले बिन (दूसरे वर्ग से) के अंदर फिट बैठती है। सन्निकटन अनुपात आर. एफ. एफ. की अनुमानित गारंटी है। के लिए सूचियों का एक परिवार मौजूद है। फर्स्ट-फिट-डीक्रीज़िंग (एफ. एफ. डी.) फर्स्ट-फिट का ऑफ़लाइन संस्करण हैः यह सभी इनपुट वस्तुओं को स्वीकार करता है, उन्हें अवरोही आकार से ऑर्डर करता है, और फर्स्ट-फिट कॉल करता है। इसका असिम्प्टोटिक सन्निकटन अनुपात बहुत बेहतर हैः 1.7 के बजाय लगभग 1.222। कार्यान्वयन पायथनः पी. आर. टी. पी. आई. पैकेज में फर्स्ट-फिट का कार्यान्वयन होता है। संदर्भ बिन पैकिंग