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

Question

Предположим, что у нас есть несколько квадратов одинакового размера. Мы хотим нарисовать прямоугольники n (здесь есть красные и желтые прямоугольники), чтобы содержать эти квадраты.

Цель состоит в том, чтобы иметь как можно меньше пространства впустую.

В приведенном ниже примере n = 2, а решение справа предпочтительнее, так как оно приводит к одному свободному пространству.

Существуют ли уже известные алгоритмы для решения этих проблем?

ОБНОВЛЕНИЕ: Расположение квадратов произвольно и они всегда превышают ось X!

UPDATE2: Для того, чтобы вопрос проще, давайте предположим, что так называемые контейнерные прямоугольники друг на друга! (Красные и желтые прямоугольники здесь)

Чуть более сложный случай: давайте предположим, два прямоугольника используются для этого тоже. Как видно, 3-е решение приводит к наименее свободному пространству.

Answer 1

Этого типа прямоугольник крышка трудно (NP-трудно на самом деле, вы можете использовать его для решения Прямоугольника Cover проблемы), но вы можете решить эту проблему с целочисленным линейным программированием, а именно:

minimize sum[i] take[i] * area[i] 
st 
sum[i] take[i] == n 
for every filled cell x,y: 
    sum[rectangle i covers x,y] take[i] == 1 
take[i] in { 0, 1 } 

Если списки прямоугольников содержат только «разумные» прямоугольники, которые могут вам понадобиться. т.е. только прямоугольники, которые не могут быть уменьшены без раскрытия некоторой заполненной ячейки, и вы можете пропустить определенные «внутренние прямоугольники», которые вы можете сказать, никогда не могут быть частью решения, потому что они оставят форму, которую сложнее покрыть. Создание этих прямоугольников - это забавное упражнение в своем собственном праве, но генерировать слишком много - это не большая проблема, а медленнее. В решении любой take[i], который равен 1, соответствует прямоугольнику, который вы берете.

Вы можете бросить это в любой доступный решатель, такой как GLPK (бесплатно) или Gurobi (доступны коммерческие и академические лицензии).

Это обычно должно быть быстрее, чем грубая сила, поскольку для управления поиском можно использовать линейную релаксацию (та же модель, что и выше, но последнее ограничение, преобразованное в 0 <= take[i] <= 1), и могут применяться различные плоские режущие трюки.

Более продвинутые трюки можно найти в this paper, например, трюки, которые используют дробное решение из линейной релаксации.

Answer 2

Этот вопрос почти идентичен голосовой задаче, которую поставил ITA Software, называемый "Strawberry Fields" (прокрутите вниз для клубничных полей, измените стоимость теплицы от 10 до 0). Я могу подтвердить это целочисленное программирование, в частности, branch and price, где решения высокого уровня: разместить два квадрата в одном прямоугольнике, очень хорошо работает для этой проблемы. Вот мой custom solver, написанный на C.Вам нужно будет изменить стоимость теплицы в strawberry_fields.h от 10 до 0.