Оптимальное размещение маленьких коробок в большой

[semyonrsh]

Чего-то не знаю, как подступиться к задаче. Может, подскажете?

На входе имеются:
a. Одна большая обычная (прямоугольнопараллелепипедная) коробка с размерами ШхГхВ (размеры являются входящими параметрами)
b. Неограниченное количество маленьких коробок (тоже обычных) с размерами ШхГхВ (размеры являются входящими параметрами)

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

[Sonic86]

Вы ошиблись разделом - это не олимпиадная задача, а дискретная оптимизационная задача.
topic183.html - загляните сюда, здесь написано, как набирать формулы (формулы здесь обязательно набираются ТеХом).
Далее:

semyonrsh в сообщении #559367 писал(а):

Одна большая коробка с размерами ШхГхВ

и

semyonrsh в сообщении #559367 писал(а):

b. Неограниченное количество маленьких коробок с размерами ШхГхВ

Что за Г? Даже спрашивать боюсь... Но размеры Вы должны точно описать. В том смысле, что при таком описании непонятно, отличаются ли размеры большой и маленьких коробок (не отличаются же!: тут ШхГхВ и там ШхГхВ - одно и то же!)? И главное - размеры маленьких коробок все одинаковые или нет?

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

[semyonrsh]

...да, действительно сформулировал не блестяще.

По порядку:
Г - это Глубина
Все "маленькие" коробки одинаковые,
Размер маленьких коробок отличается от размера большой коробки. Думаю, лучше далее называть большую коробку "Контейнером"

Спасибо за отсылку к задаче укладки. Теоретически похоже.
Но практически все примеры, которые удалось найти с ходу - они "одномерные" - т.е. укладываеются не маленькие коробки в контейнер, а различные маленькие отрезки на большой отрезок. В этом случае вопроса "куда класть" не возникает - всегда "слева направо".

В случае 3-мерных контейнера и коробок мне кажется каким-то подозрительно непростым вопрос того, какую коробку каким образом можно уложить в контейнер при условии какой-то частичной заполненности этого контейнера. Ну не перебирать же каждый кубический миллиметр на предмет того, можно ли в него упаковать "дальний левый нижний угол" очередной коробки...
По этому поводу какая-то "стандартная" методика имеется?

[ИСН]

Хранить массив дальних левых нижних внутренних углов (первоначально таковых ровно 1, потом делается больше), тыкать коробкой в каждый из них.

[mserg]

Если мне не изменяет память, то эта задача именуется как «Плотная упаковка». Занимался ей, в частности, Саати. Может чего и нагуглите.

Коробочки можно плотно уложить в виде прямоугольного параллелепипеда (назовем это блоком) так, что ШГВ этого блока будут кратны ШГВ коробочек. Блок нужно собрать побольше, но чтобы он мог уместиться в контейнере. Возникает несколько комбинаций помещение блока «максимального размера» в контейнер, если учитывать возможность поворота блока на 90 градусов. Блок нужно задвигать в дальний левый угол контейнера. Спереди, справа и сверху может остаться свободное пространство. Его также можно попытаться заполнить блоками. С учетом порядка заполнения «спереди, справа и сверху» и поворотов блоков возникает некоторое некосмическое количество вариантов…
При большом контейнере и маленьких коробочках это почти оптимально.

Линейное программирование решает такие задачи крайне плохо. К тому же размер контейнера фиксирован, а количество коробочек, которое нужно уложить – неизвестно. Поэтому потребуется решить ряд задач линейного программирования, например, с дихотомией количества коробочек.

[temp03]

semyonrsh в сообщении #559367 писал(а):

(коробки можно вертеть не во всех 3D-направлениях, а только на 90-градусов-кратные углы во всех 3-х плоскостях)

Это бессмысленное условие. Всё равно оптимальным будет размещение под углами в 90 градусов, т.к. в прямоугольном треугольнике катеты всегда меньше гипотенузы.

В общепринятых терминах:
Пусть размеры большой коробки $(x_1,y_1,z_1)$, а размеры маленькой $(x_2,y_2,z_2)$. Тогда очевидна система равенств:
$\begin{cases} k_1x_2=x_1+m_1\\ k_2y_2=y_1+m_2\\ k_3z_2=z_1+m_3 \end{cases}$
Задача заключается в том, чтобы минимизировать свободные коэффициенты $m_1,m_2,m_3\to\min$. (или максимизировать $\sum{k_i\to\max}$).
Существует только три свободных свободных положения (степеней свободы), в которых можно уложить коробку: $x_2$ вдоль $x_1$, $x_2$ вдоль $y_1$, $x_2$ вдоль $z_1$. И на каждую из которых по две степени свободы оставшихся положений, итого: $3\cdot2=6$ способов укладки, которые надо рассмотреть.

Далее пусть $x_2<y_2<z_2$. Остаются способы, когда $m_i>x_1$ и $m_i>y_1$, т.е. дополнительные коробки можно запихать в оставшиеся щели. Заметим, что во всех 6-ти положениях размещения щели будут из себя представлять меньшие параллелепипеды, у которых одно измерение $m_i>x_2$ или $m_i>y_2$, а два других $(y_1,z_1)$, $(y_1,x_1)$ или $(x_1,z_1)$(рассматриваются также максимум два случая).
Далее исключаем все лишние случаи и получаем требуемое $\sum{k_i}+k'\to\max$, где $k'$ - количество дополнительных коробок в щелях после упаковки основных.

[mserg]

