Алгоритм расчета минимальной площади (размещайте плитки только на краю)

У меня есть разные размеры маленьких прямоугольников (1 см х 2 х м, 2 см х 3 см, 4 см * 6 см и т. д.). Количество прямоугольников разных типов может варьироваться в зависимости от случая. Каждый тип различных прямоугольников может иметь разное количество отсчетов.

Мне нужно создать большой прямоугольник со всеми этими маленькими прямоугольниками, которые эти маленькие прямоугольники могут быть размещены только на краях. без ротации. Последний внешний прямоугольник в идеале должен быть похож на квадрат. Х ~ Y. Не все края должны быть заполнены. Между меньшими прямоугольниками могут быть промежутки. Пример изображения:
http://i.stack.imgur.com/GqI5z.png

Я пытаюсь написать код, который определяет минимально возможную площадь, которую можно сформировать.

У меня есть алгоритм, который перебирает все возможные места размещения, чтобы найти минимально возможную площадь. Но это занимает много времени, так как количество прямоугольников разных типов и количество прямоугольников увеличивается. т.е. 2 типа прямоугольников, в каждом по 100+ прямоугольников. 8 для петель. Это будет ~100^8 итераций.

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

    for rectange_1_top_count in (range(0,all_rectangles[1]["count"]+1)):
      for rectange_1_bottom_count in range(0,all_rectangles[1]["count"]-rectange_1_top_count+1):
        for rectange_1_left_count in (range(0,all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count+1)):
          for rectange_1_right_count in ([all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count-rectange_1_left_count]):
            for rectange_2_top_count in (range(0,all_rectangles[2]["count"]+1)):
              for rectange_2_bottom_count in (range(0,all_rectangles[2]["count"]-rectange_2_top_count+1)):
                for rectange_2_left_count in (range(0,all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_top_count+1)):
                  for rectange_2_right_count in [(all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_left_count-rectange_2_top_count)]:
                      area=calculate_minimum_area()
                      if area< minimum_area:
                        minimum_area=area

algorithm geometry rectangles minimization placement
person Charles Tang    schedule 22.01.2016    source источник
comment
Итак, размер внешнего прямоугольника задан, и вы хотите минимизировать белую область в середине?   -  person M Oehm    schedule 22.01.2016
comment
Условие, которое делает его трудным, - это прямоугольник, который можно разместить только по краям/сторонам. Их нельзя складывать   -  person Charles Tang    schedule 22.01.2016
comment
Размер внешнего прямоугольника не указан. Даются только размеры небольших прямоугольников. Размер внешнего прямоугольника будет меняться по мере изменения размещения. Но мне нужно оптимальное размещение маленького прямоугольника на краю, которое даст наименьшую площадь внешнего прямоугольника.   -  person Charles Tang    schedule 22.01.2016
comment
Хорошо спасибо. Вы должны использовать все плитки?   -  person M Oehm    schedule 22.01.2016
comment
Да, все плитки должны быть использованы. Например, у меня есть 10 плиток. Все 10 плиток могут быть размещены только на краю, и все должны быть размещены. Спасибо   -  person Charles Tang    schedule 22.01.2016
comment
Требуется ли, чтобы каждый сегмент ребра прилегал к прямоугольнику, или могут быть пропуски? Очевидно, что прямоугольники в углах являются частью двух ребер. Но может ли большой прямоугольник также быть частью, скажем, нижнего и верхнего края?   -  person lex82    schedule 22.01.2016
comment
Должны ли противоположные стороны быть равными или у них могут быть разные прямоугольники?   -  person Juan Lopes    schedule 22.01.2016
comment
Может ли решение иметь высоту или ширину 1?   -  person lex82    schedule 22.01.2016
comment
Решение должно иметь как можно более близкие высоту и ширину, чтобы больший прямоугольник мог иметь квадратную форму. Противоположные стороны не обязательно должны быть равными, они могут иметь разное количество прямоугольников.   -  person Charles Tang    schedule 22.01.2016
comment
@lex82 @juan Lopes Я придумал один способ уменьшить сложность. Поскольку мы знаем, что внешний прямоугольник должен быть как можно ближе к квадрату. Вместо того, чтобы начинать с 0 до # прямоугольников типа 1, я могу попытаться найти меньший диапазон, for rectange_1_top_count in (range(5,all_rectangles[1]["count"]+1)): Если мы начнем с 5, а не с 0, на 3 ^ 8 меньше итераций. Я могу сделать то же самое для других петель. Но мне интересно, будет ли еще лучшее решение,   -  person Charles Tang    schedule 22.01.2016
comment
Я должен признать, что не понимаю, как работает ваш код. А откуда цифра пять в вашем улучшении?   -  person lex82    schedule 22.01.2016
comment
@lex82 Код перебирал все возможные места размещения с каждой стороны, от 0 до общего количества каждого прямоугольника. А затем узнать минимально возможную площадь. Теперь, учитывая, что окончательный больший прямоугольник хочет быть как можно более похожим на квадрат, мы знаем, что каждая сторона получит несколько прямоугольников, это не будет 0 . Чтобы уменьшить количество итераций, мы будем начинать не с 0, а с числа. 5 это просто пример. Число будет основано на формуле, которая зависит от размеров и количества прямоугольников. Я до сих пор не придумал эту формулу.   -  person Charles Tang    schedule 22.01.2016
comment
Но если мы сможем уменьшить количество итераций для каждого цикла, каждое сокращение приведет к экспоненциальному уменьшению времени выполнения. Это не оптимальное решение, но оно значительно сократит время выполнения. Что касается вашего ответа, что вы подразумеваете под разделением проблемы? Спасибо, если вы можете дать мне немного больше намека на это. Спасибо!   -  person Charles Tang    schedule 22.01.2016
comment
Я не имел в виду разделение проблемы, но что ваша проблема связана с проблемой разделения, которая трудно. Так что вашу проблему тоже очень трудно решить, по крайней мере, если вам нужно оптимальное решение.   -  person lex82    schedule 22.01.2016

Ответы (1)


arrow_upward
0
arrow_downward

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

Почему это NP-сложно? Предположим, что все ваши прямоугольники имеют высоту 1, а у вас есть прямоугольник высоты 2, тогда имеет смысл искать решение с общей высотой 2 (по сути, вы пытаетесь сформировать две горизонтальные линии прямоугольников высоты-1 с одинаковой длиной ). Чтобы выяснить, существует ли такое решение, вам нужно сформировать два подмножества ваших маленьких прямоугольников, оба в сумме дают одинаковую общую ширину. Это называется проблемой разделения и является NP-полной. Даже если могут быть промежутки и общая ширина не обязательно должна быть одинаковой, это все еще NP-сложная задача. Вы можете свести задачу о разбиении к задаче о прямоугольниках, преобразовав элементы разбиения в прямоугольники высотой 1, как описано выше.

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

person lex82    schedule 22.01.2016
comment
Я думаю, что ваш эскиз доказательства слишком неформален. Ваш аргумент в основном говорит о том, что вы можете свести один конкретный экземпляр проблемы к проблеме раздела, что не доказывает NP-полноты. Вам следует доказать обратное: что любой экземпляр NP-полной задачи можно свести (за полиномиальное время) к этой задаче, тогда он будет считаться NP-трудным. Ее нельзя доказать NP-полной, потому что это не проблема решения, т. е. ее нет в NP. - person Juan Lopes; 22.01.2016
comment
@juan-lopes, спасибо, что указали на это. Я перепутал NP-hard и NP-complete. Я попытался улучшить ответ. - person lex82; 22.01.2016