Преследование–уклонение
-
Основы преследования-уклонения
- Преследование-уклонение — семейство задач в математике и информатике, где одна группа пытается выследить другую.
- Ранние модели использовали геометрию, в 1976 году Парсонс представил графическую формулировку.
-
Дискретная формулировка
- Окружающая среда моделируется в виде графа, где преследователи и уклоняющиеся занимают вершины.
- Преследователь может захватить уклоняющегося, если они находятся в одной вершине.
- Вопрос о количестве преследователей для поимки всех уклоняющихся является ключевым.
- Существуют различные варианты правил передвижения, включая скорость уклоняющихся и наличие «вертолетов» у преследователей.
-
Варианты и сложность
- Некоторые варианты эквивалентны параметрам графа, например, ширине дерева или минимальному доминирующему набору.
- Сложность задач преследования и уклонения была изучена, включая минимальное количество преследователей и минимальное время выполнения задачи.
-
Многопользовательские игры
- Многопользовательские игры с преследованием и уклонением также привлекли внимание, с алгоритмами для оптимального решения.
- Алгоритмы не масштабируются для большого числа игроков, поэтому разрабатываются методы разделения игры на несколько игр с меньшим числом игроков.
-
Непрерывная формулировка
- В непрерывной постановке задачи преследователи и уклоняющиеся моделируются геометрически, с ограничениями на маневренность и препятствиями.
- Бесикович доказал, что человек может бесконечно уклоняться от поимки в ограниченной среде.
-
Приложения
- Проблема преследования-уклонения использовалась в системах наведения ракет и других приложениях.
-
Ссылки
- В статье упоминаются другие связанные задачи, такие как проблема ангела и игра про принцессу и монстра.
Полный текст статьи: