भरें मेरे पास कुछ आयाम लंबाई, चौड़ाई, ऊंचाई वाला बॉक्स है।वॉल्यूम एल्गोरिदम
मेरे पास अलग-अलग लंबाई, चौड़ाई, ऊंचाई के साथ आइटम हैं।
क्या कोई मौजूदा एल्गोरिदम है जो बॉक्स के अंदर रखने के लिए उपयोग करने के लिए सर्वोत्तम आइटम निर्धारित कर सकता है?
भरें मेरे पास कुछ आयाम लंबाई, चौड़ाई, ऊंचाई वाला बॉक्स है।वॉल्यूम एल्गोरिदम
मेरे पास अलग-अलग लंबाई, चौड़ाई, ऊंचाई के साथ आइटम हैं।
क्या कोई मौजूदा एल्गोरिदम है जो बॉक्स के अंदर रखने के लिए उपयोग करने के लिए सर्वोत्तम आइटम निर्धारित कर सकता है?
इसे बिन पैकिंग/कटिंग स्टॉक/नैप्सैक समस्या कहा जाता है, और यह एनपी हार्ड है। सामान्य तौर पर आप केवल heuristics का उपयोग करके एक अनुमानित समाधान प्राप्त कर सकते हैं,
http://en.wikipedia.org/wiki/Knapsack_problem
यह उनमें से नहीं है। क्या आप इसके लिए कोई अनुमान लगा सकते हैं? –
ये सभी एल्गोरिदम कम से कम एक आयाम, स्थान में असंबद्ध अनुकूलित करने में आपकी सहायता करते हैं। परिमित बॉक्स आयाम दिए गए उपलब्ध वस्तुओं से सर्वोत्तम फिट चुनने के लिए क्या आवश्यक है। –
यह शायद उनमें से कोई भी बिल्कुल मेल नहीं खाता है। लेकिन वे सभी कड़े से जुड़े हुए हैं। जैसे एक बिन के साथ एक बिन पैकिंग एक और समस्या बन जाती है। कड़वाहट में इस तरह की समस्या को आमतौर पर "तीन आयामी पैकिंग समस्या" कहा जाता है। एक विद्वान खोज बहुत सारे परिणाम देता है http://scholar.google.com/scholar?q=box+packing+problem –
उदाहरण के लिए देखें यह शायद वास्तव में एक जवाब नहीं है, लेकिन मेरा मानना है कि इस सवाल का जवाब है कि समस्या असंभव है। हां, यह एक पैकिंग समस्या का एक संस्करण है। लेकिन 2 आयामों में एरिच फ्रेडमा के शोध पर एक नज़र डालें: ऐसा लगता है कि वर्ग में बराबर आकार के आयताकारों की समस्या अभी भी अनसुलझा है - इनमें से कुछ समाधानों की जटिलता को देखें!
http://www2.stetson.edu/~efriedma/squinsqu/
http://www2.stetson.edu/~efriedma/rigidrect/
(समस्या कुछ अलग ढंग से पेश किया जाता है, यानी कैसे सबसे अच्छा कम से कम अंतरिक्ष पर कब्जा करने के लिए मदों की एक निश्चित संख्या की व्यवस्था करने, के रूप में चुनने जो आइटम के लिए विरोध किया। लेकिन मैं आपकी समस्या को उम्मीद वस्तुओं के कई संयोजनों से अधिक गणना इस तरह की पुनरावृत्ति को कम कर देता है)
और एक 3 डी संस्करण है जो केवल बहुत आंशिक रूप से हल दिखता है:। http://www2.stetson.edu/~efriedma/cubincub/
संभवतः आपकी सर्वश्रेष्ठ शर्त एक ह्युरिस्टिक है क्योंकि एंडर्स सुझाव देते हैं, हालांकि यह लगभग हर समस्या के लिए लगभग निश्चित रूप से उपमहाद्वीप होगा। दिलचस्प बात यह है कि, सबसे इष्टतम समाधान अत्यधिक अनियमित दिखाई देते हैं, इसलिए शायद आप उन्हें नहीं ढूंढ पाएंगे।
बॉक्स फॉर्म में Knapsack समस्या? –
यह टीसीओ की मैराटन मैच समस्याओं में से एक था, अगर आपने टीसीओ में पंजीकृत किया है तो आप इसके लिए एक अच्छा समाधान ढूंढ सकते हैं (मुझे बिल्कुल पता नहीं है कि मुझे एक साल पहले क्या लगता है)। समाधान का कोई भी सटीक उत्तर नहीं है, वे सभी अनुरूपित एनीलिंग और एसएचएच का उपयोग करने की कोशिश करते हैं। –