🙌🏿 👤 ✏️ दो आयामी पैकेजिंग के बारे में: ऑनलाइन एल्गोरिदम 👩🏼‍⚕️ 🗨️ 🤴🏻

यह ऑफ़लाइन पैकेजिंग एल्गोरिदम के बारे में पोस्ट का एक निरंतरता है।

समस्या का सार: हमारे पास एक अर्ध-अनंत पट्टी है - जैसे कि टेट्रिस में, केवल गेम ओवर के बिना, और आयतों का एक सीमित सेट। आयतों पर डेटा वास्तविक समय में आता है; प्रत्येक नई आयत को तुरंत रखा जाना चाहिए और अब स्थानांतरित नहीं किया जाना चाहिए। लक्ष्य पैक आयतों की समग्र ऊंचाई को कम करना है।
यह एक अर्ध-बाउंड स्ट्रिप (2 डायमेंशनल स्ट्रिप पैकिंग, 2DSP) में आयतों को पैक करने के कार्य का ऑनलाइन रूपांतर है।

पिछले लेख में थोड़ी अधिक सैद्धांतिक जानकारी मिल सकती है, लेकिन अब, आगे की हलचल के बिना, आइए एल्गोरिदम पर चलते हैं।

वर्णन करने के लिए ईंटों के इस क्रम का उपयोग किया जाएगा:

(स्रोत डेटा प्रायोजक - random.org)।
कुछ अनुमानी एल्गोरिदम का वर्णन किया जाएगा, जिनमें से सामान्य विचार पट्टी को क्षेत्रों में विभाजित करना है, और कुछ मानदंडों के अनुसार एक विशेष क्षेत्र में नए आगमन वाले आयतों को रखना है।

स्तर के एल्गोरिदम

सभी स्तर के एल्गोरिदम का दृष्टिकोण यह है कि इस स्तर पर उपलब्ध आयतों की ऊंचाई के आधार पर पट्टी को स्तरों में विभाजित किया गया है। आयत को वर्तमान स्तर के आधार पर बाएं से दाएं तक संभव के रूप में रखा जाता है; एक आयत जो फिट नहीं होती है उसे अगले स्तर पर पैक किया जाता है। प्रत्येक स्तर की ऊंचाई इसमें उच्चतम आयत द्वारा निर्धारित की जाती है। यहां तीन पैकेजिंग विकल्प दिए गए हैं:
अगला फ़िट स्तर - जब अगला स्तर खुलता है, तो पिछला "बंद हो जाता है" और अब इसे नहीं माना जाता है;
पहला फिट स्तर - एल्गोरिथ्म के प्रत्येक चरण पर, प्रत्येक स्तर को देखा जाता है, सबसे कम से शुरू होता है, और आयत पहले उपयुक्त एक पर पैक किया जाता है, जिसमें पर्याप्त स्थान होता है;
एल्गोरिथ्म के प्रत्येक चरण में सर्वश्रेष्ठ फिट स्तर - सभी स्तरों को स्कैन किया जाता है, और सबसे उपयुक्त एक का चयन किया जाता है - वह जिसमें पैकेजिंग के बाद न्यूनतम स्थान होगा।
सभी तीन एल्गोरिदम ऊपर चित्रित किए गए हैं। इस स्तर पर, यह अनुमान लगाना आसान है कि कौन सा कहां है।

एल्गोरिदम एनएफएल, एफएफएल, बीएफएल

अगला फिट स्तर

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: स्तर = 0;  h (स्तर + 1) = 0;  एच = 0;  मैं = ०
  2: जबकि एक अनपैक्ड आयत है
  3: i ++
  4: यदि वर्तमान स्तर पर पर्याप्त जगह है तो
  5: पैक आयत छोड़ दिया जायज है
  6: यदि h (स्तर + 1) <h (Li) तब
  7: एच (स्तर + 1) = एच (ली)
  8: अंत अगर
  9: और [वर्तमान स्तर पर अपर्याप्त जगह है]
 10: एक नया स्तर खोलें और आयत पैक करें
 11: एच + = एच (स्तर + 1);  स्तर ++
 12: अंत यदि
 13: जबकि अंत
 14: प्रिंट एच और पूरी पैकिंग

