Задачи упаковки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пары задач покрытия/упаковки
Минимальное покрытие множества     Максимальная упаковка множеств
Минимальное вершинное покрытие Максимальное паросочетание
Минимальное рёберное покрытие     Максимальное независимое множество

Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии[en], в которой спрашивается, как много требуется некоторых предметов, чтобы полностью покрыть все области контейнера, при этом предметы могут накладываться.

В задаче упаковки задано:

  • «контейнеры» (обычно одна двумерная или трёхмерная выпуклая область или бесконечная область)
  • множество «объектов», некоторые из которых или все должны быть упакованы в один или несколько контейнеров. Множество может содержать различные объекты с заданными размерами, или один объект фиксированных размеров, который может быть использован несколько раз.

Обычно в упаковке объекты не должны пересекаться и объекты не должны пересекать стены контейнера. В некоторых вариантах цель заключается в нахождении конфигурации, которая упаковывает один контейнер с максимальной плотностью. В более общем виде целью является упаковка всех объектов в как можно меньше контейнеров[1]. В некоторых вариантах наложение (объектов друг на друга и/или на границы контейнера) разрешается, но это наложение должно быть минимизировано.

Упаковка бесконечного пространства[править | править код]

Многие из этих задач, если размер контейнера увеличивается во всех направлениях, становятся эквивалентны задачам упаковки объектов как можно плотнее в бесконечном евклидовом пространстве. Эта задача относится к некоторому числу научных дисциплин и получает существенное внимание. Гипотеза Кеплера постулировала оптимальное решение упаковки шаров за сотни лет до того, когда была доказана Томасом Хейлзом[en]. Получили внимание другие формы, включая эллипсоиды [2], платоновы и архимедовы тела [3], в том числе тетраэдры[en][4][5] и димеры различных сфер [6].

Шестиугольная упаковка кругов[править | править код]

Шестиугольная упаковка кругов на 2-мерной евклидовой плоскости.

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

Аналоги круга в других размерностях не могут быть упакованы с абсолютной эффективностью в размерностях, больших единицы (в одномерном пространстве аналог окружности — просто две точки). Таким образом, всегда останется незанятое пространство при упаковке исключительно кругами. Наиболее эффективный путь упаковки кругов, шестиугольная упаковка, даёт примерно 91 % эффективности[7].

Упаковка сфер в высших размерностях[править | править код]

В трёхмерном пространстве гранецентрированная решётка даёт оптимальную упаковку сфер. Доказано, что 8-мерная решётка E8 и 24-мерная решётка Лича оптимальны в соответствующих пространствах.

Упаковка платоновых тел в трёхмерных пространствах[править | править код]

Кубы легко могут быть расположены в трёхмерном пространстве так, что они полностью заполнят пространство. Наиболее естественная упаковка — кубические соты[en]. Никакой другой правильный многогранник не может заполнить полностью пространство, но некоторые результаты известны. Тетраэдр[en] может дать упаковку по меньшей мере 85 %. Одна из лучших упаковок правильными додекаэдрами основывается на вышеупомянутой гранецентрированной кубической решётке.

Тетраэдры и октаэдры вместе могут заполнить всё пространство в конфигурации, известной как тетраэдрально-октаэдральная мозаика[en].

Тело Оптимальная плотность решётчатой упаковки
икосаэдры 0.836357...[8]
додекаэдры [8]
октаэдры 18/19 = 0.947368...[9]

Моделирование, совмещающее методы локального улучшения со случайно сгенерированными упаковками, наводит на мысль, что решётчатые упаковки для икосаэдра, додекаэдра и октаэдра являются оптимальными и в более широком классе всех упаковок[3].

Упаковка в 3-мерные контейнеры[править | править код]

Сферы в евклидов шар[править | править код]

Задача нахождения наименьшего шара, в который можно упаковать без перекрытия открытых единичных шаров, имеет простой и полный ответ в -мерном евклидовом пространстве, если , а в бесконечномерном гильбертовом пространстве — без ограничений. Имеет смысл описать его здесь с целью показать общую проблему. В этом случае возможна конфигурация попарно касающихся единичных шаров. Разместим центры в вершинах правильного мерного симплекса с ребром 2. Это легко сделать, начав с ортонормированного базиса. Лёгкие вычисления показывают, что расстояние от любой вершины до центра тяжести равно . Кроме того, любая другая точка пространства имеет большее расстояние по меньшей мере до одной из вершин. В терминах включения шаров, открытых единичных шаров, имеющих центры в точках , попадают в шар радиуса , который минимален для такой конфигурации.

