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

Question

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

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

Любые предложения?

-Edit-

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

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

Answer 1

У меня были хорошие результаты, используя этот алгоритм:

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

Edit:

Алгоритм, описанный в ссылке, которую я поставляемой даст вам «Да» или «Нет» ответ на вопрос, может ли данный набор прямоугольников быть упакован в конкретный прямоугольник. Чтобы найти минимальный прямоугольник, вы можете запустить алгоритм повторно. В принципе, вычислите нижнюю границу и верхнюю границу для охватывающего прямоугольника, затем выполните двоичный поиск, чтобы найти минимальное решение, которое попадает в эти границы. Я предполагаю, что охватывающий прямоугольник является фиксированным размером в одном измерении (т. Е. Ширина является постоянной, ища минимальную длину или наоборот). Если ширина и длина охватывающего прямоугольника могут меняться, то это сложнее, и это может не сработать.

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

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

Верхние границы. Наихудший случай заключается в том, что каждый прямоугольник должен быть упакован на отдельной «строке», поэтому для каждого входного прямоугольника вычислите min(width, height) и суммируйте их (т. Е. Притворяющиеся входные прямоугольники укладываются друг на друга с использованием минимальной ширины или высоты каждого входа, так что другой размер входного сигнала не превышает ширину охватывающего прямоугольника).

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