Проблемы с упаковкой

Эта статья посвящена задачам геометрической упаковки. Для числовых задач упаковки см. Задача о рюкзаке .

Сферы или круги упакованы свободно (вверху) и более плотно (внизу).

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

В задаче об упаковке мусора людям дается:

• Контейнер , возможно , , обычно двух- или трехмерная выпуклая область бесконечного размера. В зависимости от проблемы может быть предоставлено несколько контейнеров.
• Набор объектов , некоторые или все из которых должны быть упакованы в один или несколько контейнеров. Набор может содержать разные объекты с указанными размерами или один объект фиксированного размера, который можно использовать повторно.

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

Упаковка в бесконечном пространстве

Многие из этих задач при увеличении размеров контейнера во всех направлениях становятся эквивалентными задаче максимально плотной упаковки объектов в бесконечном евклидовом пространстве . Эта проблема актуальна для ряда научных дисциплин и ей уделяется значительное внимание. Гипотеза Кеплера постулировала оптимальное решение для упаковки сфер за сотни лет до того, как ее доказал правильность Томас Каллистер Хейлз . Внимание привлекли многие другие формы, в том числе эллипсоиды, Платоновые и архимедовы тела в том числе тетраэдры , штативы (объединения кубов по трем положительным осно-параллельным лучам), и димеры неравных сфер.

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

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

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

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

упаковки в более

Основная статья: Упаковка сфер

В трех измерениях плотноупакованные структуры обеспечивают лучшую решетчатую упаковку сфер и считаются оптимальной из всех упаковок. При «простых» трехмерных упаковках сфер («простые» должны быть тщательно определены) существует девять возможных определимых упаковок. Также было доказано, что 8-мерная решетка E8 и 24-мерная решетка Лича оптимальны в соответствующем реальном размерном пространстве.

Упаковки платоновых тел в трех измерениях

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

Тетраэдры и октаэдры вместе могут заполнить все пространство, образуя структуру, известную как тетраэдрически-октаэдрические соты .

Твердый	Оптимальная плотность решетчатой ​​упаковки
икосаэдр	0.836357...
додекаэдр	(5 +  √ 5 )/8 = 0.904508...
октаэдр	18/19 = 0.947368...

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

Упаковка в трехмерные контейнеры

Разные кубоиды в кубоид

Определите минимальное количество кубовидных контейнеров (контейнеров), которые необходимы для упаковки заданного набора кубовидных предметов. Упаковываемые прямоугольные кубоиды можно поворачивать на 90 градусов по каждой оси.

Сферы в евклидов шар

Основная статья: Упаковка сфер в сферу

