आयत की कमी

Question

साथ पैकिंग मैं एक (उदाहरण) आयतों के सेट पैक करने के लिए करना चाहते हैं:

ताकि कुल ऊंचाई बाधा के साथ संभव के रूप में कम है कि आयतों में समाप्त होगा उसी कॉलम में उन्होंने शुरू किया। आयताकारों को अंतिम स्थिति तक पहुंचने के लिए एक-दूसरे के माध्यम से "स्थानांतरित" करने की अनुमति है, जब तक कि वे अंत में छेड़छाड़ न करें।

हमारा वर्तमान एल्गोरिदम आयताकार को सबसे बड़ी ऊंचाई से छोटी ऊंचाई तक संसाधित करना है, और उन्हें उपलब्ध सबसे कम वाई स्थिति में रखना है। क्या कोई और इष्टतम एल्गोरिदम है?

संपादित करें: मुझे इष्टतम समाधान की आवश्यकता नहीं है, किसी भी एल्गोरिदम जो वर्तमान में से बेहतर समाधान उत्पन्न करता है, दिलचस्प है। इसके अलावा, आयताकारों की संख्या लगभग 50 है।

Answer 1

मान लें कि आपके पास N आयताकार हैं। प्रत्येक आयताकार i के लिए, [a_i, b_i] क्षैतिज अवधि बनें, और h_i ऊंचाई बनें।

आपका समाधान स्थान y_i, i = 1, ..., N जैसा दिखता है, जहां आयताकार i का लंबवत अवधि [y_i, y_i + h_i] है।

सामान्यता के नुकसान के बिना, हम y_i >= 0 को बाधित कर सकते हैं। हम फिर उद्देश्य कार्य max{y_i + h_i | i} को कम करना चाहते हैं।

की कमी गैर-अतिव्यापी आयतों के लिए आपके पास हैं:

y_i + h_i <= y_j 
    OR 
y_j + h_j <= y_i 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

जो [a_i, b_i] एक दूसरे के साथ एक दूसरे को काटना इसके बारे में पता करना आसान है, इसलिए पता लगाना है जिसके लिए आयतों इन बाधाओं के रूप में की जोड़ी आसान होना चाहिए।

से छुटकारा पाने के लिए या हमारे बाधा में, हम हर बाधा k और एक "बिग एम" M कि पर्याप्त रूप से बड़े है और फिर से लिखने के लिए द्विआधारी डमी चर z_k बना सकते हैं:

y_i + h_i <= y_j + (z_k)M 
y_j + h_j <= y_i + (1-z_k)M 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

हम एक लागू कर सकते हैं डमी वैरिएबल H और बाधाएं y_i + h_i <= H जोड़ें ताकि हम उद्देश्य कार्य को H को कम करने के रूप में पुनः लिख सकें।

जिसके परिणामस्वरूप अनुकूलन समस्या है:

minimize H 
with respect to: y_i, z_k, H 
subject to: 

(1) y_i + h_i <= y_j + (z_k)M for all i != j such that [a_i, b_i] 
    y_j + h_j <= y_i + (1-z_k)M and [a_j, b_j] intersect 

(2) y_i + h_i <= H    for all i 

(3) y_i >= 0      for all i 

(4) z_k in {0, 1}    for all constraints of type (1) k 

यह एक mixed-integer linear optimization problem है। ऐसे सामान्य समाधान हैं जो इस प्रकार की समस्या के लिए मौजूद हैं जो आप सीधे आवेदन कर सकते हैं।

आमतौर पर, वे बाधा कि [0,1] में एल्गोरिथ्म, जो एक linear programming problem में इस बदल जाता है, जो कुशलता से हल किया जा सकता बहुत दौरान हो z_k को z_k पर द्विआधारी बाधा आराम की तरह चालें प्रदर्शन करेंगे।

मैं उन हलकों को पुनर्जीवित करने की कोशिश करने की सलाह देता हूं।

Answer 2

यह देखते हुए कि आयताकार केवल लंबवत स्थानांतरित हो सकते हैं, केवल दो समाधान दिखाई देंगे: सभी आयताकारों को ऊपर की ओर ले जाना जितना आप टकराव तक हो सकते हैं, या उन्हें नीचे की ओर ले जा सकते हैं एक टकराव होने तक। मुझे एक झुकाव संदेह है कि ये समाधान समकक्ष होने जा रहे हैं *। मुझे नहीं लगता कि जब आप एक आयाम से बाध्य होते हैं तो पैकिंग की एक और अधिक परिष्कृत धारणा होती है। शायद मुझे कुछ याद आ रहा है?

