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

Теория гарантированного поиска (сокращённо — ТГП) — раздел математики, посвящённый изучению свойств поиска, не зависящих от скорости движения преследователей и наличия информации об убегающем.

Пример гарантированного поиска на графе. Синим цветом отмечены преследователи, а зелёным выделена исследованная ими область.

Одна из главных задач теории гарантированного поиска (ТГП) формулируется следующим образом. На некотором пространстве располагаются преследователи, которые должны гарантированно поймать так называемого убегающего, информация о скорости и месторасположении которого отсутствует. Все участники поиска передвигаются по пространству непрерывно. Мы должны найти минимальное число преследователей, которые гарантированно смогут поймать убегающего на данном пространстве. Данную числовую характеристику принято называть поисковым числом рассматриваемого пространства.

Например, для отрезка такое число равно $1$: достаточно поставить одного преследователя в один из концов отрезка, откуда он пойдёт к другому концу, где гарантированно поймает убегающего. А на окружности одного преследователя уже не будет достаточно, поскольку неограниченно быстрый убегающий всегда будет держаться в диаметрально противоположной относительно этого преследователя точке. В пространстве, имеющем форму символа Y одного преследователя также недостаточно, ведь дойдя до «развилки» он, за неимением соответствующей информации, не сможет наверняка угадать в какой из двух оставшихся частей находится убегающий.

История

Любопытно, что впервые вопрос о наименьшем числе преследователей был поставлен спелеологом Брейшом. Представим, что в некоторой пещере, состоящей из ходов и лазов, потерялся незадачливый исследователь, которого мы должны спасти. В нашем распоряжении имеется карта пещеры (граф), но число спасателей ограничено. То, что заблудившийся спелеолог желает встречи со спасателями, никак не облегчает нашу задачу, если речь идет о гарантированном спасении. Он может бесцельно метаться по всей пещере с неизвестной скоростью. Требуется разработать план поиска, гарантирующий спасение спелеолога, то есть исключающий любую возможность с ним разминуться.

Впервые задача нахождения поискового числа была поставлена Т. Д. Парсонсом в 1978 году для случая графа. В работе Н. Н. Петрова приводилось решение задачи нахождения поискового числа для деревьев. Через некоторое время было доказано, что задача нахождения поискового числа является NP-полной. В той же работе были охарактеризованы все графы с поисковым числом, меньшим 4. Позже П. А. Головач доказал эквивалентность топологической и комбинаторной формулировок задачи преследования. В 2022 году Д. А. Гришмановским была поставлена и изучена задача поиска на топологическом пространстве, которая образовала отдельное направление в ТГП.

Разделы теории гарантированного поиска

Общая теория гарантированного поиска

Основная статья: Общая теория гарантированного поиска

Общая теория гарантированного поиска (ОТГП) — раздел теории гарантированного поиска, в котором поиск разворачивается на топологическом пространстве. Он посвящён исследованию фундаментальных свойств поиска, таких как, например, гарантированность и непрерывность.

Конечная теория гарантированного поиска

Основная статья: Конечная теория гарантированного поиска

Конечная теория гарантированного поиска (КТГП) — раздел ТГП, в котором рассматривается использующий конечное число преследователей дискретный поиск на комбинаторных графах и исследуется вопрос нахождения их поисковых чисел и времени оптимального поиска.

Приложения

Одним из первых приложений ТГП стали системы управления ракетами. Задачи для данных систем сформулировал Руфус Айзекс из корпорации RAND. Некоторые учёные полагают, что ТГП может быть использована для создания антивирусных программ. Вот мнение известного специалиста Биенстока:

Рассмотрим поведение в сети компьютерного вируса. Предполагая худшее, мы должны подозревать, что заражена вся сеть, поэтому узлы должны быть очищены. Предположим, что у нас имеется несколько копий вакцинных программ, и изготовление большего числа копий непрактично. С другой стороны, плохо разработанная стратегия может стать причиной повторного заражения узла. Таким образом, ставится задача разработки стратегии очистки, использующей наименьшее число копий вакцинных программ.

Также ТГП имеет приложения в таких сферах научной деятельности, как

• дизайн сверхбольших интегральных схем
• рациональное использование памяти компьютера
• сохранение секретности информации
• обработка естественного языка
• координация движения роботов
• теория баз данных
• распределённые вычисления
• маршрутизация в телекоммуникационных сетях
• нахождение карт ДНК

и многих других.

См. также

• Задача об Ангеле и Дьяволе
• Задача о водителе-убийце
• Принцесса и Чудовище (игра)
• Игра на поиск

Литература

• Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах. — Вестник Санкт-Петербургского университета, 2013. — С. 3—35.
• Гришмановский Д. А. Общая теория гарантированного поиска. — Современные проблемы математики и математического образования, РГПУ им. Герцена, 2022. — С. 252—257.
• Головач П. А. Об одном топологическом инварианте в задачах преследования. — Дифференциальные уравнения, 1989. — С. 923–929.
• Петров Н. Н. Задачи преследования при отсутствии информации об убегающем. — Дифференциальные уравнения, 1982. — С. 1345–1352.
• Bienstock D. Graph searching, path-width, tree-width and related problems (a survey). — New Brunswick: Reliability of computer and communication networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc., Providence, RI. Vol. 5, 1991. — С. 33—49.
• Breisch R. An intuitive approach to speleotopology. — Southwestern Cavers, 1967. — С. 72—78.
• Isaacs R. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. — New York: John Wiley & Sons, 1965.
• Lapaugh A. Recontamination does not help to search a graph. — Princeton University: Tech. Report 335, Dept. of Elec. Eng. and Comput. Sci., 1993.
• Megiddo N., Hakimi S. L., Garey M. R. The complexity of searching a graph. — J. Assoc. Comput. Mach, 1988. — С. 18—44.
• Torrence D. Parsons. Pursuit-evasion in a graph // Theory and Applications of Graphs. — Springer-Verlag, 1976. — С. 426–441.