पहले फिट का स्तर

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: स्तर = 0;  h (स्तर + 1) = h (L1);  एच = एच (एल 1);  मैं = १
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  स्तर = 0
  4: पर्याप्त स्थान के साथ निम्नतम स्तर की खोज करें
  5: यदि ऐसा स्तर मौजूद है तो
  6: पैक आयत छोड़ दिया जायज है
  7: यदि यह शीर्ष-सबसे स्तर और h (स्तर) <h (Li) है तो
  8: एच (स्तर) = एच (ली)
  9: अंत अगर
 10: बाकी [सभी मौजूदा स्तरों में अपर्याप्त जगह है]
 11: सबसे ऊपर के स्तर से ऊपर एक नया स्तर बनाएं
 12: पैक आयत को सही ठहराया
 13: एच (स्तर) = एच (ली);  एच + = एच (ली)
 14: अंत यदि
 15: जबकि अंत
 16: प्रिंट एच और पूरी पैकिंग

सबसे अच्छा फिट स्तर

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: स्तर = 0;  h (स्तर + 1) = h (L1);  एच = एच (एल 1);  मैं = ०
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  स्तर = 0
  4: न्यूनतम अवशिष्ट क्षैतिज स्थान के साथ निम्नतम स्तर की खोज करें
  5: यदि ऐसा स्तर मौजूद है तो
  6: पैक आयत छोड़ दिया जायज है
  7: और [ऐसा स्तर मौजूद नहीं है]
  8: शीर्ष-सबसे स्तर से ऊपर एक नया स्तर बनाएं
  9: पैक आयत सही छोड़ दिया
 10: एच (स्तर) = एच (ली);  एच + = एच (ली)
 11: अंत यदि
 12: जबकि अंत
 13: प्रिंट एच और पूरी पैकिंग

द्वि-स्तरीय अगला फ़िट

नेक्स्ट फिट लेवल का ट्रिकी मोडिफिकेशन। दो स्तर बनाए गए हैं, जिनमें से प्रत्येक की अपनी रणनीति है।
निचले स्तर (या सभी विषम): पहली आने वाली आयत बाएं किनारे पर पैक की जाती है, बाकी - दाएं से बाएं, जबकि पर्याप्त जगह होती है। फिर स्तर को बंद कर दिया जाता है और इसकी ऊंचाई इसमें उच्चतम आयत द्वारा निर्धारित की जाती है।
ऊपरी स्तर (या सभी संख्याएँ): यदि निचले स्तर पर केवल एक आयत है, तो स्तर निचले वाले के समान ही पैक किया जाता है। यदि दो या अधिक, पहले आयत को पट्टी के किनारों पर दबाए गए दो के निचले हिस्से पर पैक किया जाता है, और पट्टी के किनारे पर भी दबाया जाता है; बाद के सभी लोग बाएं से दाएं पैक किए जाते हैं, भले ही पहले वाला पैक सही या बाएं हो।

यह भ्रमित लगता है और यह तुरंत स्पष्ट नहीं है कि इस तरह के एक नखरे के साथ क्यों नृत्य किया जाता है। केवल एक चीज जो इस एल्गोरिदम को स्पष्ट रूप से प्रदान करती है, वह बाएं किनारे को तिरछा किए बिना, पट्टी की मात्रा पर आयतों का अधिक समान वितरण है। लेकिन हम इस रणनीति पर लौटेंगे जब हम संपीड़न एल्गोरिदम पर विचार करेंगे।

बीएनएफएल एल्गोरिथम

द्वि-स्तरीय अगला फ़िट

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: स्तर = 1;  h (स्तर) = 0;  एच = 0;  मैं = १
  2: एक नया द्वि-स्तर खोलें
  3: कॉल 'निचले स्तर पर पैक'
  4: प्रिंट एच और पूरी पैकिंग है
 प्रक्रिया 'निचले स्तर पर पैक'
  1: पैक किया गया पहला आयत न्यायसंगत है
  2: बाद में जो आयतें फिट होंगी वे सही हैं
  3: यदि अपर्याप्त स्थान है तो
  4: h (स्तर) पैक किए गए सबसे लंबे आयत की ऊंचाई द्वारा दिया गया है
  5: कॉल 'ऊपरी स्तर पर पैक'
  6: अंत अगर
 प्रक्रिया 'ऊपरी स्तर पर पैक'
  1: यदि Li + 1 पहला आयत है तो पैक किया जाता है
  2: ली के शीर्ष पर औचित्य छोड़ दिया
  3: और
  4: यदि ली + 2 पहला आयत है तो पैक किया गया है
  5: मिनट के ऊपर पैक {h (ली);  एच (ली + 1)}
  6: min {h (Li) के अनुसार औचित्य;  एच (ली + 1)}
  7: और
  8: अगर Li + j (j> 3) ऊपरी स्तर पर फिट बैठता है तो
  9: बाकि सभी आयतों को सही ठहराना
 10: बाकी [आयत फिट नहीं है]
 11: एच + = एच (कम) + एच (ऊपरी);  नया द्वि-स्तर खोलें
 12: अंत यदि
 13: अंत यदि
 14: अंत यदि

