Послідовний мультістартовий алгоритм розміщення багатовимірних куль.
DOI:
https://doi.org/10.30837/bi.2026.1(104).16Ключові слова:
БАГАТОВИМІРНА КУЛЯ, NP-СКЛАДНА ЗАДАЧА, МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ, ПОСЛІДОВНА ОПТИМІЗАЦІЯ, МУЛЬТІСТАРТОВИЙ АЛГОРИТМАнотація
У роботі розглядається задача розміщення конгруентних багатовимірних куль у евклідовому просторі в кулі мінімального радіуса, яка належить до класу NP-складних. Запропоновано швидкий послідовний мультістартовий алгоритм розміщення куль, який ґрунтується на поетапному додаванні елементів до конфігурації з локальним уточненням положення кожної нової кулі. На кожному кроці для чергової кулі генерується початкове допустиме положення, після чого здійснюється спрямований пошук у напрямку до початку координат. За допомогою дихотомії локалізації визначається перший контакт із уже розміщеними кулями, що дає змогу сформувати обмежену множину активних геометричних обмежень. Подальше уточнення положення нової кулі виконується в локальному околі точки контакту. На заключному етапі оптимізаційного процесу для зменшення залежності результату від вибору стартової точки використовується мультистартова стратегія для останніх куль, після чого обирається найліпше з отриманих локально допустимих розміщень. Це дає змогу зменшити накопичення локальних геометричних дефектів без виконання повної глобальної оптимізації. Запропонований алгоритм характеризується низькою обчислювальною складністю, добре масштабується з ростом розмірності простору та зберігає можливість розпаралелювання обчислень. Результати числових експериментів для розмірностей аж до d=64 підтверджують ефективність методу та поліпшення якості отриманих конфігурацій порівняно з одностартовими послідовними підходами.
Посилання
Conway J. H., Sloane N. J. A. (1999). Sphere Packings, Lattices and Groups, Springer New York, NY. https://doi.org/10.1007/978-1-4757-6568-7.Стоян Ю.Г., Яськов Г.М., Романова Т.Є., Яковлев С.В. (2021). Пакування сферичних об’єктів: моделі, методи, застосування. Київ: Наукова думка, 279 с.
Litvinchev I., Fischer A., Romanova T., Stetsyuk P. (2024). A New Class of Irregular Packing Problems Reducible to Sphere Packing in Arbitrary Norms.
Mathematics 12(7), 935.
https://doi.org/10.3390/math12070935.
Torquato S., Uche O. U., Stillinger F. H. (2006). Random sequential addition of hard spheres in high
Euclidean dimensions. Phys. Rev. E 74(6), 061308. https://doi.org/10.1103/PhysRevE.74.061308.
Ryan B. Jadrich, Beth A. Lindquist, Thomas M. Truskett (2022). Treating random sequential addition via the replica method. J. Chem. Phys. 157 (8), 084116. https://doi.org/10.1063/5.0096276.
Cohn H., Kumar A., Miller S., Radchenko D., Viazovska M. (2022). Universal optimality of the E8 and Leech lattices and interpolation formulas. Ann. of Math. (2) 196 (3), pp. 983– 1082. https://doi.org/10.4007/annals.2022.196.3.3.
Chen B., et al. (2023). Geometrically-Shaped Multi-Dimensional Modulation Formats in Coherent Optical Transmission Systems. Journal of Lightwave Technolog, 41(3), pp. 897–910. https://doi.org/ 10.1109/JLT.2022.3204101.
Favano A., Ferrari M., Magarini M., Barletta L. (2023). A Sphere Packing Bound for Vector Gaussian Fading Channels Under Peak Amplitude Constraints. IEEE Transactions on Information Theory. 69(1), pp. 238–250. https://doi.org/10.1109/TIT.2022.3203293.
Chen B.et al. (2025). On Shaping Gain of Multidimensional Constellations in Linear and Nonlinear Optical Fiber Channel, IEEE Journal on Selected Areas in Communications 43(5), pp. 1455–1468. https://doi.org/10.1109/JSAC.2025.3543507.
Wang X., Fujisawa M. Mikawa M. (2023). XProtoSphere: an eXtended multi-sized sphere packing algorithm driven by particle size distribution. Vis Comput 39, pp. 3333–3346. https://doi.org/10.1007/s00371-023-02977-w.
Andrei, N. (2022). Interior-Point Filter Line-Search. In: Modern Numerical Nonlinear Optimization. Springer Optimization and Its Applications, vol 195, pp. 661–678. Springer, Cham. https://doi.org/10.1007/978-3-031-08720-2_19.
