TY - JOUR

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

AU - Абрамовская, Т.В.

AU - Петров, Н.Н.

PY - 2012

Y1 - 2012

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

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

UR - https://elibrary.ru/item.asp?id=25068873

M3 - Обзор литературы

SP - 9

EP - 65

JO - ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ И ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ И ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1817-2172

IS - 2

ER -