शेल्फ एल्गोरिदम

शेल्फ एल्गोरिदम आयतों की सटीक ऊंचाई से बंधा नहीं है और स्तर (शेल्फ) पर पहले एक को पैक करने के बाद, अगले एक से थोड़ा अधिक होने की स्थिति में बहुत कम जगह होती है। यह "छोटा" पैरामीटर r 0 (0; 1) द्वारा नियंत्रित किया जाता है। शेल्फ की ऊँचाई को r ^{k के} रूप में परिभाषित किया गया है, जहाँ r ^{k + 1} <h (L _i ) for r ^k कुछ पूर्णांक k और पहले पैक आयत h (L _i ) की ऊँचाई के लिए है। टियर एल्गोरिदम के समान, नेक्स्ट फिट, फर्स्ट फिट और बेस्ट फिट शेल्फ बायपास की रणनीतियां लागू होती हैं। प्रत्येक शेल्फ पर छोड़ा गया "आरक्षित" पिछले दो मामलों में लाभदायक हो जाता है (एफएफएल और एफएफएस, बीएफएल और बीएफएस की तुलना करें)। उदाहरण में, पी = 0.7।

एनएफएस, एफएफएस, बीएफएस एल्गोरिदम

अगला फिट शेल्फ

  इनपुट: आयतों के आयाम {w (ली);  एच (ली)}
        पैरामीटर r और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: शेल्फ = 1;  w (शेल्फ) = 0;
     h (शेल्फ) = r ^ k कुछ पूर्णांक k के लिए;  i = 0;  एच = एच (शेल्फ)
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  कंप्यूट k
  4: यदि पर्याप्त जगह है और r ^ (k + 1) <h (Li) there r ^ k तब
  5: पहले से पैक किए गए आयत के दाईं ओर आयत पैक करें
  6: अन्यथा [अपर्याप्त स्थान है]
  7: पिछले एक के ऊपर एक नया शेल्फ बनाएं
           और नए शेल्फ पर आयत ली पैक करें।
  8: शेल्फ ++;  एच + = आर ^ के
  9: अंत अगर
 10: जबकि अंत
 11: प्रिंट एच और पूरी पैकिंग।

पहला फिट शेल्फ

  इनपुट: आयतों के आयाम {w (ली);  एच (ली)}
        पैरामीटर r और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: शेल्फ = 1;  h (शेल्फ) = r ^ k कुछ पूर्णांक k के लिए;
     i = 0;  एच = एच (शेल्फ);  shelnum = 1
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  कंप्यूट k
  4: पर्याप्त जगह के साथ उचित ऊंचाई के सबसे कम शेल्फ की खोज करें
  5: यदि ऐसा शेल्फ मौजूद है
  6: पहले से पैक किए गए आयत के दाईं ओर आयत पैक करें
  7: और [सभी अलमारियों में अपर्याप्त स्थान है
              उपयुक्त ऊँचाई या ऐसा शेल्फ मौजूद नहीं है]
  8: सबसे ऊपरी शेल्फ के ऊपर एक नया शेल्फ बनाएं
           और नए शेल्फ पर आयत ली पैक करें।
  9: शेल्फ ++;  एच + = आर ^ के;  shelnum ++
 10: अंत यदि
 11: जबकि अंत
 12: प्रिंट एच और पूरी पैकिंग।

सबसे अच्छा फिट शेल्फ

  इनपुट: आयतों के आयाम {w (ली);  एच (ली)}
        पैरामीटर r और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: शेल्फ = 1;  h (शेल्फ) = r ^ k कुछ पूर्णांक k के लिए;
     i = 0;  एच = एच (शेल्फ);  shelnum = 1
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  कंप्यूट k
  4: सभी अलमारियों (नीचे से शुरू) को एक के लिए खोजें
        उचित ऊंचाई के साथ और न्यूनतम अवशिष्ट क्षैतिज स्थान है।
  5: यदि ऐसा शेल्फ मौजूद है
  6: पहले से पैक किए गए आयत के दाईं ओर आयत पैक करें
  7: अन्यथा [अपर्याप्त स्थान है या
              उपयुक्त ऊंचाई का कोई शेल्फ नहीं है]
  8: सबसे ऊपरी शेल्फ के ऊपर एक नया शेल्फ बनाएं
           और आयत ली को नए शेल्फ पर पैक करें।
  9: शेल्फ ++;  एच + = आर ^ के;  shelnum ++
 10: अंत यदि
 11: जबकि अंत
 12: प्रिंट एच और पूरी पैकिंग।

हार्मोनिक शेल्फ

एक स्तर पर हार्मोनिक शेल्फ पैक न केवल एक समान ऊंचाई के साथ, बल्कि एक समान चौड़ाई के साथ भी होता है। परिणाम अधिक स्तर होगा, लेकिन वे सघन भरे होंगे। अनुमेय चौड़ाई की गणना करने के लिए एक अतिरिक्त पैरामीटर एम पेश किया जाता है।

पट्टी की कुल चौड़ाई, सादगी के लिए हम इसे एक इकाई के रूप में लेते हैं, जिसे एम अंतराल I _{1 से} विभाजित किया जाता है। I _M. लेखक का दावा है कि एम का एक उचित मूल्य है [3; 12]। अंतराल की चौड़ाई सूत्र द्वारा गणना की जाती है:

;

प्रत्येक आयत के लिए, p की गणना की जाती है। ऊंचाई पैरामीटर k की गणना अपतटीय एल्गोरिदम के समान की जाती है। दो स्थितियों की जाँच की जाती है: क्या ऊंचाई आर के के किसी भी शेल्फ पर आयत के लिए एक जगह है और क्या इसके पी मैच पहले से ही वहां पैक किए गए हैं। यदि कम से कम एक पूरा नहीं होता है, तो इसके लिए एक शेल्फ बनाया जाता है, जिसमें लाठी और सबसे आरामदायक स्थितियां होती हैं। उदाहरण में, पी = 0.7, एम = 4।

एचएस एल्गोरिथ्म

हार्मोनिक शेल्फ

  इनपुट: आयतों के आयाम {w (ली);  एच (ली)}
        पैरामीटर एम, आर और स्ट्रिप चौड़ाई डब्ल्यू।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: शेल्फ = 1;  h (शेल्फ) = r ^ k कुछ पूर्णांक k के लिए;  मैं = ०
  2: जबकि एक अनपैक्ड आयत है
  3: i ++;  कंप्यूट k ऐसे कि r ^ (k + 1) <h (Li) k r ^ k
  4: p के मान की गणना करें जैसे कि 1 / (p + 1) <w (Li) value 1 / p
        जहां 1 ≤ पी <एम
  5: ऊँचाई के समतल के बीच r ^ k एक पाते हैं
        पैकिंग आयतों के साथ जिसकी चौड़ाई अंतराल अंतराल में फिट होती है
  6: यदि अपर्याप्त जगह है या ऊंचाई r ^ k का आयत नहीं है
  7: शीर्ष-सबसे अधिक शेल्फ के ऊपर उपयुक्त ऊंचाई का एक नया शेल्फ बनाया गया है
  8: शेल्फ ++
  9: अंत अगर
 10: यदि आयत ली पहले शेल्फ पर है तो
 11: एच (शेल्फ) = आर ^ के;  एच + = एच (शेल्फ)
 12: अंत यदि
 13: जबकि अंत
 14: प्रिंट एच और पूरी पैकिंग

अजर _य

स्तरों में विभाजित करने के लिए, एक निश्चित सीमा मूल्य 0 < Y <1/2 है। आयतों की चौड़ाई को पट्टी की चौड़ाई के अनुसार बढ़ाया जाता है, जिसे एक इकाई के रूप में लिया जाता है। ऊंचाई 2 ^{जे -1 -1} एच (एल _आई ) and 2 ^जे और चौड़ाई 2 ^{- एक्स -1} <एच (एल _आई ) _i 2 ^{-x के} साथ आयत एक स्तर पर पैक किए जाते हैं। यही है, स्तर कुछ पूर्णांक जे और एक सकारात्मक पूर्णांक x के लिए एक जोड़ी ( x , j ) की विशेषता है।

