ТЕОРЕТИЧНІ ОЦІНКИ СКЛАДНОСТІ АЛГОРИТМІВ ІТЕРАЦІЙНИХ МЕТОДІВ ТИПУ БРАУНА-РОБІНСОН ДЛЯ РОЗВ’ЯЗУВАННЯ КОМБІНАТОРНИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ ІГРОВОГО ТИПУ

Автор(и)

DOI:

https://doi.org/10.32782/tnv-tech.2024.3.6

Ключові слова:

мінімальний програш, стратегії гравців, обмеження-перестановки, максимальний виграш

Анотація

Комбінаторні оптимізаційні задачі ігрового типу є однією з найважливіших категорій задач в області теорії ігор і оптимізації. Вони охоплюють широкий спектр проблем, від розподілу ресурсів до стратегічного планування в умовах конфлікту. Ітераційні методи, зокрема метод Брауна-Робінсон, є класичними підходами до розв’язання таких задач. Потреба в розв'язуванні комбінаторних оптимізаційних задач ігрового типу на множинах перестановок та розміщень підкреслює важливість дослідження можливості модифікації існуючих методів та оцінки їхньої складності. Виконано розширення ітераційного методу для задач комбінаторної оптимізації ігрового типу з різними комбінаторними конфігураціями. Стаття починається з опису алгоритмів методів типу Брауна-Робінсон, що використовуються для розв’язування комбінаторних оптимізаційних задач ігрового типу на множинах перестановок та розміщень. Далі основний акцент робиться на теоретичних оцінках складності цих алгоритмів. Розглядається кількість ітерацій, необхідних для досягнення оптимального розв’язання, а також асимптотична складність алгоритмів у залежності від розмірності задачі та параметрів. Досліджуються умови збіжності алгоритмів. Визначаються межі складності для найгірших сценаріїв, де алгоритми можуть демонструвати максимальну складність. Для ітераційних методів типу Брауна-Робінсон, що розв'язує комбінаторні оптимізаційні задачі ігрового типу з обмеженнями у вигляді перестановок, накладеними на стратегії обох гравців, та для розв’язування ігрових задач з обмеженнями-розміщеннями на стратегії одного гравця. отримано теоретичні оцінки складності, сформульовані у вигляді теорем. Результати дослідження підтверджують, що ітераційні методи типу Брауна-Робінсон є ефективними інструментами для розв’язання комбінаторних оптимізаційних задач ігрового типу. Проте їх обчислювальна складність значною мірою залежить від специфіки задачі. Подальші дослідження у цьому напрямку можуть значно покращити розуміння і застосування цих методів у практиці, сприяючи розвитку теорії ігор і комбінаторної оптимізації.

Посилання

Ємець О. О. Ольховська О. В. Монотонний ітераційний метод для розв’язування задач комбінаторної оптимізації ігрового типу на переставленнях. Доповіді Національної академії наук України. 2014. №8. С. 48-52.

Слабінога М. О., Чабан С. В. Розробка веб-додатків в контексті оптимізації їх швидкодії. Таврійський науковий вісник. Серія: Технічні науки, 2022, (3), 63-69. https://doi.org/10.32851/tnv-tech.2022.3.7

Стоян Ю. Г., Ємець О. О. Теорія і методи евклідової комбінаторної оптимізації. К., ІСДО, 1993. 188 с.

Черненко Н. Штучний інтелект в управлінні персоналом. Таврійський науковий вісник. Серія: Економіка, 2022, (12), 76-83. https://doi.org/10.32851/2708-0366/2022.12.11

Avinash K Dixit, Susan Skeath, David McAdams Games of Strategy. Fifth Edition, 2020, 1853 р.

Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Courier Corporation, 1998. 496 р.

Dexter C Kozen. The Design and Analysis of Algorithms, 1990, 25 р.

Fraenkel A. Combinatorial games: Selected bibliography with a succinct gourmet introduction. Games of No Chance 3. Vol. 56. 2009. Р. 491–575.

Jon Kleinberg, Eva Tardos Algorithm design. 1st ed., 2006. 864 р.

Nowakowski, Richard J., Landman, Bruce M., Luca, Florian, Nathanson, Melvyn B., Nešetřil, Jaroslav and Robertson, Aaron. Combinatorial Game Theory: A Special Collection in Honor of Elwyn Berlekamp, John H. Conway and Richard K. Guy, Berlin, Boston: De Gruyter, 2022. https://doi.org/10.1515/978311075541

Thomas H Cormen, Charles E Leiserson, Ronald L, Clifford Stein Rivest Introduction to Algorithms, 3rd Edition, 2009. 1292 р.

##submission.downloads##

Опубліковано

2024-09-23

Як цитувати

Ольховська, О. В., Кошова, О. П., Гаркуша, С. В., & Тур, В. М. (2024). ТЕОРЕТИЧНІ ОЦІНКИ СКЛАДНОСТІ АЛГОРИТМІВ ІТЕРАЦІЙНИХ МЕТОДІВ ТИПУ БРАУНА-РОБІНСОН ДЛЯ РОЗВ’ЯЗУВАННЯ КОМБІНАТОРНИХ ОПТИМІЗАЦІЙНИХ ЗАДАЧ ІГРОВОГО ТИПУ. Таврійський науковий вісник. Серія: Технічні науки, (3), 51-61. https://doi.org/10.32782/tnv-tech.2024.3.6

Номер

Розділ

КОМП’ЮТЕРНІ НАУКИ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