Задача о нахождении наименьшего шара, внутри которого можно упаковать k непересекающихся открытых единичных шаров, имеет простой и полный ответ в n -мерном евклидовом пространстве, если $k\leq n+1$, и в бесконечномерном гильбертовом пространстве без ограничений. Здесь стоит описать подробно, чтобы дать представление об общей проблеме. конфигурация из k попарно касательных В этом случае доступна единичных шаров. Люди размещают центры в вершинах $a_{1},\dots ,a_{k}$ регулярного $(k-1)$ размерный симплекс с ребром 2; это легко реализовать, исходя из ортонормированного базиса . Небольшое вычисление показывает, что расстояние каждой вершины от барицентра равно ${\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$. При этом любая другая точка пространства обязательно находится на большем расстоянии хотя бы от одной из k вершин. С точки зрения включений шаров, k открытых единичных шаров с центром в $a_{1},\dots ,a_{k}$ включены в шар радиуса ${\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$, что минимально для данной конфигурации.

Чтобы показать, что эта конфигурация оптимальна, пусть $x_{1},\dots ,x_{k}$ — центры k непересекающихся открытых единичных шаров, содержащихся в шаре радиуса r с центром в точке $x_{0}$. Рассмотрим отображение из конечного множества $\{x_{1},\dots ,x_{k}\}$ в $\{a_{1},\dots ,a_{k}\}$ принимая $x_{j}$ в соответствующем $a_{j}$ для каждого $1\leq j\leq k$. Поскольку для всех $1\leq i<j\leq k$, $\|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|$ это отображение 1- липшицево и по теореме Киршбрауна продолжается до 1-липшицева отображения, определенного глобально; в частности, существует точка $a_{0}$ такой, что для всех $1\leq j\leq k$ у одного есть $\|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|$, так что также $r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r$. имеется k Это показывает, что в шаре радиуса r непересекающихся единичных открытых шаров тогда и только тогда, когда $r\geq r_{k}$. Обратите внимание, что в бесконечномерном гильбертовом пространстве из этого следует, что существует бесконечно много непересекающихся открытых единичных шаров внутри шара радиуса r тогда и только тогда, когда $r\geq 1+{\sqrt {2}}$. Например, единичные шары с центром в ${\sqrt {2}}e_{j}$, где $\{e_{j}\}_{j}$ является ортонормированным базисом, не пересекаются и входят в шар радиуса $1+{\sqrt {2}}$ сосредоточено в начале координат. Более того, для $r<1+{\sqrt {2}}$, максимальное количество непересекающихся открытых единичных шаров внутри шара радиуса r равно ${\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$.

Сферы в кубоиде

См. Также: Упаковка сферы в куб.

Люди определяют количество сферических объектов заданного диаметра d , которые можно упаковать в кубоид размером $a\times b\times c$.

Одинаковые сферы в цилиндре

Основная статья: Упаковка сфер в цилиндр

Люди определяют минимальную высоту h цилиндра , в который заданного радиуса R поместятся n одинаковых сфер радиуса r (< R ) . При малом радиусе R сферы образуют упорядоченные структуры, называемые столбчатыми структурами .

Многогранники в сферах

Люди определяют минимальный радиус R , который упакует n одинаковых единичного объема многогранников заданной формы.

Упаковка в двухмерные контейнеры

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

Было изучено множество вариантов двумерных задач упаковки.

Упаковка кругов

Основная статья: Упаковка кругов

Людям даны n единичных кругов , и они должны упаковать их в наименьший возможный контейнер. Были изучены несколько видов контейнеров:

• Упаковка кругов в круг - тесно связана с распределением точек в единичном круге с целью найти наибольшее минимальное расстояние d _n между точками. Оптимальные решения доказаны для n ≤ 13 и n = 19 .
• Упаковка кругов в квадрат - тесно связана с распределением точек в единичном квадрате с целью найти наибольшее минимальное расстояние d _n между точками. Для преобразования между этими двумя формулировками задачи квадратная сторона единичного круга будет равна $L=2+2/d_{n}$.

  

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

  Оптимальные решения доказаны при n ≤ 30 .
• Упаковка кругов в прямоугольник
• Упаковка кругов в равнобедренный прямоугольный треугольник — хорошие оценки известны для n < 300 .
• Упаковочные круги в равносторонний треугольник . Оптимальные решения известны для n < 13 , а гипотезы доступны для n < 28 .

Упаковка квадратов

Основная статья: Квадратная упаковка

Людям дают n единичных квадратов , и они должны упаковать их в минимально возможный контейнер, тип контейнера может быть разным:

• Упаковка квадратов в квадрат . Оптимальные решения доказаны для n от 1 до 10, 14–16, 22–25, 33–36, 62–64, 79–81, 98–100 и любого квадрата целого . Потерянное пространство асимптотически равно O ( a ^3/5 ) .
• Упаковка квадратов в круг : Хорошие решения известны для n ≤ 35 .

  

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

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

Основная статья: Прямоугольная упаковка

• Упаковка одинаковых прямоугольников в прямоугольник . Проблема упаковки нескольких экземпляров одного прямоугольника размера ( l , w ) , допускающего поворот на 90 °, в прямоугольник большего размера ( L , W ) имеет некоторые приложения, такие как загрузка коробок. на поддонах и, в частности, для хранения древесной массы . Например, можно упаковать 147 прямоугольников размером (137,95) в прямоугольник размером (1600,1230).
• Упаковка разных прямоугольников в прямоугольник . Проблема упаковки нескольких прямоугольников различной ширины и высоты в охватывающий прямоугольник минимальной площади (но без границ по ширине и высоте охватывающего прямоугольника) имеет важное применение при объединении изображений в одно большее изображение. . Веб-страница, загружающая одно изображение большего размера, часто отображается в браузере быстрее, чем та же страница, загружающая несколько маленьких изображений, из-за дополнительных затрат, связанных с запросом каждого изображения с веб-сервера. В целом задача NP-полная , но существуют быстрые алгоритмы решения небольших случаев.

Связанные поля

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

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

Прямоугольник a × b можно упаковать полосками размером 1 × n тогда и только тогда, когда n делит a или n делит b .

Теорема де Брейна : Коробку можно упаковать гармоническим кирпичом a × ab × abc , если коробка имеет размеры ap × abq × abcr для некоторых натуральных чисел p , q , r (т. е. коробка кратна кирпичу).

Изучение мозаики полимино в основном касается двух классов задач: замостить прямоугольник совпадающими плитками и упаковать по одному из каждого n -мино в прямоугольник.

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

Упаковка нестандартных предметов

Упаковка объектов неправильной формы представляет собой проблему, которая не поддается решению в закрытой форме; однако применимость к практической науке об окружающей среде весьма важна. Например, частицы почвы неправильной формы упаковываются по-разному в зависимости от размера и формы, что приводит к важным результатам для видов растений по адаптации корневых образований и обеспечению движения воды в почве.

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

См. также

• Проблема с упаковкой контейнера
• Плотная упаковка равных сфер
• Пазл Конвея
• Проблема с покрытием
• Проблема с обрезкой материала
• Эллипсоидная упаковка
• Проблема с числом поцелуев
• Задача о рюкзаке
• Случайная закрытая упаковка
• Упаковка комплекта
• Загадка Слотубера – Граатсмы
• Проблема с упаковкой ленты
• Упаковка тетраэдра
• Тетрис

Ссылки

• Вайсштейн, Эрик В. «Теорема Кларнера» . Математический мир .
• Вайсштейн, Эрик В. «Теорема де Брейна» . Математический мир .

Внешние ссылки

• Оптимизация трехмерной упаковки в контейнеры

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

• Ссылки на различные статьи MathWorld об упаковке
• Заметки MathWorld об упаковке квадратов.
• Упаковочный центр Эриха
• www.packomania.com Сайт с таблицами, графиками, калькуляторами, справочниками и т. д.
• «Упаковка коробок» , Эд Пегг-младший , Демонстрационный проект Вольфрама , 2007 г.
• Наиболее известные упаковки равных кругов в круге, до 1100.

• Проблема с упаковкой кругов в Python