कम से कम Y की चौड़ाई वाले आयतों को बफर कहा जाता है और प्रत्येक को एक अलग स्तर पर पैक किया जाता है। यही है, अगर ऐसी आयत पकड़ी जाती है, तो आपको तत्काल एक नया स्तर खोलने की आवश्यकता है, इसके बराबर ऊंचाई। अन्य सभी (गैर-बफर) पहले उपयुक्त स्तर पर पैक किए जाते हैं। उपयुक्त - एक ही जोड़ी ( x , j ) के अर्थ में। यदि अचानक पर्याप्त जगह नहीं है, तो गैर-बफर आयत एक नए स्तर में पहला बन सकता है, फिर इस स्तर की ऊंचाई 2 ^जे होगी।
सामान्य तौर पर कुछ प्रकार के अस्वास्थ्यकर पदानुक्रम।
उदाहरण में, Y = 0.4।

अजार एल्गोरिथम

अजर _य

  इनपुट: आयतों के आयाम {w (ली);  एच (ली)}
        पैरामीटर Y और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: एच (स्तर) = 0;  w (स्तर) = 0;  स्तर = 0
  2: जबकि एक अनपैक्ड आयत है
  3: यदि w (Li)। Y है तो
  4: स्तर ++;  w (स्तर) = w (Li);  h (स्तर) = h (Li);  एच + = एच (स्तर)
  5: और [w (ली) <वाई]
  6: एक्स और जे की गणना करें
           2 ^ (j-1) <h (Li) j 2 ^ j और 2 ^ (- x-1) <w (ली) Li 2 ^ (- x)
  7: निम्नतम (x, j) स्तर की खोज करें
  8: यदि कोई (x, j) स्तर उपलब्ध नहीं है या ली अवरुद्ध है तो
  9: स्तर ++;  एच (स्तर) = 2 ^ जे;  एच + = एच (स्तर)
 10: w (स्तर) + = w (Li)
 11: बाकी [(x, j) स्तर उपलब्ध है और अवरुद्ध नहीं है]
 12: w (स्तर) + = w (Li)
 13: अंत यदि
 14: अंत यदि
 15: जबकि अंत
 16: प्रिंट एच और पूरी पैकिंग

संपीड़न एल्गोरिदम

संपीड़न एल्गोरिदम BiNFL पर आधारित हैं और अनिवार्य रूप से शीर्ष-स्तरीय पैकेजिंग विधि के लिए पैच हैं।
सामान्य अंतर यह है कि शीर्ष स्तर हमेशा बाएं से दाएं पैक किया जाता है।
संपीड़न भाग फ़िट: ऊपरी स्तर पर पैक किए गए प्रत्येक आयत के लिए, यह देखने के लिए जांचता है कि क्या निचले स्तर पर इसके नीचे स्थान है या नहीं। यदि आप इसे निचले स्तर पर ले जा सकते हैं, ताकि इसका हिस्सा ऊपरी स्तर पर बना रहे, तो यह चलता है (इसलिए भाग फ़िट - यह आंशिक रूप से पिछले स्तर पर "दबाया" जा सकता है)। इस तरह, दूसरे स्तर की समग्र ऊंचाई को कम किया जा सकता है। वह मौलिक रूप से पैकेजिंग को प्रभावित नहीं करता है। पहला आंकड़ा एक आयत दिखाता है जो स्तरों के बीच लटका हुआ है - इसे स्थानांतरित कर दिया गया था।
संपीड़न पूर्ण फ़िट: ऊपरी स्तर पर पैक किए गए प्रत्येक आयत के लिए, यह जांचा जाता है कि क्या यह पूरी तरह से पिछले स्तर पर शिफ्ट हो सकता है। दरअसल, अगर यह हो सकता है, तो यह स्थानांतरण है। यह हमें एक रणनीतिक लाभ देता है: इस तरह से मुक्त किया गया स्थान अगले आयत के लिए इस्तेमाल किया जा सकता है। दुर्भाग्य से, दूसरे आंकड़े में ऐसी स्थिति नहीं है, लेकिन इस पर आप दो असफल देख सकते हैं।
संपीड़न कॉम्बो: हाँ, यह पिछले दो का एक संयोजन है और, तदनुसार, उनके फायदे का एक संयोजन है। तीसरा आंकड़ा दिखाता है।