Чтобы показать, что такая конфигурация оптимальна, допустим, что — центры непересекающихся открытых единичных шаров, находящихся в шаре с радиусом и центром в точке . Рассмотрим отображение из конечного множества в , сопоставляющее в для всех . Поскольку для всех , , это отображение 1-липшицево и по теореме Киршбрауна оно распространяется до глобально определённого 1-липшицева отображения. В частности, существует точка , такая что для всех имеем , а следовательно, . Это показывает, что существуют непересекающихся единичных открытых шаров в шаре радиусом тогда и только тогда, когда . Заметим, что в случае бесконечномерного гильбертова пространства отсюда следует существование бесконечного числа непересекающихся единичных открытых шаров внутри шара радиуса тогда и только тогда, когда . Например, единичные шары с центрами в , где — ортонормальный базис, не пересекаются и содержатся в шаре радиуса с центром в начале координат. Более того, для максимальное число непересекающихся открытых единичных шаров внутри шара радиуса r равно .

Сферы в параллелепипед[править | править код]

Задача определяет число сферических объектов заданного диаметра d, которые могут быть упакованы в прямоугольный параллелепипед размера a × b × c.

Одинаковые сферы в цилиндр[править | править код]

Задача определяет минимальную высоту h цилиндра с заданным радиусом R, в который упаковано n одинаковых шаров радиуса r (< R) [10].

Упаковка в 2-мерные контейнеры[править | править код]

Упаковка кругов[править | править код]

Круги в круге[править | править код]

Оптимальная упаковка 10 кругов в круге

Упаковка n единичных кругов в как можно меньшую окружность. Задача тесно связана с распределением точек в единичной окружности с целью достичь наибольшего минимального расстояния dn между точками.

Оптимальные решения были доказаны для n≤13 и для n=19.

Круги в квадрате[править | править код]

Оптимальная упаковка 15 кругов в квадрате

Упаковка n единичных кругов в как можно меньший квадрат. Задача тесно связана с распределением точек в единичном квадрате с целью достичь наибольшего минимального расстояния dn между точками[11]. Для преобразования двух этих формулировок задачи размер квадрата единичных кругов будет L=2+2/dn.

Оптимальные решения были доказаны для n≤30[12].

Круги в равнобедренном прямоугольном треугольнике[править | править код]

Оптимальная упаковка 6 кругов в равнобедренном прямоугольном треугольнике

Упаковка n единичных кругов в как можно меньший равнобедренный прямоугольный треугольник[en]. Хорошие приближения известны для n<300 [13].

Круги в правильном треугольнике[править | править код]

Оптимальная упаковка 5 кругов в правильном треугольнике

Упаковка n единичных кругов в как можно меньший правильный треугольник. Оптимальные решения известны для n<13, а для n<28 высказаны гипотезы[14].

Упаковка квадратов[править | править код]

Квадраты в квадрате[править | править код]

Оптимальная упаковка 10 квадратов в квадрате

Упаковка n единичных квадратов в как можно меньший квадрат.

Оптимальные решения доказаны для n=1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100 и любого полного квадрата [15].

Незаполненное пространство асимптотически равно O(a7/11) [16].

Квадраты в круге[править | править код]

Упаковка n квадратов в как можно меньший круг.

Минимальные решения:[17]

Число квадратов Радиус окружности
1 0.707...
2 1.118...
3 1.288...
4 1.414...
5 1.581...
6 1.688...
7 1.802...
8 1.978...
9 2.077...
10 2.121...
11 2.214...
12 2.236...

Упаковка прямоугольников[править | править код]

Одинаковые прямоугольники в прямоугольнике[править | править код]

Задача упаковки множественных копий одного прямоугольника размера (l,w) с разрешением поворота на 90° в больший прямоугольник размера (L,W) имеет несколько приложений, таких как загрузка коробок на поддоны и укладка древесно-стружечных плит.

Например, можно упаковать 147 прямоугольников размера 137x95 в прямоугольник размера 1600x1230 [18].

Различные прямоугольники в прямоугольнике[править | править код]

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

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

Связанные задачи[править | править код]

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

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

Прямоугольник a × b может быть упакован в ленту 1 × n тогда и только тогда, когда n делится на a или n делится на b [19][20]
Теорема де Брёйна: прямоугольный параллелепипед может быть упакован гармоническим кирпичом[en] a × a b × a b c, если параллелепипед имеет размеры a p × a b q × a b c r для некоторых натуральных чисел p, q, r (т.е. параллелепипед кратен кирпичу.) [19]

Изучение замощений плитками полимино в значительной степени касается двух классов задач — замощение прямоугольника конгруэнтными плитками и замощение набором плиток n-полимино прямоугольника.

