आयताकार 2 डी आकार भरें आयतों के दिए गए सेट

Question

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

यह बहुत packing problem के समान है और समस्या को कवर लेकिन क्षेत्र को कवर आयताकार नहीं लगता है ...

मुझे लगता है कि यह एनपी समस्या है, और मैं यकीन है कि वहाँ कुछ कागजात कि इसे हल करने के लिए अच्छा heuristics दिखाने होना चाहिए हूँ , लेकिन मुझे नहीं पता कि Google क्या करना है? मुझे कहां से शुरू करना चाहिए?

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

Answer 1

मुझे लगता है कि आप पैकिंग और स्वचालित लेआउट पीढ़ी एल्गोरिदम की तलाश कर सकते हैं। स्वचालित वीएलएसआई लेआउट पीढ़ी एल्गोरिदम को समान रूप से कपड़ा लेआउट प्रश्नों की तरह ही चीजों की आवश्यकता हो सकती है ...

यह पेपर Hegedüs: Algorithms for covering polygons by rectangles इसी तरह की समस्या का समाधान करता प्रतीत होता है। और चूंकि यह पेपर 1 9 82 से है, तो papers which cite this one को देखना दिलचस्प हो सकता है। इसके अतिरिक्त, this meeting इससे संबंधित अनुसंधान समस्याओं पर चर्चा कर रहा है, इसलिए इस विचार में शोध करने वाले कीवर्ड या नामों के लिए एक प्रारंभिक बिंदु हो सकता है।

मुझे नहीं पता कि कम्प्यूटेशनल ज्यामिति शोध में आपकी विशिष्ट समस्या के लिए एल्गोरिदम हैं या यदि ये एल्गोरिदम लागू करने के लिए पर्याप्त/व्यावहारिक हैं। यहां बताया गया है कि अगर मैं पिछले काम को देखने में सक्षम होने के बिना ऐसा करना चाहता हूं तो मैं उससे कैसे संपर्क करूंगा। यह सिर्फ एक दिशा है, अब तक कोई समाधान नहीं है ...

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

Answer 2

मुझे लगता है कि यह समस्या जेनेटिक एल्गोरिदम और/या विकासवादी रणनीति एल्गोरिदम के साथ हल करने के लिए उपयुक्त है। मैंने कुछ प्रकार की विकासवादी रणनीति एल्गोरिदम की सहायता से समान बॉक्स पैकिंग समस्या की है। इसे in my blog देखें।

तो अगर आप इस तरह के दृष्टिकोण का उपयोग करेगा - गुणसूत्रों में सांकेतिक शब्दों में बदलना बॉक्स:

• x निर्देशांक
• y समन्वय
• कोण

फिर

समारोह- फिटनेस कम करने की कोशिश

y = w1 * box_intersection_area + W2 * box_area_out_of_shape + w3 * average_circle_radius_in_free_space

चुनें भार w1, W2, जैसे कारकों के महत्व को प्रभावित करने के लिए डब्ल्यू 3। जब आनुवांशिक एल्गोरिदम को आंशिक समाधान मिलेगा - बॉक्स को हटाएं जो अभी भी एक साथ ओवरलैप हो या आकार से बाहर हो - और आपके पास कम से कम कानूनी (लेकिन आवश्यक इष्टतम) समाधान नहीं होगा।

इस दिलचस्प समस्या में शुभकामनाएं!

Answer 3

यह वास्तव में एनपी कठिन है और चूंकि इसमें हाई-टेक एप्लिकेशन है, इसलिए अनुमानित कार्यक्षमता अनुमानित रणनीतियों पेटेंट में भी नहीं हैं, अकेले प्रकाशित कागजात दें।

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

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

आयताकारों की कक्षाओं को परिभाषित करने पर काम जो आपकी स्कीमा के साथ अच्छी तरह से पैक करते हैं - यह पूरी प्रक्रिया को उलटा रखने के लिए फिर से है - आप जो भी आपको दिए गए हैं उसे वास्तव में फिट करने की कोशिश नहीं कर रहे हैं - आप परिभाषित कर रहे हैं कि आपको क्या देना है इसे अच्छी तरह से फर करें - फिर आप अनुमान के रूप में बाकी को पलटते हैं क्योंकि यह अनुमान है।

फिर आप थोड़ा और करने की कोशिश कर सकते हैं, लेकिन अधिक नहीं - बैकट्रैकिंग में कोई पर्ची या मनमाने ढंग से छोटी त्रुटि और यह घातीय है।

यदि आप एक शोध सुविधा में हैं और कुछ सुपरकंप्यूटर समय प्राप्त कर सकते हैं - पैथोलॉजिकल मिश्रणों के साथ संपूर्ण खोजों का एक सेट चलाएं, यह देखने के लिए कि इष्टतम पैकिंग कैसा दिख सकता है और यह देखने के लिए कि क्या आप कुछ और उप-विभाजन प्राप्त कर सकते हैं आयताकार सेट के स्कीमा और/या कक्षाएं।

यह पहले 2 साल या शोध के लिए पर्याप्त होना चाहिए :-)