एल्गोरिदम सीपीएफ, सीएफएफ, सीसी

दबाव

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: i = 0;  ज = ०
  2: खुला नया द्वि-स्तर
  3: निचले स्तर पर पैकिंग BiNFL के समान है;  एच + = एच (लोअरवेल)
  4: यदि निचले स्तर पर एक आयत को पैक करने के लिए अपर्याप्त जगह है तो
  5: कॉल 'ऊपरी स्तर पर पैक'
  6: अंत अगर
  7: प्रिंट एच और पूरी पैकिंग
 प्रक्रिया 'ऊपरी स्तर पर पैक'
  1: जबकि एक अनपैक्ड आयत है
  2: अगर मैं and 3 और ली पहला आयत है तो पैक किया जाता है
  3: छोटे के अनुसार औचित्य
           सबसे बाएं और दाएं-सबसे बड़े आयतों में
  4: पर्याप्त जगह होने पर आयत को नीचे की ओर खिसकाएं
           और 12 पर जाएं
  5: और
  6: यदि मैं and 3 और ली दूसरा आयत है तो पैक किया जाता है
  7: सही औचित्य और 12 पर जाएं
  8: अन्यथा [आयत फिट नहीं है]
  9: एच + = एच (अपरेल);  नया द्वि-स्तर खोलें
 10: अंत यदि
 11: अंत यदि
 12: जबकि अंत

संपीड़न भाग फ़िट

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: i = 0;  ज = ०
  2: एक नया द्वि-स्तर खोलें
  3: निचले स्तर पर पैकिंग BiNFL के समान है;  एच + = एच (लोअरवेल)
  4: यदि निचले स्तर पर एक आयत को पैक करने के लिए अपर्याप्त जगह है तो
  5: कॉल 'ऊपरी स्तर पर पैक'
  6: अंत अगर
  7: प्रिंट एच और पूरी पैकिंग
 प्रक्रिया 'ऊपरी स्तर पर पैक'
  1: जबकि एक अनपैक्ड आयत है
  2: यदि h (Li)> वर्टिकलस्पेस और w (Li) Space क्षैतिज स्थान
  3: आयत ली को नीचे की ओर शिफ्ट करें;  11 पर जाएं
  4: और
  5: यदि h (Li) Li वर्टिकलस्पेस और W - w (स्तर) Li w (Li) तब
  6: बायां औचित्य;  11 पर जाएं
  7: बाकी [आयत फिट नहीं है]
  8: एच + = एच (अपरेल);  एक नया द्वि-स्तर खोलें
  9: अंत अगर
 10: अंत यदि
 11: जबकि अंत

संपीड़न पूर्ण फ़िट

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: i = 0;  ज = ०
  2: एक नया द्वि-स्तर खोलें
  3: निचले स्तर पर पैकिंग BiNFL के समान है;  एच + = एच (लोअरवेल)
  4: यदि निचले स्तर पर एक आयत को पैक करने के लिए अपर्याप्त जगह है तो
  5: कॉल 'ऊपरी स्तर पर पैक'
  6: अंत अगर
  7: प्रिंट एच और पूरी पैकिंग
 प्रक्रिया 'ऊपरी स्तर पर पैक'
  1: जबकि एक अनपैक्ड आयत है
  2: यदि h (Li) Li वर्टिकलस्पेस और w (ली) Space क्षैतिज स्थान
  3: स्लाइड आयत ली नीचे की ओर;  11 पर जाएं
  4: और
  5: यदि h (Li) Li वर्टिकलस्पेस और W - w (स्तर) Li w (Li) तब
  6: बायां औचित्य;  11 पर जाएं
  7: बाकी [आयत फिट नहीं है]
  8: एच + = एच (अपरेल);  नया द्वि-स्तर खोलें
  9: अंत अगर
 10: अंत यदि
 11: जबकि अंत

