АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

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

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

undefined

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

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

В случае произвольного графа задача нахождения поискового числа остаётся открытой.[1]

История

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

Впервые задача нахождения поискового числа была поставлена независимо математиками Торренсом Парсонсом[3] и Николаем Петровым[4] в 1980-х годах. В их работах содержалось решение задачи поиска для деревьев. Через некоторое время было доказано[5], что задача нахождения поискового числа является NP-полной. В той же работе были охарактеризованы все графы с поисковым числом, меньшим 4. В 1989 году П. А. Головач доказал[6] эквивалентность топологической и комбинаторной формулировок задачи преследования. Позже (в немного другой формулировке) было доказано[7], что среди всех оптимальных поисков на графе можно выделить монотонный поиск. В перечисленных выше работах речь шла о поиске на графах. В 2022 году Д. А. Гришмановским была поставлена и изучена задача поиска на топологическом пространстве.

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

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

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

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

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

Приложения

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

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

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

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

См. также

Примечания

Литература

  • Абрамовская Т. В., Петров Н. Н. Теория гарантированного поиска на графах. — Вестник Санкт-Петербургского университета, 2013. — С. 3—35.
  • Головач П. А. Об одном топологическом инварианте в задачах преследования. — Дифференциальные уравнения, 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.

Категории