Harmonic bin packing
हार्मोनिक बिन-पैकिंग बिन पैकिंग के लिए ऑनलाइन एल्गोरिदम का एक परिवार है। इस तरह के एल्गोरिथ्म के लिए इनपुट विभिन्न आकारों की वस्तुओं की एक सूची है। आउटपुट एक पैकिंग है-वस्तुओं का एक निश्चित क्षमता के डिब्बे में विभाजन, जैसे कि प्रत्येक बिन में वस्तुओं के आकार का योग अधिकतम क्षमता पर हो। आदर्श रूप से, हम जितना संभव हो उतना कम डिब्बे का उपयोग करना चाहेंगे, लेकिन डिब्बे की संख्या को कम करना एक एन. पी.-कठिन समस्या है। हार्मोनिक बिन-पैकिंग एल्गोरिदम एक हार्मोनिक प्रगति के बाद वस्तुओं को उनके आकार के आधार पर श्रेणियों में विभाजित करने पर निर्भर करते हैं। इस विचार के कई रूप हैं। हार्मोनिक-के एल्गोरिथ्म आकारों के अंतराल को सामंजस्यपूर्ण रूप से टुकड़ों में विभाजित करता है। एक वस्तु को एक-वस्तु कहा जाता है, यदि। एल्गोरिथ्म खाली डिब्बे के सेट को प्रत्येक आइटम प्रकार के लिए एक बिन प्रकार के लिए अनंत वर्गों में विभाजित करता है। प्रकार के डिब्बे का उपयोग केवल प्रकार की वस्तुओं को पैक करने के लिए किया जाता है। के लिए प्रकार के प्रत्येक बिन में बिल्कुल-आइटम हो सकते हैं। एल्गोरिथ्म अब इस प्रकार कार्य करता हैः यदि अगली वस्तु एक-वस्तु के लिए है, तो वस्तु को पहले (केवल खुले) बिन में रखा जाता है जिसमें कम से कम टुकड़े होते हैं या यदि ऐसा कोई बिन मौजूद नहीं है तो एक नया खोलता है। यदि अगला आइटम एक-आइटम है, तो एल्गोरिथ्म इसे नेक्स्ट-फिट का उपयोग करके प्रकार के डिब्बे में रखता है। इस एल्गोरिथ्म का वर्णन सबसे पहले ली और ली ने किया था। इसमें एक समय जटिलता है जहाँ n इनपुट वस्तुओं की संख्या है। प्रत्येक चरण में, अधिक से अधिक खुले डिब्बे होते हैं जिनका संभावित रूप से वस्तुओं को रखने के लिए उपयोग किया जा सकता है, यानी, यह एक के-बाउंडेड स्पेस एल्गोरिदम है। ली और ली ने एसिम्प्टोटिक सन्निकटन अनुपात का भी अध्ययन किया। उन्होंने एक अनुक्रम को परिभाषित किया, और साबित किया कि इसके लिए यह है। क्योंकि यह इसे धारण करता है। इसके अतिरिक्त, उन्होंने उस रिफाइंड-हार्मोनिक (आरएच) के लिए सबसे खराब स्थिति के उदाहरणों का एक परिवार प्रस्तुत किया रिफाइंड-हार्मोनिक हार्मोनिक-के एल्गोरिदम के विचारों को रिफाइंड-फर्स्ट-फिट के विचारों के साथ जोड़ता है। यह रिफाइंड-फर्स्ट-फिट के समान बड़ी वस्तुओं को रखता है, जबकि छोटी वस्तुओं को हार्मोनिक-के का उपयोग करके रखा जाता है। इस रणनीति के लिए अंतर्ज्ञान उन टुकड़ों वाले डिब्बों के लिए भारी कचरे को कम करना है जो केवल उससे बड़े हैं। एल्गोरिथ्म निम्नलिखित अंतरालों के संबंध में वस्तुओं को वर्गीकृत करता हैः,,,, के लिए, और। एल्गोरिथ्म-वस्तुओं को हार्मोनिक-के के रूप में रखता है, जबकि यह और में वस्तुओं के लिए एक अलग रणनीति का पालन करता है। डिब्बे में वस्तुओं और वस्तुओं को पैक करने की चार संभावनाएँ हैं। एक-बिन में केवल एक-वस्तु होती है। एक-बिन में केवल एक-वस्तु होती है। एक-बिन में एक-वस्तु और एक-वस्तु होती है। एक-बिन में दो-वस्तुएँ होती हैं। एक-बिन एक बिन को दर्शाता है जिसे दूसरी-वस्तु रखने के लिए नामित किया जाता है। एल्गोरिथ्म समाधान में संबंधित डिब्बों की संख्या की गणना करने के लिए संख्याएँ N _ a, N _ b, N _ ab, N _ b b और N _ b 'का उपयोग करता है। इसके अलावा, एक सूची के लिए N _ c = N _ b + N _ ab एल्गोरिदम परिष्कृत-हार्मोनिक-k L = (i _ 1, \dotts i _ n): 1। एन. ए. = एन. बी. = एन. बी. बी. = एन. बी. बी. = एन. सी. = 02। यदि i _ j एक I _ k-टुकड़ा है तो इसे पैक करने के लिए एल्गोरिथ्म हार्मोनिक-k का उपयोग करें 3. अन्यथा यदि i _ j एक I _ a-आइटम है तो यदि N _ b! = 1, तो i _ j को किसी भी J _ b-बिन में पैक करें; N _ b--; N _ ab + +; अन्यथा i _ j को एक नए (खाली) बिन में रखें; N _ a + +; 4. अन्यथा यदि i _ j एक I _ b-आइटम है तो यदि N _ b '= 1 तो i _ j को I _ b'-बिन में रखें; N _ b '= 0; N _ bb + +; 5. अन्यथा यदि N _ bb <= 3N _ c है तो i _ b को रखें। उन्होंने साबित कर दिया कि इसके लिए यह सही है। अन्य प्रकार संशोधित हार्मोनिक (एम. एच.) में एसिम्प्टोटिक अनुपात होता है। संशोधित हार्मोनिक 2 (एम. एच. 2) में असिम्प्टोटिक अनुपात होता है। हार्मोनिक + 1 (एच + 1) में एसिम्प्टोटिक अनुपात होता है। हार्मोनिक + + (एच + +) का एसिम्प्टोटिक अनुपात और है। संदर्भ बिन पैकिंग