ТЕОРЕТИЧНА ОЦІНКА СКЛАДНОСТІ АЛГОРИТМІВ РОЗВ’ЯЗУВАННЯ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ІГРОВОГО ТИПУ
##plugins.themes.bootstrap3.article.main##
Анотація
Серед задач комбінаторної оптимізації все актуальнішими стають задачі розв’язування конфліктних ситуацій, конкуренції, які відносяться до класу задач комбінаторної оптимізації ігрового типу з обмеженнями на стратегії гравців, що визначаються комбінаторними конфігураціями, зокрема множинами перестановок та розміщень. Для таких задач необхідними є дослідження існуючих методів розв’язування, вивчення питання можливості їхньої модифікації, а також проведення числових експериментів з метою визначення їх практичної ефективності.
##plugins.themes.bootstrap3.article.details##
Посилання
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.