Моделирование игры безопасности, разработка и оптимизации алгоритма

1.

Министерство науки и высшего образования Российской Федерации
Санкт-Петербургский политехнический университет Петра Великого
Физико-механческий институт
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
РАБОТА БАКАЛАВРА
МОДЕЛИРОВАНИЕ ИГРЫ БЕЗОПАСНОСТИ , РАЗРАБОТКА И ОПТИМИЗАЦИИ АЛГОРИТМА.
По направлению подготовки 01.03.02 Прикладная математика и информатика
Направленность (профиль) 01.03.02_01 Математическое моделирование и исскусственный интеллект
Выполнил
студент гр. 5030102/00101
Х.Л. Нгуен
Руководитель
профессор ВШВМВФ, д.т.н.
Ф.А. Новиков
Санкт-Петербург – 2024

2.

Актуалность
- Защита национальной инфраструктуры, является непростой задачей для
органов безопасности.
- Ограниченность ресурсов означает, что обычно невозможно обеспечить
полную безопасность в любое время.
- Грабители могут наблюдать за механизмами безопасности с течением
времени и использовать любые предсказуемые закономерности в своих
интересах.
- В большинстве областей патрулирования безопасности агенты безопасности
не могут постоянно исследовать все области.
- Вместо этого они выбирают политику, согласно которой они патрулируют
различные маршруты в разное время, учитывая такие факторы, как
вероятность совершения преступлений в разных районах.
2/17

3.

Цель и задачи
Цель: моделирование игры безопасности и оптимизации алгоритма.
Задачи:
- Исследование теории игры, включая: игру в нормальной форме, чистую
стратегию, смешанную стратегию, равновесие Нэша, существование равновесия
Нэша со смешанной стратегией.
- Моделирование игры безопасности, включ: игроков, награды и потери для
каждого игрока, чистую стратегию для каждого игрока.
- Учитывая сложность задачи . Использование линейного программирования для
решения проблемы. Доказательство того, что решение линейного
программирования является оптимизацией вознаграждения агента безопасности.
- Оптимизация алгоритма, сравнение времени выполнения.
3/17

4.

Постановка задачи
4/17

5.

Оценка сложности
• NP-полно.
• Задача может быть решена за полиномиальное время.
• Линейное программирование :
5/17

6.

Эвритический подход
-Ограничиваем возможные смешанные стратегии лидера выбором
1
действий с вероятнотями, кратными