वस्तु पोजिशनिंग एल्गोरिथ्म

Question

मैं अगर वहाँ इस समस्या के लिए एक "इष्टतम" समाधान सोच रहा हूँ। अब मैं बिना किसी ओवरलैपिंग के इस स्थान में क्यू (समान आकार) नई ऑब्जेक्ट्स रखना चाहता हूं।

एल्गोरिथ्म मैं के साथ आया था:

1. सरणी बनाएं [] [] आकार [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. पी से सभी तत्वों और प्रत्येक के लिए दोहराएं साथ:

   mark all fields in A[][] as occupied, where the element "lies"

3. क्यू से सभी तत्वों को उन स्थानों पर रखें जहां ए [] [] में फ़ील्ड चिह्नित नहीं हैं

(लड़के, मुझे आशा है कि मुझे लगता है कि समझ में आता है कर सकता है ...)

वहाँ यह करने के लिए किसी भी बेहतर तरीका है? आपकी किसी भी मदद के हम दिल से आभारी होंगे!

Answer 1

इंटरनेट में एक संक्षिप्त खोज से, ऐसा लगता है कि इष्टतम आयताकार पैकिंग NP-hard समस्या है। मुझे लगता है कि अकादमिक में स्मार्ट लोगों को इसके लिए कुछ अनुमानित एल्गोरिदम मिले, इसलिए यह googling के लिए एक विकल्प है।

लेकिन मैं पहले सरल विधि काम करने के लिए कोशिश करेंगे: उनके चौड़ाई

करने के लिए उन्हें सबसे बड़ी से छोटी से छोटी करने के लिए पंक्ति-दर-पंक्ति डालने का प्रयास करें अनुसार

1. फूट डालो आकारों में अपना वस्तुओं।

मेरा अनुमान है कि कई मामलों में यह निष्क्रिय समाधान काम करेगा।

Answer 2

मुझे पता है कि यह आपके प्रश्न का एक विशिष्ट उत्तर नहीं है, लेकिन यह graphviz स्रोत कोड में शोध और/या खोदने के लिए उपयोगी हो सकता है। ग्राफ़विज़ ने नीटो समेत कई लेआउट मॉडल प्रदान किए हैं, जो वैश्विक ऊर्जा कार्य को कम करने का प्रयास करते हैं।

विकिपीडिया में force-base algorithms के लिए कुछ छद्म कोड है।

Answer 3

यदि मैं प्रश्न समझता हूं, तो ऐसा लगता है कि आप "इष्टतम" बिन पैकिंग एल्गोरिदम (उर्फ द नाप्सैक समस्या) की तलाश में हैं। यह एक एनपी-पूर्ण समस्या है, हालांकि आपका वर्णन ऐसा लगता है कि आप शायद इष्टतम समाधान के लिए अपना रास्ता मजबूर कर सकते हैं।