Можно еще получить более точную верхнюю оценку оптимума. Простейшая – разделить объем контейнера на объем маленькой коробки и взять целую часть. Можно прикинуть, какой объем контейнера в любом случае останется незаполненным. Для этого с длинами сторон контейнера и маленькой коробочки нужно решить задачи о рюкзаке. Так, если размеры маленькой коробочки 4x8x12, а размер контейнера 57x35x62, то не заполнение по сторонам составит как минимум 1, 3 и 2 соответственно. Т.е. верхняя граница будет 56x32x60 / 4x8x12 = 280

[ИСН]

temp03 в сообщении #559851 писал(а):

Это бессмысленное условие. Всё равно оптимальным будет размещение под углами в 90 градусов

$\begin{picture}(100,100) \put(0,0){\line(1,0){100}} \put(0,0){\line(0,1){100}} \put(100,0){\line(0,1){100}} \put(0,100){\line(1,0){100}} \put(0,10){\line(1,1){90}} \put(10,0){\line(1,1){90}} \put(10,0){\line(-1,1){10}} \put(100,90){\line(-1,1){10}} \end{picture}$

[semyonrsh]

temp03 в сообщении #559851 писал(а):

В общепринятых терминах:
Пусть размеры большой коробки $(x_1,y_1,z_1)$, а размеры маленькой $(x_2,y_2,z_2)$. Тогда очевидна система равенств:
$\begin{cases} k_1x_2=x_1+m_1\\ k_2y_2=y_1+m_2\\ k_3z_2=z_1+m_3 \end{cases}$
Задача заключается в том, чтобы минимизировать свободные коэффициенты $m_1,m_2,m_3\to\min$. (или максимизировать $\sum{k_i\to\max}$).

Задача сложнее - в некоторых случаях если коробки повертеть в разных направлениях, то можно добиться более оптимальной укладки

mserg в сообщении #559782 писал(а):

Коробочки можно плотно уложить в виде прямоугольного параллелепипеда (назовем это блоком) так, что ШГВ этого блока будут кратны ШГВ коробочек. Блок нужно собрать побольше, но чтобы он мог уместиться в контейнере. Возникает несколько комбинаций помещения блока «максимального размера» в контейнер, если учитывать возможность поворота блока на 90 градусов. Блок нужно задвигать в дальний левый угол контейнера. Спереди, справа и сверху может остаться свободное пространство. Его также можно попытаться заполнить блоками. С учетом порядка заполнения «спереди, справа и сверху» и поворотов блоков возникает некоторое некосмическое количество вариантов…
При большом контейнере и маленьких коробочках это почти оптимально.

Спасибо, по поводу составления блоков - у меня тоже появилась такая идея. Только оптимальной может быть комбинация из некоторого количества различных "блоков", по-разному повернутых.


В общем, судя по всему задача сводится к:
1. Перебору на каждом шаге всех возможных блоков и их "ориентаций" (это несложно)
2. Перебору на каждом шаге всех возможных "нижних левых дальних" углов, в которые можно попытаться вставить каждый из блоков (вот это - какая-то довольно непростая задача, в которой, думаю, вылезет куча различных нюансов, каждый из которых нужно мелочно обсчитать)
3. Выбору оптимального размещения из перебираемых вариантов

Всем большое спасибо за комментарии.
Осталось собраться с силами в свободное от работы время... :)

[mserg]

Линейное программирование позволяет с помощью псевдобулевых переменных описать и ориентацию коробочек, и их непересекаемость в пространстве друг с другом. Т.е. математическая постановка задачи, решение которой дает глобальный оптимум, существует. Если коробочек всего несколько штук – то глобальный оптимум найти реально. Но все это не работает, если коробочек будет больше чем несколько штук, так как наступает «комбинаторная смерть» «частично-целочисленного линейного программирования».

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

[temp03]

semyonrsh в сообщении #560555 писал(а):

Задача сложнее - в некоторых случаях если коробки повертеть в разных направлениях, то можно добиться более оптимальной укладки

Нельзя. И случай приведённый ИСН не пример.

[Sender]

temp03 в сообщении #560619 писал(а):

Нельзя. И случай приведённый ИСН не пример.

В самом деле?



Кстати, сейчас заметил, что рядом с картинкой есть и описание парочки алгоритмов, правда, для двумерного случая.

[mserg]

В интернете преобладают программы-симулякры. Делается некоторый алгоритм на простых эвристиках. Потом к нему подбираются специальные примеры, дающие оптимальный результат. И это выставляется в интернет. Так, пример выше имеет признаки искусственного конструирования и он с высокой вероятностью является частью «симулякризации».

Чтобы не попасть впросак, нужно иметь библиотечку примеров, на которых можно оценивать общую реальную эффективность интернет-творений и сравнивать их друг с другом. Да и для своих творений тоже нужна библиотека. Это, конечно, актуально, если речь идет о реальном приложении, а не об учебном.

[ИСН]

Не пример? Хе-хе. "Примеров нет, сказал мудрец брадатый."

[Sonic86]

(Оффтоп)

mserg в сообщении #560666 писал(а):

В интернете преобладают программы-симулякры. Делается некоторый алгоритм на простых эвристиках. Потом к нему подбираются специальные примеры, дающие оптимальный результат. И это выставляется в интернет. Так, пример выше имеет признаки искусственного конструирования и он с высокой вероятностью является частью «симулякризации».

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

ИСН в сообщении #560708 писал(а):

Не пример? Хе-хе. "Примеров нет, сказал мудрец брадатый."

+1!