2024, випуск 4, c. 5-21
Одержано 05.09.2024; Виправлено 29.09.2024; Прийнято 03.12.2024
Надруковано 18.12.2024; Вперше Online 23.12.2024
https://doi.org/10.34229/2707-451X.24.4.1
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Використання r-алгоритму для пакування нерівних кругів у круг мінімального радіусу
Б.О. Задорожний 1 *, Т.Є.
Романова 2 
, П.І. Стецюк 1, 3
, С.Р. Тиводар 1,
С.Б. Шеховцов 4
1 Ужгородський національний університет
2 Університет Лідса, Велика Британія
3 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
4 Харківський національний університет радіоелектроніки
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Досліджено два способи використання r-алгоритму Шора для задачі пакування нерівних кругів в зовнішній круг мінімального радіусу. Перший спосіб реалізує багаторазовий запуск r-алгоритму з дихотомією кроку із допустимої стартової точки, в якій досягається знайдений евристичним алгоритмом найменший радіус зовнішнього круга. Розглядаються дві версії алгоритму. Для першої версії величина кроку зменшується вдвічі по ходу ітераційного процесу, а для другої – додається опція, яка дозволяє відновлювати максимальне значення величини кроку r-алгоритму. Алгоритм реалізовано мовою програмування Rust з використанням бібліотеки nalgebra.
Другий спосіб має на меті дослідження щодо підвищення точності за значенням радіуса зовнішнього круга локальних мінімумів багатоекстремальної негладкої функції та зменшення числа ітерацій r-алгоритму за рахунок підвищення розрядності чисел (128 та 256 біт). Відповідний алгоритм реалізований мовою програмування Julia. Обчислювальні експерименти проводилися для тестової задачі з п’ятю кругами та порівнювалися з розв’язками, наведеними на веб-сайті http://www.packomania.com/. Показано, що з підвищенням розрядності чисел кількість ітерацій r-алгоритму зменшується, а точність знаходження радіусу зовнішнього круга зростає. При правильно підібраних параметрах r-алгоритм знаходить всі 28 цифр після коми, які представлені на веб-сайті http://www.packomania.com/.
Ключові слова: пакування кругів, r-алгоритм, евристичний алгоритм, Rust, Julia.
Цитувати так: Задорожний Б.О., Романова Т.Є., Стецюк П.І., Тиводар С.Р., Шеховцов С.Б. Використання r-алгоритму для пакування нерівних кругів у круг мінімального радіусу. Cybernetics and Computer Technologies. 2024. 4. С. 5–21. https://doi.org/10.34229/2707-451X.24.4.1
Список літератури
1. Задорожний Б.О., Міца О.В., Стецюк П.І. Про покращення евристичного алгоритму упаковки кругів в круг мінімального радіусу. Cybernetics and Computer Technologies. 2023. 2. С. 32–45. https://doi.org/10.34229/2707-451X.23.2.4
2. Задорожний Б.О., Романова Т.Є., Стецюк П.І. Покращення евристичного алгоритму пакування нерівних кругів із застосуванням r-алгоритму Шора. Матеріали XXVI Міжнародного науково-практичного семінару «Комбінаторні конфігурації та їхні застосування» (Кропивницький–Запоріжжя–Київ, 13-15 червня 2024 року). Кропивницький: ПП «ЕксклюзивСистем», 2024. С. 59–65.
3. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.
4. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dordrecht, London. 1998. 412 p.
5. Стецюк П.І., Романова Т.Є., Тиводар С.Р. Використання солвера BARON для розв’язання квадратичної задачі оптимальної упаковки нерівних кругів. Матеріали XXVI Міжнародного науково-практичного семінару «Комбінаторні конфігурації та їхні застосування» (Кропивницький–Запоріжжя–Київ, 13-15 червня 2024 року). Кропивницький: ПП «ЕксклюзивСистем», 2024. С. 179–188.
6. Tawarmalani M., Sahinidis N.V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005. 103 (2). P. 225–249.
7. Sahinidis N.V., BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs, User's manual, 2021.
8. Щільна упаковка кругів в круг мінімального радіусу. Eolymp. https://packing-circles.eolymp.io (звернення: 23.05.2024).
9. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57.
10. Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных выпуклых функций. Вычислительные технологии. 2017. Т. 22, № 2. С. 127–149.
11. Стецюк П.І. Комп'ютерна програма "Octave-програма ralgb5a: r(α)-алгоритм з адаптивним кроком". Свідоцтво про реєстрацію авторського права на твір № 85010. Україна. Міністерство економічного розвитку і торгівлі. Державний департамент інтелектуальної власності. Дата реєстрації 29.01.2019.
12. Packomania. http://www.packomania.com/(звернення: 09.08.2023)
13. Romanova T., Pankratov A., Litvinchev I., Stetsyuk P., Lykhovyd O., Marmolejo-Saucedo J.A., Vasant P. Balanced Circular Packing Problems with Distance Constraints. Computation. 2022. Vol. 10, Iss. 7. P. 113. https://doi.org/10.3390/computation10070113
14. Романова Т.Є., Стецюк П.І., Чугай А.М., Шеховцов С.Б. Технології паралельних обчислень для розв’язання оптимізаційних задач геометричного проектування. Кибернетика и системный анализ. 2019. № 6. С. 17–29.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна