Алгоритмы построения оптимальных упаковок шаров в эллипсоиды

Abstract

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