कम्प्रेशन कॉम्बो

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: i = 0;  ज = ०
  2: एक नया द्वि-स्तर खोलें
  3: निचले स्तर पर पैकिंग BiNFL के समान है;  एच + = एच (लोअरवेल)
  4: यदि निचले स्तर पर एक आयत को पैक करने के लिए अपर्याप्त जगह है तो
  5: कॉल 'ऊपरी स्तर पर पैक'
  6: अंत अगर
  7: प्रिंट एच और पूरी पैकिंग
 प्रक्रिया 'ऊपरी स्तर पर पैक'
  1: जबकि एक अनपैक्ड आयत है
  2: यदि w (Li) Space क्षैतिज स्थान
  3: स्लाइड आयत ली नीचे की ओर;  11 पर जाएं
  4: और
  5: यदि w (Li)> क्षैतिज स्थान और W - w (स्तर) Li w (Li) तब
  6: बायां औचित्य, 11 पर जाएं
  7: बाकी [आयत फिट नहीं है]
  8: एच + = एच (अपरेल);  नया द्वि-स्तर खोलें
  9: अंत अगर
 10: अंत यदि
 11: जबकि अंत

ऑनलाइन फिट

पिछले वाले की तुलना में अधिक श्रमसाध्य विधि, लेकिन अधिक उत्पादक भी। एक कार्य के ऑफ़लाइन संस्करण के लिए बर्क एल्गोरिथ्म पर आधारित है। मैं शायद कुछ पहलुओं को आकर्षित करूंगा।

पैकेजिंग प्रक्रिया के दौरान, खाली क्षेत्र बन सकते हैं, जिसे एल्गोरिथ्म पहले भरने की कोशिश करेगा। वे कैसे बना सकते हैं बाईं तरफ की तस्वीर में देखा जा सकता है। ध्यान दें कि इसके लिए आपको बैंडविड्थ के एक निश्चित प्रतिनिधित्व को संग्रहीत करने की आवश्यकता है।
एक खाली क्षेत्र से भरने के बाद, आपको दो मिल सकते हैं (या यह काम नहीं कर सकता है, आप जानते हैं)।

इसके अलावा, कई क्षेत्रों को एक बार पैकेजिंग के एक चरण के साथ बनाया जा सकता है - आयत के नीचे की जगह का लंबवत विश्लेषण किया जाता है और "चरणों" की संख्या से विभाजित किया जाता है। बीच की तस्वीर में, आयत के भरे जाने के बाद खाली क्षेत्र को दो में विभाजित करने के बाद फिर से दिखाया गया है (वैसे, यह मुझे लगता है कि इस जगह में इसे क्षैतिज रूप से विभाजित करना बेहतर होगा)।
सामान्य तौर पर, जंगल में दूर, अधिक voids। प्रत्येक चरण में, तेजी से लुप्त होती voids की बारीकी से जांच की जाती है। यहां मुझे एक और अनुकूलन दिखाई देता है: आप प्रयोग करने योग्य क्षेत्र का एक उपाय दर्ज कर सकते हैं और आपत्तिजनक त्याग सकते हैं।

यदि कोई खाली क्षेत्र उपयुक्त नहीं है, तो बर्क विधि के साथ पैकेजिंग जारी है। याद दिला दूंगा। एक ऊंचाई का नक्शा पट्टी के लिए बनाया गया है, और आयत को इस समय सबसे कम क्षेत्र पर आज़माया गया है। यदि यह वहां प्रवेश नहीं करता है, तो निम्न स्थान निकटतम चरण के स्तर पर "भरा" है, और खोज को दोहराया जाता है। तो एक संभावित स्थान को बहुत ऊपर तक धकेल दिया जा सकता है, और फिर खाली स्थान के निर्माण का एक और विकल्प है (दाएं देखें)।
खाली क्षेत्रों की पहचान करने के लिए हर कदम पर एक ही ऊंचाई के नक्शे का उपयोग किया जाता है।

सामान्य तौर पर, सब कुछ पहले ही कहा जा चुका है। पहले हम खाली क्षेत्रों में, फिर सबसे कम जगह में पैक करने की कोशिश करते हैं, और अंतिम से कम नहीं, ऊपर से, "सबसे कम जगह" का एक पतित मामला।

एल्गोरिथ्म के