Классическая головоломка второго вида — расположить все двенадцать плиток пентамино в прямоугольниках размером 3×20, 4×15, 5×12 или 6×10.

Упаковка неправильных объектов[править | править код]

Упаковка неправильных объектов является задачей, решение которой вряд ли возможно в замкнутой (аналитической) форме. Однако в науке об окружающем мире задача весьма важна. Например, неправильные частички почвы упаковываются различным образом при изменении размеров и формы частичек, что ведёт к существенным последствиям для растений по формированию корней и возможности перемещения воды в почве.[21]

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

  • S. Torquato, Y. Jiao Dense packings of the Platonic and Archimedean solids // Nature. — 2009. — Т. 460, вып. 7257. — С. 876–879. — ISSN 0028-0836. — DOI:10.1038/nature08239. — Bibcode2009Natur.460..876T. — arXiv:0908.4107. — PMID 19675649.
  • Hallard T. Croft, Kenneth J. Falconer, Richard K. Guy. Unsolved Problems in Geometry. — New York: Springer-Verlag, 1991. — С. 108–110. — ISBN 0-387-97506-3.
  • J. Melissen Packing 16, 17 or 18 circles in an equilateral triangle // Discrete Mathematics. — 1995. — Т. 145. — С. 333–342. — DOI:10.1016/0012-365X(95)90139-C.
  • Y. G. Stoyan, G. N. Yaskov Packing identical spheres into a cylinder // International Transactions in Operational Research. — 2010. — Т. 17. — С. 51–70. — DOI:10.1111/j.1475-3995.2009.00733.x.
  • Eckard Specht. The best known packings of equal circles in a square (20 May 2010). Проверено 25 мая 2010.
  • P. Erdős, R. L. Graham On packing squares with equal squares // Journal of Combinatorial Theory, Series A. — 1975. — Т. 19. — С. 119–123. — DOI:10.1016/0097-3165(75)90099-0.
  • A. Lodi, S. Martello, M. Monaci Two-dimensional packing problems: A survey // European Journal of Operational Research. — Elsevier, 2002. — Т. 141. — С. 241–252. — DOI:10.1016/s0377-2217(02)00123-6.
  • A. Donev, F. Stillinger, P. Chaikin, S. Torquato Unusually Dense Crystal Packings of Ellipsoids // Physical Review Letters. — 2004. — Т. 92, вып. 25. — DOI:10.1103/PhysRevLett.92.255506. — Bibcode2004PhRvL..92y5506D. — arXiv:cond-mat/0403286.
  • A. Haji-Akbari, M. Engel, A. S. Keys, X. Zheng, R. G. Petschek, P. Palffy-Muhoray, S. C. Glotzer Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra // Nature. — 2009. — Т. 462, вып. 7274. — С. 773–777. — DOI:10.1038/nature08641. — Bibcode2009Natur.462..773H. — arXiv:1012.5138. — PMID 20010683.
  • E. R. Chen, M. Engel, S. C. Glotzer Dense Crystalline Dimer Packings of Regular Tetrahedra // Discrete & Computational Geometry. — 2010. — Т. 44, вып. 2. — С. 253–280. — DOI:10.1007/s00454-010-9273-0.
  • T. S. Hudson, P. Harrowell Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures // Journal of Physics: Condensed Matter. — 2011. — Т. 23, вып. 19. — С. 194103. — DOI:10.1088/0953-8984/23/19/194103.
  • E. G. Birgin, R. D. Lobato, R. Morabito An effective recursive partitioning approach for the packing of identical rectangles in a rectangle // Journal of the Operational Research Society. — 2010. — Т. 61. — С. 306–320. — DOI:10.1057/jors.2008.141.
  • Ross Honsberger. Mathematical Gems II. — The Mathematical Association of America, 1976. — ISBN 0-88385-302-7.
  • D.A. Klarner, M.L.J Hautus Uniformly coloured stained glass windows // Proceedings of the London Mathematical Society. — 1971. — Т. 23. — DOI:10.1112/plms/s3-23.4.613.
  • Eckard Specht. The best known packings of equal circles in an isosceles right triangle (11 March 2011). Проверено 1 мая 2011.
  • U. Betke, M. Henk Densest lattice packings of 3-polytopes // Comput. Geom.. — 2000. — Т. 16. — С. 157–186.
  • H. Minkowski Dichteste gitterförmige Lagerung kongruenter Körper // Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II. — 1904. — С. 311–355.
  • Erich Friedman Packing unit squares in squares: a survey and new results // The Electronic Journal of Combinatorics. — 2005. — Т. DS7.

Ссылки[править | править код]

Многие книги с головоломками, так же, как и математические журналы, содержат статьи об упаковках.