Алгоритм стекирования - укладка трехмерных объектов на минимально возможную площадь

Question

Я пытаюсь решить проблему укладки объектов в наиболее удобный для почтового формата размер. Размер и форма объектов будут варьироваться. Длина, ширина и высота всех объектов известны.

Например, клиент может заказать объект (длина х ширина х высота) размером 200x100x10 см (широкий, длинный и плоский) вместе с 2 объектами размером 50x50x50 см (кубиками). Если бы я должен был упаковать это, я бы положил плоский широкий предмет внизу, а 2 кубика сверху, рядом.

Кто-нибудь имеет или знает достаточно эффективное алгоритмическое решение для этого? Или даже подход к тому, как я должен думать о решении этого. Я кодировал всю неделю, уже поздно, и мой мозг зажарен. Я еще не в отчаянии, но я просто хочу завтра отдохнуть.

То, как я это представлял, было бы создать массив, представляющий трехмерное пространство, каждый элемент массива представлял бы 1 квадрат / см в этом пространстве. Длина и ширина трехмерного пространства будут основываться на самом длинном и самом широком объекте. Затем вы просто работаете от самого большого объекта до самого маленького, находя достаточное количество «дырок» и заполняя их по мере продвижения.

Хотя я уверен, что была бы математическая формула, которая делает это намного эффективнее.

Есть идеи?

Answer 1

Первый совет - отойди от клавиатуры, перестань кодировать, начинай думать!

Второй совет - предложенный вами подход (сначала самый большой, затем следующий по величине) является хорошо уважаемой и широко используемой эвристикой для этой проблемы. И если у вас нет огромного количества вещей, которые нужно упаковать, или огромного количества упаковок, которые не нужно делать, не слишком заботьтесь об эффективности выполнения, эффективность разработки, вероятно, должна быть вашим первым приоритетом.

Третий совет - Google для упаковки в мусорное ведро, но будьте осторожны, об этом огромное количество литературы.

Наконец, не будьте настолько уверены, что для этого есть математическая формула: -)

Answer 2

Я не думаю, что это тривиально. Я считаю, что правильное название для этого - bin pack , и поиски в Google показывают много научных статей, но не содержат простых алгоритмов (особенно в 3-D, что вам и нужно).

Сколько объектов вы хотите обработать на практике? Если их относительно мало (то есть не сотни в транспортный контейнер TEU, а, возможно, несколько штук в картонную коробку для FedExing), то, возможно, лучшим подходом будет использование метода грубой силы для решения локальных максимумов.

Answer 3

Это не простая проблема, и я думаю, что это даже NP-сложная задача. Похоже, у вас есть хорошие идеи! Я бы порекомендовал почитать о проблеме Рюкзак , чтобы получить больше теории и новых идей.

Answer 4

Я не эксперт, но я думаю, что в настоящее время невозможно найти оптимальный результат без использования метода грубой силы, но я могу предложить некоторые вещи:

1) Если вы начнете упаковывать объектс наибольшим объемом в первом контейнере и вторым по величине объектом во втором контейнере, третьим по величине в первом контейнере до бесконечности, результат будет максимум 14% (или 34%? Не могу вспомнить точно!) худшийчем оптимальный результат.Я читал это где-то в книге Пола Хоффмана «Человек, который любил только цифры».

2) Генетический алгоритм должен дать вам относительно лучшие результаты за счет некоторой производительности.

Есть также такие компании, как Logen Solutions и MaxLoad , которые делают это для заработка, поэтому, если вы готовы платить, вы также можете использовать их веб-сервисы.