Татьяна Викторовна Абрамовская
Cанкт-Петербургский государственный университет,
математико-механический факультет
Аспирант
Николай Николаевич Петров
Cанкт-Петербургский государственный университет,
математико-механический факультет
Доктор физико-математических наук, Профессор
Рассматриваются некоторые задачи преследования-уклонения на графах, наиболее интересные результаты в этой области, а также многочисленные приложения теории гарантированного поиска в математике и других науках.
Предметом настоящего обзора являются, главным образом, задачи поиска, изучением которых активно занимаются выпускники и сотрудники кафедры исследования операций Санкт-Петербургского государственного университета, отметившей в 2010 году своё сорокалетие.
В самой общей постановке, задача поиска описывается как игра между группой преследователей и убегающим. На графе, являющемся фазовым ограничением для всех игроков, команда преследователей ловит невидимого для них убегающего. Различные формализации задачи поиска определяются динамическими возможностями участников, условием поимки и другими параметрами игры поиска. Искомое в каждой задаче поисковое число графа – это минимальное число преследователей, гарантирующих поимку убегающего при данных условиях.
Обсуждаются поставленные у самых истоков теории гарантированного поиска проблемы вычисления рёберно-поискового числа и тесно связанного с ним вершинно-поискового числа на графах. Исследуются проблемы гарантированного поиска с противодействием. Рассмотрение в качестве арены поиска топологических графов, по-видимому, существенно усложняют задачу поиска, о чём говорят результаты исследования задач с ограничением на скорости игроков и проблем поиска с радиусом поимки. Авторы формулируют также некоторые нерешённые проблемы теории гарантированного поиска.