2009-10-13 15 views
9

मैं किसी भी 3 डी बिन पैकिंग एल्गोरिदम के लिए एक निर्धारिक कार्यान्वयन की तलाश में हूं, यानी एक या कई बड़े लोगों के अंदर कई छोटे और अलग क्यूबोइड पैक करने के लिए। समाधान इष्टतम से भिन्न हो सकता है।3 डी बिन पैकिंग एल्गोरिदम

यह सी, सी ++, जावा, सी #, आयरनपीथन, आयरन रूबी या किसी अन्य भाषा में लिखा जा सकता है जो नेट कोड से है।

मुझे यह सी एल्गोरिदम http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c मिला, लेकिन यह सबसे अच्छा फिट खोजने के लिए क्यूबोइड घुमाता नहीं है। मैं उन्हें उल्टा घुमाने के साथ ठीक हूं, लेकिन क्षैतिज घूर्णन संभव होना चाहिए।

+0

@Mouk: क्या यह होमवर्क है? – Asaph

+4

आप दावा करते हैं कि आप एक एल्गोरिदम खोज रहे हैं, लेकिन फिर आप प्रोग्रामिंग भाषाओं की सूची बनाते हैं। क्या आप एक सामान्य एल्गोरिदम या कार्यान्वयन की तलाश में हैं? –

+0

क्या आप इष्टतम समाधान चाहते हैं, या वह बहुत अच्छा है? क्या cuboids सभी समान हैं? जब आप रोटेशन कहते हैं, तो क्या आपका मतलब 90 डिग्री, या कोई कोण है? – Beta

उत्तर

8

मैंने सी ++ में ऑर्थोगोनल रोटेशन के साथ यानी 3 डी आयताकार बक्से का वर्णन करने वाले मामले के लिए अनुमानित एल्गोरिदम लिखा है। आप प्रकाशित समाचार पत्र में परिणाम और कलन विधि पा सकते हैं: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

+3

क्या स्रोत या सी ++ ऐप कहीं भी ऑनलाइन उपलब्ध है? –

+0

यह एक साधारण समाधान के लिए अच्छा है लेकिन वास्तव में यह सब ठीक से काम नहीं करता है। किसी के लिए स्पष्टीकरण चाहते हैं और एक लिखने में मदद करने के लिए मैं इस पुस्तक का सुझाव देता हूं: मार्टेलो और टोथ द्वारा नॅपैकैक समस्याएं, आईएसबीएन: 0471924202 – ars265

1

यह समस्या एनपी-हार्ड है। आपकी सबसे अच्छी शर्त एक अनुमानित एल्गोरिदम है (जब तक कि एक प्रतिभा व्यक्ति किसी भी एनपी समस्या को हल नहीं करता है, या एक बहुत भाग्यशाली साथी समाधान में ठोकर खा जाता है।) दुर्भाग्य से इस समस्या के लिए मुझे किसी भी अच्छी तरह से अनुमानित एल्गोरिदम पता नहीं है।

+3

बहुपद समय में एक एनपी-पूर्ण समस्या को हल करने से आपको अभी भी एनपी-हार्ड समस्याओं का बहुपद समाधान नहीं मिलेगा :) –

1

मैं जावास्क्रिप्ट को wknechtel/3d-bin-pack सी कोड बदल दिया। सी # को आसानी से पोर्ट किया जा सकता है।

https://github.com/keremdemirer/3dbinpackingjs

आप index.html फ़ाइल से उदाहरण गणनाएं और उत्पन्न रिपोर्ट की समीक्षा कर सकते हैं। pack1.js फ़ाइल में ऐप और एल्गोरिदम शामिल है। मुझे यकीन नहीं है कि एल्गोरिदम कैसे काम करता है लेकिन परिणाम पैकेजिंग गणनाओं के लिए संतोषजनक हैं।

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