Прямоугольник упаковки с ограничениями

Question

Я хочу, чтобы упаковать набор прямоугольников (пример):

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

Наш текущий алгоритм состоит в том, чтобы обрабатывать прямоугольники от наибольшей высоты до наименьшей высоты и помещать их в самое низкое положение y, которое доступно. Существует ли более оптимальный алгоритм?

EDIT: Мне не обязательно нужно оптимальное решение, интересен любой алгоритм, который генерирует лучшее решение, чем текущее. Кроме того, число прямоугольников составляет около 50.

Answer 1

Предположим, у вас есть N прямоугольники. Для каждого прямоугольника i, пусть [a_i, b_i] будет горизонтальным пролетом, и пусть h_i будет высотой.

Ваше пространство для решения выглядит как y_i, i = 1, ..., N, где вертикальный диапазон прямоугольника i - [y_i, y_i + h_i].

Без ограничения общности можно ограничить y_i >= 0. Затем мы хотим свести к минимуму объективную функцию max{y_i + h_i | i}.

Ограничения у вас есть для непересекающихся прямоугольников:

y_i + h_i <= y_j 
    OR 
y_j + h_j <= y_i 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

Выяснение которые [a_i, b_i] пересекаются друг с другом легко, поэтому выяснить, для каких пар прямоугольников, чтобы сформировать эти ограничения должны быть простыми.

Чтобы избавиться от OR в нашем ограничении, мы можем создать бинарный переменные фиктивные z_k для каждого ограничения k и «Больших М» M, достаточно большие и перепишет:

y_i + h_i <= y_j + (z_k)M 
y_j + h_j <= y_i + (1-z_k)M 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

Мы можем ввести фиктивная переменная H и добавьте ограничения y_i + h_i <= H, чтобы мы могли переписать объектную функцию как минимизирующую H.

В результате проблема оптимизации:

minimize H 
with respect to: y_i, z_k, H 
subject to: 

(1) y_i + h_i <= y_j + (z_k)M for all i != j such that [a_i, b_i] 
    y_j + h_j <= y_i + (1-z_k)M and [a_j, b_j] intersect 

(2) y_i + h_i <= H    for all i 

(3) y_i >= 0      for all i 

(4) z_k in {0, 1}    for all constraints of type (1) k 

Это mixed-integer linear optimization problem. Существуют общие решатели, которые существуют для этого типа проблем, которые вы можете применить напрямую.

Как правило, они будут выполнять трюки, как расслабляющий двоичное ограничение на z_k с тем ограничением, что z_k быть в [0,1] в ходе алгоритма, который превращает это в linear programming problem, которая может быть решена очень эффективно.

Я бы не советую попытаться изобрести эти решатели.

Answer 2

Учитывая, что прямоугольники могут перемещаться только вертикально, будут отображаться только два решения: перемещение всех прямоугольников как можно дальше до столкновения или перемещение их вниз пока не произойдет столкновение. У меня есть подозрение, что эти решения будут эквивалентны *. Я не могу думать, что существует гораздо более сложное понятие упаковки, когда вы ограничены одним измерением. Может, я что-то упустил?

* Если я правильно понял ваше ограничение, минимальная высота всегда будет числом заполненных ячеек в столбце с наибольшим количеством заполненных ячеек. Это не зависит от того, применяется ли перевод вверх или вниз.

Answer 3

По моему скромному мнению, первым шагом является вычисление для каждого столбца наименее требуемой высоты. Используя изображение в качестве примера, для первого столбца требуется, по меньшей мере, высота 10, что обеспечивается красными, зелеными и маленькими синими прямоугольниками. Это легко сделать путем итерации через каждый заданный прямоугольник и добавления их соответствующей высоты к столбцам, которые он занимает. Таким образом, максимальное число во всей «высоте столбца» найдено, что я называю «столпом». На вашей фотографии «столп» находится в столбце 8:10 с высотой 14, внесенный прямоугольником 1,2,4,6 (пронумерованный снизу вверх). Это означает, что минимальная высота упаковки составляет, по меньшей мере, высоту «столба», поскольку столбцы «столба» заполнены сплошным слоем и не могут быть дополнительно уменьшены. И укладка эти четыре прямоугольника вверх формирует такую ​​картину: (не-столп прямоугольник не показан)

