Русская Википедия:Теория гарантированного поиска
Теория гарантированного поиска (или теория поиска; сокращённо — ТГП) — раздел математики, изучающий свойства поиска на графах и топологических пространствах.
Нестрого говоря, одна из основных задач ТГП формулируется следующим образом. На арене поиска <math>X</math> располагаются преследователи, которые должны гарантированно поймать так называемого убегающего, информация о скорости и месторасположении которого отсутствует. Все передвигаются по арене поиска непрерывно. От нас требуется найти минимальное число преследователей, которые гарантированно смогут поймать убегающего. Числовая характеристика, описывающая минимальное количество преследователей, необходимых для поимки убегающего, называется поисковым числом арены <math>X</math>.Шаблон:Sfn
Например, поисковое число отрезка равно <math>1</math>: достаточно поставить преследователя в один из концов отрезка, откуда он пойдёт к другому концу, где гарантированно поймает убегающего. А на окружности одного преследователя уже недостаточно, поскольку убегающий будет держаться в диаметрально противоположной относительно этого преследователя точке. В графе, имеющем форму буквы «Т» одного преследователя также недостаточно, ведь дойдя до «развилки» он не сможет наверняка угадать в какой из двух оставшихся частей находится убегающий. Но двух преследователей будет уже достаточно, следовательно, поисковое число этого графа равно <math>2</math>.
В случае произвольного графа задача нахождения поискового числа остаётся открытой.Шаблон:Sfn
История
Любопытно, что впервые вопрос о наименьшем числе преследователей был поставлен спелеологом Брейшом. Представим, что в некоторой пещере, состоящей из ходов и лазов, потерялся незадачливый исследователь, которого мы должны спасти. В нашем распоряжении имеется карта пещеры (граф), но число спасателей ограничено. То, что заблудившийся спелеолог желает встречи со спасателями, никак не облегчает нашу задачу, если речь идет о гарантированном спасении. Он может бесцельно метаться по всей пещере с неизвестной скоростью. Требуется разработать план поиска, гарантирующий спасение спелеолога, то есть исключающий любую возможность с ним разминуться.Шаблон:Sfn
Впервые задача нахождения поискового числа была поставлена независимо математиками Торренсом ПарсонсомШаблон:Sfn и Николаем ПетровымШаблон:Sfn в 1980-х годах. В их работах содержалось решение задачи поиска для деревьев. Через некоторое время было доказаноШаблон:Sfn, что задача нахождения поискового числа является NP-полной. В той же работе были охарактеризованы все графы с поисковым числом, меньшим 4. В 1989 году П. А. Головач доказалШаблон:Sfn эквивалентность топологической и комбинаторной формулировок задачи преследования. Позже (в немного другой формулировке) было доказаноШаблон:Sfn, что среди всех оптимальных поисков на графе можно выделить монотонный поиск. В перечисленных выше работах речь шла о поиске на графах. В 2022 году Д. А. Гришмановским была поставлена и изучена задача поиска на топологическом пространстве.
Разделы теории гарантированного поиска
Конечная теория гарантированного поиска
Шаблон:Main Конечная теория гарантированного поиска (КТГП), или теория гарантированного поиска на графах — раздел теории гарантированного поиска, в котором любой поиск использует конечное число преследователей, посвящён нахождению поисковых чисел графов и изучению свойств поиска на комбинаторных графах.
Аналитическая теория гарантированного поиска
Шаблон:Main Аналитическая теория гарантированного поиска (АТГП) — занимается изучением поисков, использующих бесконечное множество преследователей. В АТГП важно, чтобы множества, так или иначе связанные с исследованной областью, всегда были измеримы.
Приложения
Одним из первых приложений ТГП стали системы управления ракетами. Задачи для данных систем сформулировал Руфус Айзекс из корпорации RANDШаблон:Sfn. Некоторые учёные полагают, что ТГП может быть использована для создания антивирусных программ. Вот мнение известного специалиста БиенстокаШаблон:Sfn: Шаблон:Начало цитаты Рассмотрим поведение в сети компьютерного вируса. Предполагая худшее, мы должны подозревать, что заражена вся сеть, поэтому узлы должны быть очищены. Предположим, что у нас имеется несколько копий вакцинных программ, и изготовление большего числа копий непрактично. С другой стороны, плохо разработанная стратегия может стать причиной повторного заражения узла. Таким образом, ставится задача разработки стратегии очистки, использующей наименьшее число копий вакцинных программ. Шаблон:Конец цитаты Также ТГП имеет приложенияШаблон:Sfn в таких сферах научной деятельности, как
- сверхбольшие интегральные схемы
- рациональное использование памяти компьютера
- сохранение секретности информации
- обработка естественного языка
- координация движения роботов
- теория миноров Робертсона-Сеймура
- нахождение карт ДНК
и многих других.
См. также
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
