Теория гарантированного поиска на графах

Т.В. Абрамовская, Н.Н. Петров

Research output

Abstract

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

Cite this