Рассматривается задача упаковки шаров двух типов в замкнутое ограниченное множество в трехмерном пространстве как с евклидовой, так и со специальной неевклидовой метрикой. Требуется максимизировать радиус шаров при известном количестве шаров каждого типа и заданном отношении между радиусами. Предложен вычислительный алгоритм, основанный на комбинации метода бильярдного моделирования и оптико-геометрического подхода, базирующегося на фундаментальных физических принципах Ферма и Гюйгенса. Приведены результаты вычислительного эксперимента.
Идентификаторы и классификаторы
Задачи упаковки, как определено в работе [4], состоят в расположении набора геометрических объектов фиксированных размеров и/или формы в заданной области. При этом, как правило, либо максимизируется число упаковываемых объектов при фиксированном размере, либо их размеры (площадь поверхности, объем, радиус и др.) при заданном количестве, также можно рассматривать задачу минимизации объема контейнера. В настоящей статье мы рассматриваем объекты, имеющие вид шаров.
Хотя проблема упаковки равных шаров в бесконечное пространство решена — показано, что плотнейшими упаковками являются гранецентрированная кубическая (ГЦК) и гексагональная плотная (ГП) с плотностью π/(3√ 2), однако для случая ограниченного контейнера эта проблема остается открытой [5]. Следует отметить, что в большинстве работ в качестве контейнеров выступают множества простой формы: сфера, куб, тетраэдр и др. Приведем краткий обзор известных научных результатов по данной тематике.
В работах [6, 7] рассмотрена задача упаковки одинаковых шаров заданного радиуса в параллелепипед минимальной высоты (длина и ширина известны) и в цилиндр с известным радиусом и минимальной высотой, предложена стратегия ее решения, которая включает в себя построение специального дерева поиска, модификацию метода возможных направлений для вычисления локальных минимумов и модификацию метода сужающихся окрестностей для поиска приближения к глобальному минимуму.
Для решения задачи упаковки равных шаров в [8] предложен алгоритм последовательного симметричного перемещения, представлены плотные упаковки до 200 шаров в сферу и до 150 шаров в куб. В [9] решается задача упаковки шаров в бесконечно длинный цилиндр с заданным радиусом с использованием метода имитации отжига. Проблема нахождения плотнейшей упаковки шаров в цилиндр рассматривается и в [10], где она решается с помощью адаптивно-сжимающейся ячейки и метода последовательного линейного программирования.
Список литературы
- Castillo I., Kampas F.J., Pintér J.D. Solving circle packing problems by global optimization: numerical results and industrial applications // European Journal of Operational Research. 2008. 191, N 3. 786-802. EDN: YAMFWB
- Harary F., Randolph W., Mezey P.G. A study of maximum unit-circle caterpillars - tools for the study of the shape of adsorption patterns // Discrete Applied Mathematics. 1996. 67, N 1-3. 127-135. EDN: ALTEAP
- Wang J. Packing of unequal spheres and automated radiosurgical treatment planning // Journal of Combinatorial Optimization. 1999. 3. 453-463. EDN: AGSEPB
- Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry. 2010. 43, N 5. 535-553. EDN: VAUZYQ
- Hales T. Cannonballs and honeycombs // Notices of the American Mathematical Society. 2000. 47, N 4. 440-449.
- Stoyan Y., Yaskov G. Packing identical spheres into a rectangular parallelepiped // Intelligent Decision Support. Wiesbaden: Betriebswirtschaftlicher Verlag Dr. Th. Gabler, 2008. 47-67.
- Stoyan Yu.G., Yaskov G. Packing identical spheres into a cylinder // International Transactions in Operational Research. 2009. 17, N 1. 51-70. EDN: YAXTVB
- Huang W., Yu L. Serial symmetrical relocation algorithm for the equal sphere packing problem. Ithaca: Cornell Univ. Library, 2012. Available at https://arxiv.org/abs/1202.4149.
- Mughal A., Chan H., Weaire D., Hutzler D. Dense packings of spheres in cylinders: simulations // Physical Review E. 2012. 85. DOI: 10.1103/PhysRevE.85.051305
-
Fu L., Steinhardt W., Zhaod H., Socolar J.E.S., Charbonneau P. Hard sphere packings within cylinders // Soft Matter. 2016. 12. 2505-2514. EDN: XMPBQH
-
Scheithauer G., Stoyan Yu., Yaskov G. Packing non-equal spheres into containers of different shapes. 2013. http://www.math.tu-dresden.de/~scheith/ABSTRACTS/2013-spheres.html.
-
Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal spheres into various containers // Cybernetics and Systems Analysis. 2016. 52, N 3. 419-426. EDN: XNQATX
-
Khlud O.M., Yaskov G.N. Packing homothetic spheroids into a larger spheroid with the jump algorithm // Control, Navigation and Communication Systems. 2017. 6, N 46. 131-135.
-
Kubach T., Bortfeldt A., Tilli T., Gehring H. Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. 2009. https://www.fernuni-hagen.de/wirtschaftswissenschaft/download/beitraege/db440.pdf.
-
Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Asia Pacific Journal of Operational Research. 2011. 28, N 6. 739-753. EDN: YCSPUF
-
Huang W.Q., Li Y., Akeb H., Li C.M. Greedy algorithms for packing unequal circles into a rectangular container // Journal of the Operational Research Society. 2005. 56, N 5. 539-548. EDN: XOETDL
-
Hifi M., Yousef L. Width beam and hill-climbing strategies for the three-dimensional sphere packing problem // 2014 Federated Conference on Computer Science and Information Systems. New York: IEEE Press, 2014. 421-428.
-
Yamada S., Kanno J., Miyauchi M. Multi-sized sphere packing in containers: optimization formula for obtaining the highest density with two different sized spheres // IPSJ Online Transactions. 2011. 4. 126-133.
-
Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50-57. EDN: NXCWVD
-
Бухаров Д.С., Казаков А.Л. Программная система "ВИГОЛТ" для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. 13 65-74. EDN: PIXMUB
-
Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87-100. EDN: QIULKJ
-
Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. 13, N 1. 200-210. EDN: UFNZOR
-
Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование. 2015. 16. 307-317. EDN: YTTXBZ
-
Казаков А.Л., Лемперт A.A., Нгуен Г.Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2016. 17. 177-188. EDN: YTTXQT
-
Kazakov A.L., Lempert A.A., Ta T.T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFAC-PapersOnLine. 2018. 51, N 32. 782-787. EDN: XXSBKH
-
Kazakov A.L., Lempert A.A., Ta T.T. On the algorithm for equal balls packing into a multi-connected set // VIth International Workshop on Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security (IWCI 2019). Paris: Atlantis Press, 2019. 216-222.
-
Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.
-
Graham R.L., Lubachevsky B.D., Nurmela K.J., Ostergard P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. 181, N 1-3. 139-154. EDN: INBXDO
Выпуск
Другие статьи выпуска
В статье рассматриваются результаты экспериментальной оценки производительности и энерго-эффективности многоядерных процессоров MALT в задачах обработки изображений на примере фильтрации изображения с помощью оператора Собеля. Измерения осуществлялись с использованием низкоуровневого эмулятора MALTemu, прототипа процессора в ПЛИС и экспериментальной СБИС модели MALT-Cv2 Rev1. Полученные результаты сравниваются с аналогичными результатами для процессоров общего назначения (последовательная реализация) и графических процессоров с поддержкой технологии CUDA.
Предложен новый метод восстановления изображений, имеющих три неизвестные градации яркости. Для их определения используются фрагменты изображения, гистограммы которых согласуются с заданным распределением шума. Далее все пиксели распределяются по найденным уровням яркости посредством бинарной классификации. Выполнен вычислительный эксперимент, по результатам которого оказалось, что ошибка оценки исходных яркостей не превысила 3%. При относительно низком уровне шума доля неверно классифицированных пикселей от их общего числа составила менее 0.006.
Рассматривается нелинейная модификация стохастической модели галактического динамо, в рамках которой коэффициент, отвечающий за турбулентную диффузию, полагается случайным процессом с обновлением. Показано, что при малых значениях напряженности магнитного поля его статистические моменты ведут себя примерно так же, как и в линейной модели (в частности, продемонстрировано наличие эффекта перемежаемости). Получены оценки для характерных времен выхода моментов на стабилизацию, которая наступает по мере приближения поля к равновесному значению. Проведено сопоставление результатов численного эксперимента, полученных при усреднении различных объемов выборки независисмых случайных реализаций поля.
Функционалы Минковского являются важным инструментом для изучения морфологии пористых сред. Настоящая работа посвящена построению алгоритма вычисления функционалов Минковского четырехмерных цифровых изображений, возникающих, в частности, при описании динамики изменения порового пространства среды. В работе впервые программно реализован алгоритм вычисления функционалов Минковского четырехмерных цифровых изображений.
Приведено описание программного комплекса для математического моделирования эволюции термопороупругой среды с учетом ее разрушения. Используемая математическая модель является модификацией модели Био для случая термопороупругих сред и позволяет моделировать изменение напряженно-деформированного состояния среды, фильтрацию флюида, неизотермические эффекты, а также разрушение среды. Разрушение среды описывается с использованием подхода континуальной механики разрушения путем введения дополнительной переменной, называемой параметром повреждаемости. Этот параметр характеризует степень разрушения среды, а его эволюция определяется заданным кинетическим уравнением. Вычислительный алгоритм основан на методе конечных элементов. Дискретизация уравнений по времени производится по неявной схеме для перемещений, давления и температуры и по явной для параметра повреждаемости. В качестве конечных элементов выбраны элементы Тейлора-Худа, имеющие второй порядок аппроксимации по перемещениям и первый по давлению и температуре. Система уравнений решается в рамках “монолитной” постановки без итерационного связывания между группами уравнений. Рассмотрены результаты расчетов с использованием программного модуля на примере задачи термического воздействия на нефтяной пласт.
Статья посвящена развитию гибридного метода крупных частиц применительно к двумерным течениям с развитием физической неустойчивости на поверхностях раздела неоднородных газовых смесей. Высокая разрешающая способность метода продемонстрирована при решении задач взаимодействия ударной волны с цилиндрическим пузырем легкого или тяжелого газов в сравнении с экспериментом и расчетами по другим схемам повышенного порядка аппроксимации.
Издательство
- Издательство
- МГУ
- Регион
- Россия, Москва
- Почтовый адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- Юр. адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- ФИО
- Садовничий Виктор Антонович (РЕКТОР)
- E-mail адрес
- info@rector.msu.ru
- Контактный телефон
- +7 (495) 9391000
- Сайт
- https://msu.ru/