Прямоугольная упаковка
Упаковка прямоугольников — это задача упаковки , цель которой — определить, можно ли поместить данный набор маленьких прямоугольников внутри данного большого многоугольника так, чтобы никакие два маленьких прямоугольника не перекрывались. Было изучено несколько вариантов этой проблемы.
Упаковка одинаковых прямоугольников в прямоугольник
[ редактировать ]В этом варианте существует несколько экземпляров одного прямоугольника размера ( l , w ) и прямоугольника большего размера ( L , W ). Цель состоит в том, чтобы упаковать как можно больше маленьких прямоугольников в большой прямоугольник без перекрытия между прямоугольниками (маленькими или большими). Общие ограничения проблемы включают ограничение поворота маленького прямоугольника кратностью 90 ° и требование, чтобы каждый маленький прямоугольник был ортогонален большому прямоугольнику.
У этой проблемы есть некоторые применения, такие как погрузка коробок на поддоны и, в частности, укладка древесной массы . В качестве примера результат: можно упаковать 147 маленьких прямоугольников размером (137,95) в большой прямоугольник размером (1600,1230). [1]
Упаковка одинаковых квадратов в прямолинейный многоугольник
[ редактировать ]Учитывая прямолинейный многоугольник (стороны которого встречаются под прямым углом ) R на плоскости, набор S точек в R и набор одинаковых квадратов, цель состоит в том, чтобы найти наибольшее количество непересекающихся квадратов, которые можно упаковать в точки С.
Предположим, что для каждой точки p в S мы поместили квадрат с центром в p . Пусть GS — граф пересечений этих квадратов. Квадратная упаковка эквивалентна множеству в GS независимому . Найти наибольшую квадратную упаковку NP-сложно; это можно доказать, сократив 3SAT . [2]
Упаковка разных прямоугольников в один прямоугольник
[ редактировать ]В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, и их следует упаковать в один большой прямоугольник. Проблема решения вопроса о существовании такой упаковки является NP-трудной . Это можно доказать сокращением от 3-х разделов . Учитывая экземпляр 3-раздела с 3 m натуральных чисел: a 1 , ..., a 3 m , с общей суммой m T , мы строим 3 m маленьких прямоугольников, все шириной 1, таких, что длина прямоугольника i — это a i + m . Большой прямоугольник имеет ширину м и длину Т + 3 м . Каждое решение экземпляра с тремя разделами вызывает упаковку прямоугольников в m подмножеств так, что общая длина в каждом подмножестве равна точно T , поэтому они точно вписываются в большой прямоугольник. И наоборот, в любой упаковке большого прямоугольника не должно быть «дырок», поэтому прямоугольники нельзя поворачивать. Следовательно, упаковка должна включать ровно m строк, где каждая строка содержит прямоугольники общей длиной ровно T . Это соответствует решению трехраздельного экземпляра. [3] [4]
Если существует дополнительное ограничение, согласно которому упаковка должна быть точной (без лишнего пространства), маленькие прямоугольники можно поворачивать только на угол, кратный 90°. В данном случае проблема в NP . Без этого требования маленькие прямоугольники можно поворачивать на произвольные углы. В этом более общем случае неясно, заключается ли проблема в NP, поскольку проверить решение гораздо сложнее. [4]
Упаковка разных прямоугольников в прямоугольник минимальной площади
[ редактировать ]В этом варианте маленькие прямоугольники могут иметь разную длину и ширину, а их ориентация фиксирована (их нельзя вращать). Цель состоит в том, чтобы упаковать их в охватывающий прямоугольник минимальной площади без границ по ширине и высоте охватывающего прямоугольника. Эта проблема имеет важное применение при объединении изображений в одно изображение большего размера. Веб-страница, загружающая одно изображение большего размера, часто отображается в браузере быстрее, чем та же страница, загружающая несколько маленьких изображений, из-за дополнительных затрат, связанных с запросом каждого изображения с веб-сервера. В целом задача NP-полная , но существуют быстрые алгоритмы решения небольших случаев. [5] [6]
Связанные проблемы
[ редактировать ]- Гильотинная резка — это вариант упаковки прямоугольников с дополнительным ограничением, заключающимся в том, что прямоугольники в упаковке должны быть разделены только с помощью гильотинных разрезов .
- Максимальное непересекающееся множество (или Максимальное независимое множество ) — это задача, в которой фиксированы размеры и расположение входных прямоугольников, а цель — выбрать наибольшую сумму непересекающихся прямоугольников. Напротив, в упаковке прямоугольников (как и в реальных задачах упаковки) размеры прямоугольников заданы, но их расположение является гибким. В некоторых статьях используется термин «упаковка», даже если места фиксированы. [7]
- Упаковка круга в прямоугольник
- Квадратная упаковка в квадрате
- Теорема де Брейна : упаковка одинаковых прямоугольных кирпичей любого размера в прямоугольные коробки.
Ссылки
[ редактировать ]- ^ Биргин, Э.Г.; Лобато, РД; Морабито, Р. (2010). «Эффективный подход рекурсивного разделения для упаковки идентичных прямоугольников в прямоугольник». Журнал Общества операционных исследований . 61 (2): 306–320. дои : 10.1057/jors.2008.141 . S2CID 12718141 .
- ^ Фаулер, Роберт Дж.; Патерсон, Майкл С.; Танимото, Стивен Л. (13 июня 1981 г.). «Оптимальная упаковка и покрытие в плоскости NP-полны» . Письма об обработке информации . 12 (3): 133–137. дои : 10.1016/0020-0190(81)90111-3 . ISSN 0020-0190 .
- ^ Демейн, Эрик Д.; Демейн, Мартин Л. (1 июня 2007 г.). «Головоломки, сопоставление ребер и упаковка полимино: связи и сложность» . Графы и комбинаторика . 23 (1): 195–208. дои : 10.1007/s00373-007-0713-4 . ISSN 1435-5914 . S2CID 17190810 .
- ^ Jump up to: Перейти обратно: а б Демейн, Эрик (2015). «MIT OpenCourseWare – повышенная жесткость 2–3-разделов I» . Ютуб .
- ^ Хуанг, Э.; Корф, Р.Э. (23 января 2013 г.). «Оптимальная упаковка прямоугольника: абсолютный подход к размещению» . Журнал исследований искусственного интеллекта . 46 : 47–87. arXiv : 1402.0557 . дои : 10.1613/jair.3735 . ISSN 1076-9757 .
- ^ «Быстрая оптимизация алгоритма упаковки прямоугольников для создания CSS-спрайтов» . www.codeproject.com . 14 июня 2011 года . Проверено 9 сентября 2020 г.
- ^ Чан, ТМ (2003). «Схемы аппроксимации полиномиального времени для упаковки и прокалывания толстых объектов». Журнал алгоритмов . 46 (2): 178–189. CiteSeerX 10.1.1.21.5344 . дои : 10.1016/s0196-6774(02)00294-8 .