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

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

Часть серии по
Загадки
Типы Гадание Загадка Ситуация Логика Расслоение Индукция Логическая сетка Самостоятельная ссылка Механический Комбинация Строительство Распутывание Замок Перейти проблемы Складной Палка Черепица Тур Раздвижной Шахматы Лабиринт  ( Логический лабиринт ) Слово и число Кроссворд Судоку Головоломки видеоигры Лабиринты Метапазлы
Темы Логические Дилемма Оптическая иллюзия Проблемы с упаковкой Парадокс Решение проблем Puzzlehunt Силлогизм Нестандартное мышление
Списки Невозможные головоломки Лабиринт видеоигры Типы пазлов Николи Головоломки видеоигры Темы-головоломки
v т е

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

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

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

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

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

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

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

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

В двойники окружности в других измерениях не могут быть упакованы с полной эффективностью в размерах больших , чем один (в одномерной Вселенной, круг аналог только две точки). То есть всегда будет неиспользуемое пространство, если вы будете только упаковывать круги. Самый эффективный способ упаковки кругов - гексагональная упаковка - дает примерно 91% эффективности. ^[8]

Сферы в высших измерениях [ править ]

В трех измерениях плотноупакованные структуры предлагают лучшую решетчатую упаковку сфер и считаются оптимальными из всех упаковок. С «простыми» сферическими насадками в трех измерениях («простая» следует четко определить) существует девять возможных определяемых упаковок. ^[9] 8-мерная решетка E8 и 24-мерная решетка Лича также оказались оптимальными в их соответствующих реальных размерных пространствах.

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

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

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

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

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

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

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

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

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

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

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

Определить количество сферических объектов данного диаметра D , которые могут быть упакованы в параллелепипеда с размером в × б × с .

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

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

Многогранники в сферах [ править ]

Определите минимальный радиус R, который будет содержать n одинаковых многогранников единичного объема заданной формы. ^[13]

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

Исследовано множество вариантов двумерных задач упаковки. См. Связанные страницы для получения дополнительной информации.

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

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

• Упаковка кругов в круг - тесно связана с распределением точек в единичном круге с целью нахождения наибольшего минимального расстояния d _n между точками. Оптимальные решения доказаны для n  ≤ 13 и  n  = 19.
• Упаковка кругов в квадрат - тесно связана с распределением точек в единичном квадрате с целью нахождения наибольшего минимального расстояния d _n между точками. Чтобы преобразовать эти две формулировки задачи, сторона квадрата для единичных кругов будет L  = 2 + 2 / d _n .
  Оптимальная упаковка 15 кругов в квадрате
  Оптимальные решения доказаны для n  ≤ 30.
• Упаковка кругов в равнобедренный прямоугольный треугольник - хорошие оценки известны для n <300.
• Упаковка кругов в равносторонний треугольник. Оптимальные решения известны для n <13, и имеются гипотезы для n  <28. ^[14]

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

Вам дано n квадратов, и вы должны упаковать их в наименьший из возможных контейнеров, в зависимости от типа контейнера:

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

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

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

Связанные поля [ править ]

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

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

× б прямоугольник может быть упакован с 1 × п полосы тогда и только тогда п делит к или п делит б . ^{[15] [16]}

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

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

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

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

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

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

См. Также [ править ]

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

Заметки [ править ]

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

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме " Проблемы с упаковкой" .

• Оптимизация трехмерной упаковки контейнеров
• API для трехмерной упаковки бункеров
• Упаковка 3D-коробок и баллонов с телескопированием

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

• Ссылки на различные статьи MathWorld по упаковке
• Заметки MathWorld об упаковке квадратов.
• Центр упаковки Эриха
• www.packomania.com Сайт с таблицами, графиками, калькуляторами, справочниками и т. д.
• "Упаковка коробки" от Ed Пегг, младший , в Wolfram Demonstrations Project 2007.
• Наиболее известные упаковки равных кругов в круге, до 1100

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