Упаковка прямоугольников - это проблема упаковки, цель которой состоит в том, чтобы определить, можно ли разместить данный набор маленьких прямоугольников внутри данного большого многоугольника, чтобы никакие два маленьких прямоугольника не перекрывались. Было изучено несколько вариантов этой проблемы.
Упаковка одинаковых прямоугольников в прямоугольник [ править ]
В этом варианте есть несколько экземпляров одного прямоугольника размера ( l , w ) и большего прямоугольника размера ( L , W ). Цель состоит в том, чтобы упаковать как можно больше маленьких прямоугольников в большой прямоугольник. Допускается поворот некоторых маленьких прямоугольников кратно 90 °.
У этой проблемы есть некоторые, такие как загрузка ящиков на поддоны и, в частности, укладка древесной массы. В качестве примера результата: можно упаковать 147 маленьких прямоугольников размера (137,95) в большой прямоугольник размером (1600,1230). [1]
Упаковка одинаковых квадратов в прямолинейный многоугольник [ править ]
Учитывая прямолинейную многоугольник R в плоскости, множество S точек в R , и множество одинаковых квадратов, цель состоит в том, чтобы найти наибольшее число непересекающихся квадратов , которые могут быть упакованы в точках S .
Предположим, что для каждой точки p в S мы помещаем квадрат с центром в p . Пусть G S - граф пересечений этих квадратов. Квадрат-упаковка эквивалентна независимое множество в G S . Найти самую большую квадратную упаковку NP-сложно; это можно доказать, перейдя с 3SAT . [2]
Упаковка разных прямоугольников в один прямоугольник [ править ]
В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, и они должны быть упакованы в заданный большой прямоугольник. Проблема решения о том, существует ли такая упаковка, является NP-трудной . Это можно доказать редукцией с 3-разбиения . Принимая во внимание экземпляр 3-разбиения с 3 - м положительных целыми числами: 1 , ..., 3 м , с общей суммой м Т , мы строим 3 м небольших прямоугольников, все с шириной 1, что длина прямоугольника i - это a i + m . Большой прямоугольник имеет ширину m и длину T.+ 3 мес . Каждое решение для случая с 3-мя разделами индуцирует упаковку прямоугольников в m подмножеств, так что общая длина в каждом подмножестве равна T , поэтому они точно помещаются в большой прямоугольник. И наоборот, в любой упаковке большого прямоугольника не должно быть «дырок», поэтому прямоугольники нельзя поворачивать. Таким образом, упаковка должна включать в себя ровно т строк , где каждая строка содержит прямоугольники с общей длиной точно T . Это соответствует решению экземпляра с 3 разделами. [3] [4]
Если существует дополнительное ограничение, заключающееся в том, что упаковка должна быть точной (без лишнего пространства), маленькие прямоугольники можно поворачивать только на кратные 90 °. В данном случае проблема в НП . Без этого требования маленькие прямоугольники можно поворачивать на произвольные углы. В этом более общем случае неясно, находится ли проблема в NP, поскольку гораздо сложнее проверить решение. [4]
Упаковка различных прямоугольников в прямоугольник с минимальной площадью [ править ]
В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, и их ориентация фиксирована (их нельзя вращать). Цель состоит в том, чтобы упаковать их в охватывающий прямоугольник с минимальной площадью, без границ по ширине или высоте охватывающего прямоугольника. Эта проблема имеет важное применение при объединении изображений в одно более крупное изображение. Веб-страница, загружающая одно большое изображение, часто отображается в браузере быстрее, чем та же страница, загружающая несколько небольших изображений, из-за накладных расходов, связанных с запросом каждого изображения с веб-сервера. В целом проблема NP-полная , но есть быстрые алгоритмы для решения небольших примеров. [5] [6]
См. Также [ править ]
- Гильотинная резка - это проблема, тесно связанная с упаковкой прямоугольников, при которой на упаковку накладывается дополнительное ограничение, заключающееся в том, что должно быть возможно разделить прямоугольники с использованием только гильотинных разрезов .
- Упаковка квадрата в квадрат
- Теорема де Брейна
Ссылки [ править ]
- ^ Birgin, EG; Лобато, РД; Морабито, Р. (2010). «Эффективный рекурсивный подход к разделению для упаковки идентичных прямоугольников в прямоугольник». Журнал Общества оперативных исследований . 61 (2): 306–320. DOI : 10,1057 / jors.2008.141 . S2CID 12718141 .
- ^ Фаулер, Роберт Дж .; Патерсон, Майкл С .; Танимото, Стивен Л. (1981-06-13). «Оптимальная упаковка и укрытие в самолете - NP-комплектация» . Письма об обработке информации . 12 (3): 133–137. DOI : 10.1016 / 0020-0190 (81) 90111-3 . ISSN 0020-0190 .
- ^ Demaine, Эрик Д .; Демейн, Мартин Л. (2007-06-01). «Пазлы, совпадение краев и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 (1): 195–208. DOI : 10.1007 / s00373-007-0713-4 . ISSN 1435-5914 .
- ^ a b Демейн, Эрик (2015). "MIT OpenCourseWare - Hardness made Easy 2 - 3-Partition I" . Youtube .
- ^ Хуанг, E .; Корф, Р.Е. (23.01.2013). «Оптимальная прямоугольная упаковка: подход с абсолютным размещением» . Журнал исследований искусственного интеллекта . 46 : 47–87. DOI : 10.1613 / jair.3735 . ISSN 1076-9757 .
- ^ «Быстрая оптимизация алгоритма упаковки прямоугольников для построения CSS-спрайтов» . www.codeproject.com . Проверено 9 сентября 2020 .
