Прямоугольная упаковка - Rectangle packing

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

Упаковка одинаковых прямоугольников в прямоугольник

В этом варианте существует несколько экземпляров одного прямоугольника размера (л,ш) и прямоугольник большего размера (L,W). Цель состоит в том, чтобы упаковать как можно больше маленьких прямоугольников в большой прямоугольник. Допускается поворот некоторых маленьких прямоугольников кратно 90 °.

Эта проблема имеет некоторые, такие как загрузка ящиков на поддоны и, в частности, древесная масса укладка. В качестве примера результата: можно упаковать 147 маленьких прямоугольников размера (137,95) в большой прямоугольник размером (1600,1230).[1]

Упаковка разных прямоугольников в заданный прямоугольник

В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, и они должны быть упакованы в заданный большой прямоугольник. Проблема решения того, существует ли такая упаковка, состоит в следующем: NP-жесткий. Это можно доказать редукцией из 3-х секционный. Учитывая экземпляр 3-разбиения с 3м положительные целые числа: а1, ..., а3м, на общую сумму м Т, строим 3м маленькие прямоугольники, все шириной 1, так что длина прямоугольника я является ая + м. Большой прямоугольник имеет ширину м и длина Т + 3м. Каждое решение для случая 3-разбиения индуцирует упаковку прямоугольников в м подмножества таких, что общая длина в каждом подмножестве в точности равна Т, поэтому они точно вписываются в большой прямоугольник. И наоборот, в любой упаковке большого прямоугольника не должно быть «дырок», поэтому прямоугольники нельзя поворачивать. Следовательно, в упаковке должно быть ровно м строки, каждая строка которых содержит прямоугольники с общей длиной ровно Т. Это соответствует решению экземпляра с 3 разделами.[2][3]

Если существует дополнительное ограничение, заключающееся в том, что упаковка должна быть точной (без лишнего пространства), маленькие прямоугольники можно поворачивать только на кратные 90 °. В этом случае проблема в НП. Без этого требования маленькие прямоугольники можно вращать на произвольные углы. В этом более общем случае неясно, находится ли проблема в NP, поскольку гораздо сложнее проверить решение.[3]

Упаковка разных прямоугольников в прямоугольник с минимальной площадью

В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, и их ориентация фиксирована (их нельзя вращать). Цель состоит в том, чтобы упаковать их в охватывающий прямоугольник с минимальной площадью, без границ по ширине или высоте охватывающего прямоугольника. Эта проблема имеет важное применение при объединении изображений в одно более крупное изображение. Веб-страница, загружающая одно более крупное изображение, часто отображается в браузере быстрее, чем та же страница, загружающая несколько небольших изображений, из-за накладных расходов, связанных с запросом каждого изображения с веб-сервера. Проблема в НП-полный в общем, но есть быстрые алгоритмы решения небольших примеров.[4][5]

Смотрите также

Рекомендации

  1. ^ Birgin, EG; Лобато, Р. Д.; Морабито, Р. (2010). «Эффективный рекурсивный подход к разделению для упаковки идентичных прямоугольников в прямоугольник». Журнал Общества оперативных исследований. 61 (2): 306–320. Дои:10.1057 / jors.2008.141. S2CID  12718141.
  2. ^ Demaine, Erik D .; Демейн, Мартин Л. (2007-06-01). «Пазлы, совпадение краев и упаковка полимино: взаимосвязи и сложность». Графы и комбинаторика. 23 (1): 195–208. Дои:10.1007 / s00373-007-0713-4. ISSN  1435-5914.
  3. ^ а б Демейн, Эрик (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3 раздела I". YouTube.
  4. ^ Huang, E .; Корф, Р. Э. (23 января 2013 г.). «Оптимальная прямоугольная упаковка: абсолютный подход к размещению». Журнал исследований искусственного интеллекта. 46: 47–87. Дои:10.1613 / jair.3735. ISSN  1076-9757.
  5. ^ «Быстрая оптимизация алгоритма упаковки прямоугольников для создания спрайтов CSS». www.codeproject.com. Получено 2020-09-09.