ТЕОРЕТИЧНА ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ РОЗВ’ЯЗУВАННЯ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ІГРОВОГО ТИПУ
Main Article Content
Abstract
Серед задач комбінаторної оптимізації все актуальнішими стають задачі розв’язування конфліктних ситуацій, конкуренції, які відносяться до класу задач комбінаторної оптимізації ігрового типу з обмеженнями на стратегії гравців, що визначаються комбінаторними конфігураціями, зокрема множинами перестановок та розміщень. Для таких задач необхідними є дослідження існуючих методів розв’язування, вивчення питання можливості їхньої модифікації, а також проведення числових експериментів з метою визначення їх практичної ефективності.
Article Details
References
1. Bachet C. G. Problèmes plaisans et délectables, qui se font par les nombres, partie recueillis de divers autheurs, et inventez de nouveau, avec leur démonstration. / C. G. Bachet – Lyons, France: Pierre Rigaud & Associates, 1612. – P. 18-33.
2. Фролов И. С. Введение в теорию комбинаторных игр./ И. С.Фролов – М., 2012. – 202 с.
3. Bouton C. L. Nim, a game with a complete mathematical theory / C. L. Bouton – Annals of Mathematics, 1902. – P. 35–39.
4. Berlekamp R. Elwyn Winning Ways for Your Mathematical Plays. // Elwyn R. Berlekamp , John H. Conway, Richard K. Guy / A K Peters, Wellesley, MA, 2nd edition, 2001–2004. – 276 р.
5. Conway H. J. On Numbers and Games. // John H. Conway / A K Peters, Wellesley, MA, 2nd edition, 2001. – 417 р. 6.
6.Conway J. H. All games bright and beautiful. // John H. Conway / American Math. – Vol. 84. – 1977. – Р. 417–434.
7. Нейман Дж. Теория игр и экономическое поведение / Дж. Нейман, О. Моргенштерн. – М.: Наука, 1970. – 780 с.
8. Емец О. А. Исследование задач комбинаторной оптимизации игрового типа на размещениях / О. А. Емец, Н. Ю. Устьян // Проблемы управления и информатики. – 2007. – № 1. – С. 26-36.
9. Емец О. А. Исследование математических моделей и методов решения задач на перестановках игрового типа / О. А. Емец, Н. Ю. Устьян // Кибернетика и сист. анализ. – 2007. – №6. – С. 103-114.
10. Ємець О. О. Розв’язування ігрових задач на перестановких / О. О. Ємець, Н. Ю. Устьян // Наукові вісті НТУУ “КПІ”. – 2007. – №3. – С. 47-52.
11. Ємець О. О. Один ітераційний метод розв’язування ігрових задач на перестановких / О. О. Ємець, Н. Ю. Устьян // Наукові вісті НТУУ “КПІ”. – 2008. – №3. – С.5-10.
12. Емец О. А. Игры с комбинаторными ограничениями / О. А. Емец, Н. Ю. Устьян // Кибернетика и сист. анализ. – 2008. – №4. – С.134-141.
13. Емец О. А. Итерационный метод решения комбинаторных оптимизационных задач игрового типа на размещениях / О. А.Емец, Е. В. Ольховская. // Проблемы управления и информатики. – 2011. – № 3. – С. 69 78.
14. Brown G.W. Iterative solution of games by fictitious play/ Brown G.W. // Activity analysis of production and allocation: Proceedings of a Conference. – 1951. – New York. – P. 374-376.
15. Алгоритмы: построение и анализ, 2-е изд./ Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. — М.: Вильямс, 2005. — 1296 с.
16. Стоян Ю. Г. Теорія і методи евклідової комбінаторної оптимізації / Ю. Г. Стоян, О. О. Ємець. – К.: ІСДО, 1993. – 188 с.
17. Ємець О.О. Розв’язування комбінаторних задач ігрового типу з обмеженнями-перестановкими у обох гравців: ітераційний метод / О.О. Ємець, О.В. Ольховська. // Системні дослідження та інфораційні технології. – 2012. – №4. – С. 80-93.
18. Ємець О. О. Монотонний ітераційний метод для розв’язування задач комбінаторної оптимізації ігрового типу на переставленнях / О. О. Ємець, О. В. Ольховська // Доповіді Національної академії наук України – 2014. – №8. – С. 48-52.