Теория гарантированного поиска (сокращённо — ТГП) — раздел математики, посвящённый изучению свойств поиска, не зависящих от скорости движения преследователей и наличия информации об убегающем.
Одна из главных задач теории гарантированного поиска (ТГП) формулируется следующим образом. На некотором пространстве располагаются преследователи, которые должны гарантированно поймать так называемого убегающего, информация о скорости и месторасположении которого отсутствует. Все участники поиска передвигаются по пространству непрерывно. Мы должны найти минимальное число преследователей, которые гарантированно смогут поймать убегающего на данном пространстве. Данную числовую характеристику принято называть поисковым числом рассматриваемого пространства.
Например, для отрезка такое число равно 1 {\displaystyle 1} : достаточно поставить одного преследователя в один из концов отрезка, откуда он пойдёт к другому концу, где гарантированно поймает убегающего. А на окружности одного преследователя уже не будет достаточно, поскольку неограниченно быстрый убегающий всегда будет держаться в диаметрально противоположной относительно этого преследователя точке. В пространстве, имеющем форму символа Y одного преследователя также недостаточно, ведь дойдя до «развилки» он, за неимением соответствующей информации, не сможет наверняка угадать в какой из двух оставшихся частей находится убегающий.
Любопытно, что впервые вопрос о наименьшем числе преследователей был поставлен спелеологом Брейшом. Представим, что в некоторой пещере, состоящей из ходов и лазов, потерялся незадачливый исследователь, которого мы должны спасти. В нашем распоряжении имеется карта пещеры (граф), но число спасателей ограничено. То, что заблудившийся спелеолог желает встречи со спасателями, никак не облегчает нашу задачу, если речь идет о гарантированном спасении. Он может бесцельно метаться по всей пещере с неизвестной скоростью. Требуется разработать план поиска, гарантирующий спасение спелеолога, то есть исключающий любую возможность с ним разминуться.[1]
Впервые задача нахождения поискового числа была поставлена Т. Д. Парсонсом[2] в 1978 году для случая графа. В работе Н. Н. Петрова[3] приводилось решение задачи нахождения поискового числа для деревьев. Через некоторое время было доказано[4], что задача нахождения поискового числа является NP-полной. В той же работе были охарактеризованы все графы с поисковым числом, меньшим 4. Позже П. А. Головач доказал[5] эквивалентность топологической и комбинаторной формулировок задачи преследования. В 2022 году Д. А. Гришмановским была поставлена[6] и изучена задача поиска на топологическом пространстве, которая образовала отдельное направление в ТГП.
Общая теория гарантированного поиска (ОТГП) — раздел теории гарантированного поиска, в котором поиск разворачивается на топологическом пространстве. Он посвящён исследованию фундаментальных свойств поиска, таких как, например, гарантированность и непрерывность.
Конечная теория гарантированного поиска (КТГП) — раздел ТГП, в котором рассматривается использующий конечное число преследователей дискретный поиск на комбинаторных графах и исследуется вопрос нахождения их поисковых чисел и времени оптимального поиска.
Одним из первых приложений ТГП стали системы управления ракетами. Задачи для данных систем сформулировал Руфус Айзекс из корпорации RAND[7]. Некоторые учёные полагают, что ТГП может быть использована для создания антивирусных программ. Вот мнение известного специалиста Биенстока[8]:
Рассмотрим поведение в сети компьютерного вируса. Предполагая худшее, мы должны подозревать, что заражена вся сеть, поэтому узлы должны быть очищены. Предположим, что у нас имеется несколько копий вакцинных программ, и изготовление большего числа копий непрактично. С другой стороны, плохо разработанная стратегия может стать причиной повторного заражения узла. Таким образом, ставится задача разработки стратегии очистки, использующей наименьшее число копий вакцинных программ.
Также ТГП имеет приложения[9] в таких сферах научной деятельности, как
и многих других.