ऑनलाइन फिट

  इनपुट: आयतों के आयाम {w (ली);  h (Li)} और स्ट्रिप चौड़ाई W।
 आउटपुट: ऊंचाई एच और पूरी पैकिंग।
  1: i = 0;  ज = ०
  2: एक रेखीय सारणी बनाएँ जिसके तत्वों की संख्या W के बराबर है
  3: जबकि एक अनपैक्ड आयत है
  4: i ++
  5: ली को पैक करने के लिए पर्याप्त स्थान के लिए खाली क्षेत्रों की सूची खोजें
  6: यदि w (EmptyArea) Li w (Li) और h (EmptyArea) (h (Li) तब
  7: खाली क्षेत्र में पैक आयत
  8: और
  9: यदि आयत खाली क्षेत्रों में से किसी में भी फिट नहीं होती है
 10: उपलब्ध पैकिंग चौड़ाई के लिए रैखिक सरणी खोजें
 11: अन्यथा [रैखिक सरणी में अपर्याप्त स्थान है]
 12: पैक आयत शीर्ष बाईं ओर उचित है
              सूचकांक से छोटे स्थान की ओर जाता है
 13: अंत यदि
 14: अंत यदि
 15: जबकि अंत
 16: एच = रैखिक सरणी में उच्चतम प्रविष्टि
 17: प्रिंट एच और पूरी पैकिंग

अंतभाषण

क्या हो रहा है, इसके लिए लक्ष्यहीनता की भावना को दूर करने के लिए, मैं एक क्लासिक, लेकिन एक अर्ध-सीमित पट्टी में दो आयामी पैकिंग एल्गोरिदम के आवेदन के प्रेरक उदाहरण दूंगा। यह मल्टीप्रोसेसर सिस्टम के लिए एक कार्य अनुसूचक है। क्लस्टर के लिए आधुनिक सॉफ्टवेयर में, अधिक "परिपक्व" एल्गोरिदम का उपयोग किया जाता है, लेकिन नियोजन कार्य स्वयं 2DSP तक कम हो जाता है। क्लस्टर ऑपरेशन की शर्तों के तहत, आने वाले कार्यों का प्रवाह पैकेजिंग के लिए ऑनलाइन डेटा से अधिक कुछ नहीं है: क्षैतिज आयाम - कोर की आवश्यक संख्या, ऊर्ध्वाधर - कार्य का समय। (तकनीक की भोर में सब कुछ वैसा ही है: आप कंप्यूटर की कतार में लग जाते हैं और पहले ही आगाह कर देते हैं कि आपको कितने संसाधनों की जरूरत है और आपका पंच कार्ड कब तक स्पिन होगा)। शेड्यूलर को कार्य के लिए विशिष्ट प्रोसेसर आवंटित करना चाहिए और प्रारंभ समय निर्धारित करना चाहिए। अपने शुद्ध रूप में, वैसे, कोई एल्गोरिथ्म का उपयोग नहीं किया जा सकता है, क्योंकि समय समाप्त हो रहा है, जबकि अनुसूचक किसी कार्य की प्रतीक्षा कर रहा है या अपने स्थान के बारे में सोच रहा है। इसके अतिरिक्त, एक प्रोग्रामर को विभिन्न विशिष्ट परिस्थितियों में हाथों से बाध्य किया जा सकता है: कार्यों की प्राथमिकता; रनटाइम पर कार्यों को स्केल करने की क्षमता; हार्डवेयर देरी और सिस्टम स्व-सेवा, जिसमें विफल संसाधनों पर आधारित पुनर्वितरण शामिल है; क्लस्टर की वास्तुकला के लिए कार्य के भीतर संचार की प्रकृति का मानचित्रण करना, आदि।
कोई भी एल्गोरिथ्म अपने गणितीय कठोरता में एकदम सही है, जब तक आप इसे वास्तविक जीवन में लागू करना शुरू नहीं करते।

और अंत में - एक सुखद, अवैयक्तिक रूप में एल्गोरिदम का एक तुलनात्मक विवरण। यहाँ प्राप्त करने के लिए इष्टतम पैकिंग ऊँचाई (पट्टी की चौड़ाई से विभाजित आयतों के क्षेत्रों का योग) का अनुपात है।

एनएफएल	FFL	BFL	BiNFL	एनएफएस	एफएफएस	BFS	एच एस	अजर _य	सीपीएफ	CFF	सीसी	की
0.56	0.63	0.75	0.56	0.45	0.57	0.57	0.37	0.44	0.60	0.59	0.63	0.72

कोड (Qt):
एल्गोरिदम packager.h packager.cpp
गुई window.h window.cpp renderarea.h रेंडरारिया । सीपीसी main.cpp

दो आयामी पैकेजिंग के बारे में: ऑनलाइन एल्गोरिदम