Некоторые вопросы сложности решения циклических игр на графах
Автор: Башлаева Ирина Александровна, Штельмах Татьяна Владимировна
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Прикладная математика
Статья в выпуске: 2 (21), 2014 года.
Бесплатный доступ
В работе дано уточнение верхней оценки сложности алгоритма потенциальных преобразований для решения циклических игр на графах. Оценка близка к нижней оценке сложности алгоритма потенциальных преобразований. Получено сведение задачи об оптимальном уклонении к решению циклических игр с временной функцией на ребрах на ориентированных графах.
Циклические игры с полной информацией, позиционные игры, стационарные равновесия по нэшу, гарантированная временная сложность, алгоритм потенциальных преобразований
Короткий адрес: https://sciup.org/14968958
IDR: 14968958
Список литературы Некоторые вопросы сложности решения циклических игр на графах
- Гурвич, В. А. Циклические игры и нахождение минимаксных средних циклов в ориентированных графах/В. А. Гурвич, А. В. Карзанов, Л. Г. Хачиян//ЖВМ МФ. -1988. -Т. 28, № 9. -C. 1407-1417.
- Карзанов, А. В. О минимальных по среднему весу разрезах и циклах ориентированного графа/А. В. Карзанов//Качественные и приближенные методы исследования операторных уравнений. -1985. -C. 72-83.
- Кларк, Э. М. Верификация моделей программ/Э. М. Кларк, О. Грамберг-мл., Д. Пелед. -М.: Изд-во Моск. центра непрерыв. мат. образования, 2002. -416 c.
- Bouyer, P. Infinite runs in weighted timed automata with energy constraints. In: Proc of FORMATS: formal modeling and analysis of timed systems/P. Bouyer, U. Fahrenberg, K. G. Larsen, N. Markey, J. Srba//LNCS. -2008. -Issue 5215. -P. 33-47.
- Lifshits, Y. M. Potential theory for mean payoff games/Y. M. Lifshits, D. S. Pavlov//Записки научных семинаров ЛОМИ. -2006. -Т. 340. -C. 61-75.
