Research output: Contribution to journal › Article › peer-review
Теория гарантированного поиска на графах. / Абрамовская, Т.В.; Петров, Н.Н.
In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ, No. 2, 2013, p. 3-39.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Теория гарантированного поиска на графах
AU - Абрамовская, Т.В.
AU - Петров, Н.Н.
PY - 2013
Y1 - 2013
N2 - Рассматриваются некоторые задачи преследования-уклонения на графах, наиболее интересные результаты в этой области, а также многочисленные приложения теории гарантированного поиска в математике и других науках. Предметом настоящего обзора являются, главным образом, задачи поиска, изучением которых активно занимаются выпускники и сотрудники кафедры исследования операций Санкт-Петербургского государственного университета. В самой общей постановке задача поиска описывается как игра между группой преследователей и убегающим. На графе, являющемся фазовым ограничением для всех игроков, команда преследователей ловит невидимого для них убегающего. Различные формализации задачи поиска определяются динамическими возможностями участников, условием поимки и другими параметрами игры поиска. Искомое в каждой задаче поисковое число графа — это минимальное число преследователей, гарантирующих поимку убегающего при данных условиях. Обсуждаются поставленные у самых истоков теории гарантированного поиска проблемы вычисления рёберно-поискового числа и тесно связанного с ним вершинно-поискового числа на графах. Исследуются проблемы гарантированного поиска с противодействием. Рассмотрение в качестве арены поиска топологических графов, по-видимому, существенно усложняют задачу поиска, о чём говорят результаты исследования задач с ограничением на скорости игроков и проблем поиска с радиусом поимки. Авторы формулируют также некоторые нерешённые проблемы теории гарантированного поиска.
AB - Рассматриваются некоторые задачи преследования-уклонения на графах, наиболее интересные результаты в этой области, а также многочисленные приложения теории гарантированного поиска в математике и других науках. Предметом настоящего обзора являются, главным образом, задачи поиска, изучением которых активно занимаются выпускники и сотрудники кафедры исследования операций Санкт-Петербургского государственного университета. В самой общей постановке задача поиска описывается как игра между группой преследователей и убегающим. На графе, являющемся фазовым ограничением для всех игроков, команда преследователей ловит невидимого для них убегающего. Различные формализации задачи поиска определяются динамическими возможностями участников, условием поимки и другими параметрами игры поиска. Искомое в каждой задаче поисковое число графа — это минимальное число преследователей, гарантирующих поимку убегающего при данных условиях. Обсуждаются поставленные у самых истоков теории гарантированного поиска проблемы вычисления рёберно-поискового числа и тесно связанного с ним вершинно-поискового числа на графах. Исследуются проблемы гарантированного поиска с противодействием. Рассмотрение в качестве арены поиска топологических графов, по-видимому, существенно усложняют задачу поиска, о чём говорят результаты исследования задач с ограничением на скорости игроков и проблем поиска с радиусом поимки. Авторы формулируют также некоторые нерешённые проблемы теории гарантированного поиска.
M3 - статья
SP - 3
EP - 39
JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
SN - 1025-3106
IS - 2
ER -
ID: 5684482