Подтвердить что ты не робот

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

Я бы начал с проскальзывания через http://mathworld.wolfram.com - они потрясающие для таких вещей.

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

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