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

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

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

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

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

Ответ 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 и достаточно большого "Big M" 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

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

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

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

Ответ 2

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

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

Ответ 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:

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

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

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