Тогда столб делит изображение на две части, одна область слева от стойки, а другой на другой боковая сторона. Кроме того, прямоугольники «без столба» (R3,5,7,8) отдельно расположены также в двух областях. R3, R7 на LHS и R5, R8 на RHS.

Теперь рассмотрим первую часть левой части. Я переставил столп прямоугольниками, как показано это на рисунке (Рис.3):

С перестроенной столп прямоугольника порядка наложения, хотя у меня нет жесткого доказательства, вполне возможно, что независимо от того, что формы и то, что число прямоугольников расположено на LHS столба, все указанные прямоугольники могут вписываться в пустое пространство на LHS (ограничение здесь состоит в том, что эти прямоугольники не могут дать более высокий опорный столб, иначе шаг 1 уже обнаружил бы и использовал бы его как фактический столп). Эта компоновка дает пустому пространству на LHS лучшую «пространственную согласованность», что означает, что пустое пространство, созданное каждым прямоугольником столбца, укладывается в порядке возрастания снизу вверх. Эта «согласованность» позволяет пустым пространствам, созданным каждым прямоугольником столбца, «работать вместе», а затем содержать перетаскивания, которые выше, чем любое пустое пространство, созданное прямоугольником одиночной колонны. Например, зеленый прямоугольник на следующем рисунке подходит для использования пустого пространства, созданного синим и фиолетовым прямоугольником вместе.

Предполагая, что утверждения выше верно, то прямоугольники, расположенные на LHS никогда не будет делать больший стек, чем колонны. Однако, если эти перегородки требуют какого-либо сотрудничества между пустым пространством, чтобы вписаться в LHS, тогда они фактически ограничивают возможность свопинга для прямоугольников столбцов. Например, пример fig.3, зеленый прямоугольник требует, чтобы фиолетовый и синий были соседними, чтобы вписаться, однако, чтобы получить лучшую согласованность пространства в RHS, пурпурный цвет должен проходить между фиолетовым и синим.Это означает, что зеленый цвет на LHS делает невозможным получение наилучшей консистенции для RHS и, следовательно, позволяет иметь прямоугольники, расположенные на RHS, не может помещаться в пустое пространство и вызывать стопку с отверстиями и превышает высоту, установленную стойкой. Извините, что здесь я не могу придумать такой случай, но он определенно имеет значение.

В заключение:
Шаг 1 - найти столп, один простой ответ можно найти здесь, если каждый прямоугольник задействован в столбе - высота столба - минимальная высота упаковки.

Шаг 2 - изучить обе стороны до стойки.
case a: Если одна сторона не имеет свободного прямоугольника, то другая сторона может быть легко заполнена методом «наилучшей согласованности», и в результате минимальная высота упаковки снова равна высоте столба.

case b: Если одна сторона не требует согласованности свободного пространства, то эта сторона может быть заполнена, а другая сторона все еще может использовать «наилучшую согласованность». Например: (исходное изображение)

В этом случае пустое пространство, требуемое для установки в R3, создается только R6 и то же для R7 и R2. Таким образом, замена порядка укладки R6 и R2 другим прямоугольником столбца не сделает R3, R7 непригодным, если R3, R7 следует за заменой. Что может привести к «лучшая консистенции» случай для РИТ:

Тогда RHS может быть заполнен с ОРЗ, расположенными прямоугольниками, не превышая высоту столба.
Это требование неконсистенции можно идентифицировать, сравнивая высоту свободного прямоугольника с подставкой и высоту прямоугольника столба, чтобы создать свободное пространство для него. Если высота свободного прямоугольника не больше, чем другая, то для этого не требуется задействовать второй прямоугольник столбца, что означает, что он не требует согласованности свободного пространства.

case c: Обеим сторонам нужна консистенция свободного пространства. Здесь возникают неприятности. Повторите пример fig.3. Зеленый на рис.3 имел фиолетовый и синий цвета. Это означает, что зеленый, фиолетовый и синий цвета считаются целыми, чтобы сменить порядок укладки с другими прямоугольниками столбцов, чтобы получить свободный прямоугольник LHS. И в этом целом синий и фиолетовый тоже могут меняться.
Если RHS не может подгонять, что приводит к высоте упаковки, превышающей высоту стойки, тогда необходимо повторить шаг 2, но сначала установите RHS и попробуйте установить LHS после этого. Затем в качестве конечного результата берется результат сравнения нижней высоты упаковки. Логика для этого случая неясна, очень вероятно, что лучше альтернатива.

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