Укладка прямоугольников занимает как можно меньше места

Question

У меня есть программа, которая вычислит минимальную площадь, занимаемую соединением прямоугольников.

Ввод: прямоугольники различной высоты и ширины.
Выходные данные: один прямоугольник, содержащий все эти прямоугольники.
Правила: Нельзя поворачивать или переворачивать прямоугольники, и они не могут перекрываться.

Я понимаю, что это связано или, возможно, определяется как проблема с упаковкой бункера (NP-hard). Однако алгоритмы, которые я нашел для них, часто устанавливают ограничение, например, ширины. У меня нет таких ограничений, единственная цель - сделать полученную область как можно меньше.

Есть ли какие-нибудь указатели на то, какой алгоритм подходит для получения достойного решения?

Answer 1

http://www -rcf.usc.edu / ~ skoenig / ICAPS / icaps04 / icapspapers / ICAPS04KorfR.pdf

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

Answer 2

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

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

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

Answer 3

Я бы начал с пролистывания http://mathworld.wolfram.com - они такие классные.

Во-вторых, я мог бы представить себе дурацкий алгоритм, который помещал бы самый длинный (в измерении X) внизу, а затем самый высокий (в измерении Y) поверх него с одной или другой стороны. Затем продолжайте складывать их таким образом «ступеньки», направляясь вправо и вверх (например, идите направо, пока не сможете, затем поднимитесь и т. Д. И т. Д.).

Это, вероятно, неидеально, и может очень хорошо дать вам плохие результаты, но это то, что всплыло первым.