कॉम्पैक्ट प्रतिनिधित्व

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

-r1- 
    -r2-- 
    -r3-- 
     -r4- 
     -r5--

कुछ ऐसा।

-r1- -r3-- 
    -r2-- -r4- 
     -r5--

सभी संकेतों की सराहना की जाएगी। मैं जरूरी नहीं कि "सर्वोत्तम" समाधान ढूंढ रहा हूं।

स्रोत

2008-09-30 stephanea

तो मूल रूप से आप एक आयत खींचने के लिए पहली उपलब्ध वाई-स्थिति निर्धारित करना चाहते हैं? – Jasper

क्या आप उन्हें पैक करना चाहते हैं, या उन्हें पैक करना चाहते हैं? –

एक्स स्थिति की तरह दिखता है अपरिवर्तनीय है लेकिन वाई स्थिति है? – Mauro

ऐसा कुछ?

क्रमबद्ध एक्स स्थिति से आयतों की अपने संग्रह
एक विधि है कि जाँच करता है जो आयतों के संग्रह से अधिक
```
Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){ 
... 
} 
```

पाश x- अक्ष की एक निश्चित अंतराल पर मौजूद हैं बारे में आयतों

Collection<Rectangle> toDraw; 
Collection<Rectangle> drawn; 
foreach (Rectangle r in toDraw){ 
Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn); 
int y = 0; 
foreach(Rectangle overlapRect in overlapping){ 
y += overlapRect.height; 
} 
drawRectangle(y, Rectangle); 
drawn.add(r); 
}

स्रोत

2008-09-30 14:41:04 Jasper

आप 4 रिक्त स्थान के साथ प्रत्येक पंक्ति को शुरू करके कोड प्रारूपित कर सकते हैं। – Roel

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

मेरे आयत सभी समान ऊंचाई नहीं हैं, और एक्स-निर्देशांक वास्तव में स्थानिक हैं, कोई अस्थायी निर्देशांक नहीं हैं, लेकिन आप सही हैं कि यह समस्या के लिए कुछ भी नहीं बदलता है। – stephanea

आपकी समस्या एक सरल संस्करण है, लेकिन आपको "बिनपैकिंग" समस्या के लिए विकसित हेरिस्टिक के बारे में कुछ सुझाव मिल सकते हैं। इसके बारे में बहुत कुछ लिखा गया है, लेकिन this page एक अच्छी शुरुआत है।

स्रोत

2008-09-30 14:44:35 twk

मैंने पहली बार आपको वोट दिया लेकिन सवाल फिर से पढ़ना, अगर उसके एक्स-निर्देशांक सेट हैं तो उनके पास एनपी-हार्ड समस्या नहीं है। इस पर निर्भर करता है कि आयत की ऊंचाई समान है, इसे जैस्पर के एल्गोरिदम जैसे कुछ हल किया जा सकता है। – Roel

आप पूरी तरह से सही हैं - मैंने तदनुसार अपना जवाब संपादित कर लिया है। – twk

अपनी वेबसाइट में एक टेट्रिस-जैसी गेम डालें। अपने पैरामीटर के आधार पर गिरने वाले ब्लॉक और प्ले क्षेत्र का आकार उत्पन्न करें। उनके डिजाइन के कॉम्पैक्टनेस (कम मुक्त स्थान = अधिक अंक) के आधार पर खिलाड़ियों को पुरस्कार अंक। अपने वेबसाइट आगंतुकों को आपके लिए काम करने के लिए प्राप्त करें।

स्रोत

2008-09-30 14:44:37 Kibbee

वितरित कंप्यूटिंग अपने सर्वश्रेष्ठ पर :) चलिए इसे 'मानव मस्तिष्क बादल' कहते हैं :) – Roel

यह एक अच्छा समाधान हो सकता है, लेकिन मुझे संदेह है कि पर्याप्त समय के साथ मुझे पर्याप्त श्रमिक मिलेंगे। धन्यवाद। – stephanea

आयताकार सभी एक ही ऊंचाई हैं? यदि वे हैं, और समस्या यह है कि प्रत्येक आयत को किस पंक्ति में रखना है, तो समस्या के आयत के सभी जोड़ों (एक्स, वाई) के ऊपर की बाधाओं की श्रृंखला में उबाल जाता है "आयताकार एक्स एक ही पंक्ति में नहीं हो सकता है आयताकार वाई "आयताकार एक्स के साथ एक्स-दिशा में आयताकार वाई

इस के लिए एक 'लालची' एल्गोरिदम आयत से बाएं से दाएं आयताकार करता है, फिर प्रत्येक आयताकार को निम्नतम संख्या वाली पंक्ति में बदल देता है जिसमें यह फिट बैठता है। चूंकि आयतों को बाएं से दाएं से संसाधित किया जा रहा है, इसलिए केवल इस बारे में चिंता करने की ज़रूरत है कि वर्तमान आयताकार का बायां हाथ किनारा किसी अन्य आयताकार को ओवरलैप करेगा, जो कुछ हद तक ओवरलैप पहचान एल्गोरिदम को सरल बनाता है।

मैं साबित नहीं कर सकता कि यह इष्टतम समाधान देता है, लेकिन दूसरी तरफ किसी भी काउंटररेक्समल्स को किसी भी तरह से नहीं सोचा जा सकता है। किसी को?

स्रोत

2008-09-30 15:05:43

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

Topcoder इस समस्या के 3 डी संस्करण को हल करने के लिए एक प्रतियोगिता थी। विजेता ने अपने दृष्टिकोण here पर चर्चा की, यह आपके लिए एक दिलचस्प पढ़ा जा सकता है।

स्रोत

2008-09-30 16:50:34 paxos1977

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

अब समस्या आयताकारों के एक सेट को वाई-निर्देशांक असाइन करना है जिनके एक्स-निर्देशांक दिए गए हैं, अगर मैं आपको सही ढंग से समझता हूं।

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

स्रोत

2010-06-22 02:08:36 Eric

कॉम्पैक्ट प्रतिनिधित्व

उत्तर

संबंधित मुद्दे