TY  - JOUR
T1  - ОБЩАЯ ТЕОРИЯ ГАРАНТИРОВАННОГО ПОИСКА
AU  - Гришмановский, Д. А.
Y1  - 2023-03-27
UR  - https://rep.herzen.spb.ru/publication/378
N2  - Одна из главных задач теории гарантированного поиска (ТГП) формулируется следующим образом. На графе   располагаются преследователи, которые должны гарантированно поймать так называемого убегающего, информация о скорости и месторасположении которого отсутствует. Все передвигаются по рёбрам графа непрерывно. От нас же требуется найти минимальное число таких преследователей на этом графе. Числовая характеристика, описывающая минимальное количество преследователей, необходимых для поимки убегающего, называется поисковым числом графа  . Например, поисковое число отрезка равно 1: достаточно поставить одного преследователя в один из концов отрезка, откуда он пойдёт к другому концу, где гарантированно поймает убегающего. А на окружности одного преследователя недостаточно,посколькуубегающий будетдержатьсявдиаметральнопротивополож-ной относительно этого преследователя точке, поэтому поисковое число окружности больше единицы. В графе, имеющем форму буквы «Y» одного преследователя также недостаточно, ведь дойдя до «развилки» он не сможет наверняка угадать в какой из двух оставшихся частей находится убегающий. Но двух преследователей будет уже достаточно. Вопрос нахождения поискового числа отличается простотой своей формулировки и вполне мог быть поставлен в XVIII веке, во времена Эйлера, но впервые задача нахождения поискового числа графа была поставлена и изучена в работах Т. Д. Парсонса [4] и Н. Н. Петрова [3] всего около 40 лет назад. На сегодняшний день ТГП уже имеет множество приложений в различных сферах научной деятельности: сверхбольшие интегральные схемы, рациональное использование памяти компьютера, системы управления ракетами, сохранение секретности информации, создание антивирусных программ, обработка естественного языка, координация движения роботов, нахождение карт ДНК и др [1]. К сожалению, содержательных исследований по ТГП на момент написания данной работы очень мало. В настоящей работе даётся определение поиска на топологическом пространстве, а также определение исследованной им области. Доказыается ряд вспомогательных утверждений и теорема о взаимосвязи границы исследованной области с границей конфигурации преследователей. Данная работа составляет материал общей теории гарантированного поиска (ОТГП). Подойдём к определению фундаментального понятия теории поиска. Рассмотрим регулярное топологическое пространство   = ( ,Ω). В рамках нашей теории оно называетсяареной поиска,ночащемыбудемпользоватьсяболее удобным терми- 253 ном: пространство. Символ R+ обозначает множество всех неотрицательных чисел {t eR: t > 0}. Определение 1. (i) Совокупность S = S(X) непрерывных отображений fi: R+ -> X называется поиском на пространстве X. (ii) Подмножество Р с S называется подпоиском поиска S. (ш) В случае выше отображение ft называется траекторией i-го преследователя. (iv) Любое другое непрерывное отображение g: R+ -> X по отношению к преследователям будет считаться траекторией убегающего. (v) Если card S = п, то мы будем говорить, что поиск S использует п преследователей. Поиск, использующий конечное количество преследователей, называется конечным. Аналогично определяется бесконечный поиск. Изучением поисков на графах занимается конечная теория гарантированного поиска (КТГП). Стоит отметить, что пространство X можно полагать линейно связным, поскольку любой поиск S(X) будет сводиться к изучению его подпоисков S(Xi) на каждой компоненте линейной связности Xi пространства X. Введём вспомогательное обозначение F{t) = Ц ft (t), которым мы не раз будем пользоваться. Оно обозначает конфигурацию всех преследователей в данный момент времени t. Определение 2. (i) Исследованной поиском S в момент времени t областью пространства X называется его подмножество S(t,X) = {хе X\Vg e C([0,t],X),g(t) =х => 30 < t0 < f. g(t0) e F(t0)}. (ii) Окончательно исследованной частью пространства называется подмножество S[t, X], состоящее из точекх е S(t), для которых из условия f > t следует, что х е S(f). Стоит заметить, что для подпоиска Р с S справедливо включение P(t) с S(t). Приведём простейший пример поиска, при котором исследованная и окончательно исследованная области отличаются друг от друга. Пример 1. . Пусть ареной поиска является отрезок / = [0, 3] и S(I) = {/}, где ft, 0 < t < 2, f(t) = U-t, 2<t<3, t-2, 3 < t < 5. В таком случае S(t, I) = [0, f(t)], если 0 < t < 5, и '[0,/(f)L te [0,1] U [3,5], S[t,I] = < [0,1], /g[1,3]. 254 Утверждение 1. . Для любого поиска S множества F(Ö) и S(Ö) равны. Доказательство. Точка х принадлежит F(0) тогда, и только тогда, когда для любой траектории убегающего g, где g(0) = х е X можно подобрать число 0 < to < О, для которого g(to) e F(to), а именно, to = О тогда, и только тогда, когда точка х принадлежит S(0). n Лемма 1. Для любого поиска S всегда верно включение F{t) с S{t). Доказательство. Пусть х е F(t), тогда для любой траектории убегающего g, где g(t) = х, в качестве 0 < to < t, для которого g(to) е F(to), можно подобрать, например, число t. Таким образом, по определению исследованной области, х е S(t), что и требовалось. D Лемма 2. Точка х принадлежит S(t) тогда и только тогда, когда для любой траектории убегающего g, где g{t) = х, существует число О < to < t, для которого g{to) е S(t0). Доказательство. Поскольку у е S(to), где у = g(to), то для любой траектории убегающего gi, где gt(to) = у, существует такое число t\ е [О, to], что gi{t\) e F{t\). В частности, это верно для сужения отображения g на интервале [0, to], а для продолжения до интервала [0, t] тем более. Таким образом х е S(t) по определению. Если х е S(t), то для любой траектории убегающего g, где g(t) = х, в качестве числа to, для которого g(to) e S(to), можно взять само число t. Вторая часть леммы доказана. D Теорема 1. Для любого поиска S всегда верно включение dS(t) с dF{t). Доказательство. Известно, что следующие три утверждения эквивалентны: множество X замкнуто, С1Х = X, дХ с X. Допустим противное, что в некоторый момент t некоторая точках принадлежит dS(t) \ dF{t). Пользуясь аксиомой Гз и замкнутостью dF(t), подберём непересекающиеся открытые окрестности V,W e Q. точки х и границы dF{t) соответственно, где V можно полагать линейно связной. Поскольку х является граничной точкой, то можно рассмотреть точки а е V П S(t) и Ъ е V C\S(t). В силу непрерывности каждого из отображений fi e S, для окрестности W найдётся положительное число 6 > 0, для которого F([t - 6, t]) с W. Рассмотрим часть траектории убегающего g: [t - 6, t] -> V, где g(t - 6) = b и g(t) = а. Поскольку окрестности УиЖне пересекаются, то g и F также не пересекаются во временном промежутке [t - 6, t]. Благодаря тому, что Ъ £ S{t), можно положить, что g не пересекается с F и на временном промежутке [0, t - 6]. Итого, g(t) = а и g(to) <£ F(to) для всех 0 < to < t, а значит а £ S{t), что противоречит выбору точки а. Теорема доказана. D 255 Следствие 1. Если F(t) замкнуто, то dS(t) с F(t). Доказательство. Из теоремы 1 и критерия замкнутого множества вытекает следующая цепочка включений: dS{t) с dF{t) с F{t). и Следствие 2. Для конечного поиска всегда верно, что dS{t) с F{t). Доказательство. Действительно, так как в таком случае конечное множество F(t) с X всегда будет замкнутым. По следствию 1 получаем требуемое. D Определение 3. Поиск S называется замкнутым в момент времени t, если S(t) замкнуто. Поиск S называется замкнутым, если он является замкнутым в любой момент t. Из следствия 1 (и леммы 1) вытекает замкнутость поиска, у которого F{t) замкнуто, а из следствия 2 вытекает замкнутость конечного поиска. Пример 2. Опровергнем контрпримером утверждение о том, что для поиска S общего вида всегда верно включение dS{t) с F{t). Рассмотрим поиск S(R2) на координатной плоскости, где F{t) = С = U^=i ^i/и Для любого t. Здесь Sr является окружностью радиуса г с центром в начале координат (0,0). К этому поиску добавим ещё одного преследователя, траектория которого задаётся формулой f(t) = (0, t). Тогда для полученного в итоге поиска, также обозначающегося через S, имеем F(t) = С U (0, t) и S(t) = С U (0,0) U (0, t). Конфигурация F{t) является замкнутой только в начальный момент времени, a S{t) замкнуто всегда, более того, dS{t) = S(t) для всех t. При t > 0 начало координат будет лежать в разности dS{t) \ F{t). В связи с этим включение dS{t) с F{t) не выполняется при всех t > 0. Теорема 2. Для замкнутого поиска S область S[t] замкнута в любой момент t. Доказательство. Прежде чем приступить к основному утверждению теоремы, мы докажем, что при выполнении тех же условий, из того, что х е dS[t], следует, что х е S(t) для любого t. Из условия х е dS[t] будет следовать, что х е C\S[t]. A из условий C\S(t) = S(t) и S[t] с S(t) следует, что Cl»S[/] с S(t). Таким образом, х е S(t). Вернёмся к доказательству нашего основного утверждения. Предположим противное, что х е dS[t] \ S[t] для некоторого t. Поскольку х £ S[t], то существует число f > t, для которого х <£ S(t'). Из f > t также следует, что S[f] D S[t]. Любая окрестность U(x) е Q нетривиально пересекается как с S(t'), поскольку х <£ S(t') и х е U(x), так и с S[f], поскольку из U(x) n S[t] Ф 0 следует U(x) n S[f] Ф 0, таким образом х е dS[f] \ S(t'). Получаем противоречие с только что доказанным утверждением. Теорема доказана. D 256 Пользуясь случаем, я бы хотел выразить огромную благодарность своему учителю геометрии и научному руководителю Валерию Валентиновичу Крылову.