* यदि मैं आपकी बाधा को सही ढंग से समझ गया हूं, तो न्यूनतम ऊंचाई हमेशा भरने वाली कोशिकाओं की सबसे बड़ी संख्या वाले कॉलम में भरी हुई कोशिकाओं की संख्या होगी। यह भिन्न नहीं होता है कि अनुवाद ऊपर या नीचे लागू किया गया है या नहीं।

Answer 3

मेरी विनम्र राय में, पहला कदम प्रत्येक स्तंभ के लिए, कम से कम आवश्यक ऊंचाई की गणना करना है। उदाहरण के रूप में अपनी तस्वीर का उपयोग करके, पहले कॉलम को कम से कम 10 की ऊंचाई की आवश्यकता होती है, जिसे लाल, हरे और छोटे नीले आयतों द्वारा योगदान दिया जाता है। यह आसानी से प्रत्येक दिए गए आयताकार के माध्यम से पुनरावृत्ति करके किया जाता है और अपने संबंधित ऊंचाई को कॉलम पर जोड़ता है। ऐसा करके, सभी "कॉलम ऊंचाई" में अधिकतम संख्या पाई जाती है, जिसे मैं इसे "स्तंभ" कहता हूं। आपकी तस्वीर में, "स्तंभ" कॉलम 8:10 पर 14 की ऊंचाई के साथ है, आयत 1,2,4,6 (नीचे से ऊपर तक गिने गए) द्वारा योगदान दिया गया है। इसका मतलब यह है कि पैकिंग की न्यूनतम ऊंचाई कम से कम "खंभे" की ऊंचाई है क्योंकि "स्तंभ" कॉलम ठोस भरा हुआ है और इसे और कम नहीं किया जा सकता है। और इन चार स्टैकिंग ऊपर रूपों में इस तरह के चित्र आयत: (गैर स्तंभ आयत नहीं दिखाया)

तब स्तंभ को दो भागों में विभाजित करता है चित्र, एक स्तंभ के बाईं और एक अन्य दूसरे पर करने के लिए क्षेत्र है पक्ष। इसके अलावा, "गैर-खंभे" आयत (आर 3,5,7,8) अलग-अलग दोनों क्षेत्रों में भी अलग-अलग स्थित हैं। एलएचएस और आर 5 पर आर 3, आर 7, आरएचएस पर आर 8।

अब बाईं ओर भाग पर विचार करें। के रूप में यह चित्र (Fig.3) में दिखाया गया है मैं स्तंभ आयतों पुन: व्यवस्थित:

पुनर्व्यवस्थित स्तंभ आयत स्टैकिंग आदेश के साथ

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

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

अंत में:
चरण 1 स्तंभ को मिल रहा है, एक आसान जवाब यहां पाया जा सकता है, तो हर दी आयत स्तंभ में शामिल है - स्तंभ की ऊंचाई कम से कम पैकिंग ऊंचाई है।

चरण 2 दोनों तरफ खंभे की जांच करना है।
केस एक: यदि एक तरफ कोई खाली आयताकार नहीं है, तो दूसरी तरफ आसानी से "सर्वोत्तम स्थिरता" विधि से भरा जा सकता है और जिसके परिणामस्वरूप न्यूनतम पैकिंग ऊंचाई फिर से खंभे की ऊंचाई होती है।

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

इस मामले में, आर 3 में फिटिंग के लिए खाली स्थान की आवश्यकता पूरी तरह से आर 6 द्वारा बनाई गई है और आर 7 और आर 2 के लिए भी बनाई गई है। इस प्रकार अन्य खंभे आयत के साथ आर 6 और आर 2 के स्टैकिंग ऑर्डर को स्वैप करने से आर 3 नहीं होगा, आर 7 अनुपयुक्त होगा यदि आर 3, आर 7 स्वैपिंग का पालन करें। कौन सा आरएचएस के लिए एक "सबसे अच्छा स्थिरता" मामले में परिणाम कर सकते हैं:

फिर आरएचएस स्तंभ ऊंचाई को पार किए बिना आरएचएस तैनात आयतों से भरा जा सकता है।
इस गैर-स्थिरता की आवश्यकता को मुक्त आयताकार की ऊंचाई की तुलना करके और खंभे आयत की ऊंचाई की तुलना करके इसकी नि: शुल्क स्थान बनाने के लिए तुलना करके पहचाना जा सकता है। यदि मुक्त आयताकार की ऊंचाई दूसरे की तुलना में बड़ी नहीं है, तो इसमें शामिल होने के लिए दूसरे स्तंभ आयत की आवश्यकता नहीं होती है जिसका अर्थ है कि इसे खाली स्थान स्थिरता की आवश्यकता नहीं है।

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

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