스태킹 알고리즘 - 가능한 한 가장 작은 영역에 3d 객체를 스택하십시오.

Question

나는 우표를 가장 편리한 크기로 스태킹하는 문제를 해결하려고합니다. 개체의 크기와 모양은 다양합니다. 모든 객체의 길이, 너비 및 높이를 알고 있습니다.

예를 들어 고객은 2 개의 50x50x50cm 개체 (큐브)와 함께 (길이 x 너비 x 높이) 200x100x10cm 개체 (넓고 긴 평면)를 주문할 수 있습니다. 내가 이것을 포장해야한다면, 바닥에 평평한 넓은 물체와 나란히 2 개의 입방체를 놓을 것입니다.

누가 합리적으로 효율적인 알고리즘 솔루션을 가지고 있습니까? 아니면 내가이 문제를 해결하려고 생각하는 방식에 대한 접근법 일 수도 있습니다. 나는 일주일 내내 코딩을하고 있었고, 늦었고 뇌가 튀었습니다. 나는 아직 절망하지 않지만 내일은 쉬고 싶다.

나는 3 차원 공간을 나타내는 배열을 만들 것입니다. 각 배열 요소는 그 공간에서 1 평방/cm를 나타냅니다. 3D 공간 길이와 너비는 가장 긴 오브젝트와 가장 넓은 오브젝트를 기반으로합니다. 그런 다음 가장 큰 개체에서 가장 작은 개체까지 작업하고 충분한 '구멍'을 찾고 이동하면서 채울 수 있습니다.

나는 이것을 훨씬 더 효율적으로하는 수학 공식이있을 것이라고 확신하지만.

아이디어가 있으십니까?

Answer 1

이것은 쉬운 문제가 아니며 NP 하드라고 생각합니다. 그래도 멋진 아이디어가있는 것 같습니다! 더 많은 이론과 새로운 아이디어를 얻으려면 Knapsack problem에 대한 정보를 읽는 것이 좋습니다.

Answer 2

나는 이것이 사소한 것이라고 생각하지 않습니다. 나는 이것에 대한 적절한 이름이 bin packing이라고 믿으며 Google 검색은 많은 학술 논문을 공개하지만 간단한 알고리즘은 없다 (특히 3-D에서 원하는 것).

실제로 처리 할 대상 개체는 몇 개입니까? 비교적 적은 양 (예 : TEU 운송 컨테이너에 수백 개가 아닌 페덱스의 골판지 상자에 몇 개가 아닌 경우), 로컬 맥시마 솔루션에 대한 간단한 무차별 대입 접근이 가장 좋은 방법 일 수 있습니다.

Answer 3

첫 번째 조언 - 키보드에서 멀리 떨어져서 코딩을 중지하고 생각을 시작하십시오!

두 번째 조언 - 제안 된 접근법 (가장 큰 것부터 큰 것)은이 문제에 대해 잘 평가되고 많이 사용됩니다. 팩할 엄청난 수의 패킹 또는 엄청난 수의 패킹이 없으면 실행 효율성에 너무 관심을 두지 말고 개발 효율성을 최우선으로 고려해야합니다.

제 3의 충고 - 빈 포장을위한 Google이 경고하지만, 이에 대한 많은 양의 문헌이 있습니다.

마지막으로, 나는 전문가가 아니에요이 :-)

Answer 4

에 대한 수학 공식이 너무 확신 할 수 있지만, 나는 그것이 무력을 사용하지 않고 최적의 결과를 찾을하실 수 없습니다 생각하지 않습니다 접근 방식이지만, 몇 가지 제안 할 수 있습니다 :

1) 첫 번째 컨테이너에서 가장 큰 볼륨으로 두 번째로 큰 객체를 두 번째 컨테이너에서 패킹하기 시작하면 첫 번째 컨테이너 광고에서 세 번째로 큰 값인 무한 결과는 최적의 결과보다 최악의 경우 14 % (또는 34 %인지 정확히 기억할 수 없는가?)입니다. 폴 호프만 (Paul Hoffman)이 저술 한 "숫자 만 좋아했던 사람"이라는 책에서이 책을 읽었습니다.

2) 유전자 알고리즘은 성능을 저하시키면서 상대적으로 더 나은 결과를 제공해야합니다.

생활을 위해 Logen Solutions 및 MaxLoad과 같은 일부 회사가 있습니다. 따라서 기꺼이 지불하려는 경우 웹 서비스를 사용할 수도 있습니다.