19:33 Задача упаковки |
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы полностью покрыть все области контейнера, при этом предметы могут накладываться. В задаче упаковки задано:
Обычно в упаковке объекты не должны пересекаться и объекты не должны пересекать стены контейнера. В некоторых вариантах цель заключается в нахождении конфигурации, которая упаковывает один контейнер с максимальной плотностью. В более общем виде целью является упаковка всех объектов в как можно меньшее число контейнеров. В некоторых вариантах наложение (объектов друг на друга и/или на границы контейнера) разрешается, но это наложение должно быть минимизировано. Упаковка бесконечного пространства Многие из этих задач, если размер контейнера увеличивается во всех направлениях, становятся эквивалентны задачам упаковки объектов как можно плотнее в бесконечном евклидовом пространстве. Эта задача относится к некоторому числу научных дисциплин и получает существенное внимание. Шестиугольная упаковка кругов Эти задачи математически отличаются от идей в теореме об упаковке кругов. Связанная задача упаковки кругов имеет дело с упаковкой кругов, возможно различных размеров, на поверхности, например, на плоскости или сфере. Аналоги круга в других размерностях не могут быть упакованы с абсолютной эффективностью в размерностях, больших единицы (в одномерном пространстве аналог окружности — просто две точки). Таким образом, всегда останется незанятое пространство при упаковке исключительно кругами. Наиболее эффективный путь упаковки кругов, шестиугольная упаковка, даёт примерно 91 % эффективности. Упаковка сфер в высших размерностях В трёхмерном пространстве гранецентрированная решётка даёт оптимальную упаковку сфер. Доказано, что 8-мерная решётка E8 и 24-мерная решётка Лича оптимальны в соответствующих пространствах. Упаковка платоновых тел в трёхмерных пространствах Кубы легко могут быть расположены в трёхмерном пространстве так, что они полностью заполнят пространство. Наиболее естественная упаковка — кубические соты. Никакой другой правильный многогранник не может заполнить полностью пространство, но некоторые результаты известны. Тетраэдр может дать упаковку по меньшей мере 85 %. Одна из лучших упаковок правильными додекаэдрами основывается на гранецентрированной кубической решётке. Тетраэдры и октаэдры вместе могут заполнить всё пространство в конфигурации, известной как тетраэдрально-октаэдральная мозаика. Моделирование, совмещающее методы локального улучшения со случайно сгенерированными упаковками, наводит на мысль, что решётчатые упаковки для икосаэдра, додекаэдра и октаэдра являются оптимальными и в более широком классе всех упаковок. По материалам сайта: |
|
|
| Всего комментариев: 0 | |