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

редактировать

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

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

Покрытие проблем	Проблемы с упаковкой
Крышка минимального набора	Максимальный набор упаковки
Минимальное краевое покрытие	Максимальное соответствие
Минимальное покрытие вершины	Максимальный независимый набор
Покрытие мусорного ведра	Бин упаковка
Полигональное покрытие	Прямоугольная упаковка

Типы

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

Темы

Нестандартное мышление

Списки

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

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

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

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

СОДЕРЖАНИЕ

1 Упаковка в бесконечном пространстве
- 1.1 Гексагональная упаковка кругов
- 1.2 Сферические уплотнения больших размеров
- 1.3 Упаковка Платоновых тел в трех измерениях
2 Упаковка в 3-х мерную тару
- 2.1 Различные кубоиды в кубоид
- 2.2 Сферы в евклидов шар
- 2.3 Сферы в кубоиде
- 2.4 Идентичные сферы в цилиндре
- 2.5 Многогранники в сферах
3 Упаковка в 2-х мерную тару
- 3.1 Упаковка кружков
- 3.2 Упаковка квадратов
- 3.3 Упаковка прямоугольников
4 Связанные поля
5 Упаковка нестандартных предметов
6 См. Также
7 Примечания
8 ссылки
9 Внешние ссылки

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

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

Гексагональная упаковка кругов

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

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

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

Сферические уплотнения в больших размерах

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

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

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

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

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

Твердый	Оптимальная плотность решетчатой упаковки
икосаэдр	0,836357...
додекаэдр	(5 + √ 5) / 8 = 0,904508...
октаэдр	18/19 = 0,947368...

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

Упаковка в 3-х мерную тару

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

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

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

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

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

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

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

Идентичные сферы в цилиндре

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

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

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

Упаковка в 2-х мерную тару

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

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

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

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

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

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

Вам дано 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 × п полосы тогда и только тогда п делит к или п делит б.

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

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

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

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

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

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

Смотрите также

Примечания

использованная литература

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

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

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

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