Задачи преследования и поиска на графах

• Автор: Фомин, Федор Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1996
• Место защиты: Санкт-Петербург
• Количество страниц: 122 с.

Оглавление
Список обозначений Введение
1 Дискретные программы
1.1 Постановка задачи поиска
1.2 Почти дискретные программы
1.3 Дискретные программы
1.4 Поиск на деревьях
1.5 Пример. Остов тетраэдра
2 Задача поиска с двумя преследователями
2.1 Обобщение одного результата Н.Н. Петрова
2.2 Связь задачи поиска с почти гамильтоновыми внешнепланарными цепями
2.3 Модельные задачи
3 Дискретная задача поиска с одним преследователем
3.1 Постановка задачи
3.2 Ширина ленты
3.3 Монотонная задача поиска

Литература

Список обозначений
R — множество вещественных чисел;
N — множество натуральных чисел;
R" — п-мерное Евклидово пространство;
х Є А — “элемент х принадлежит множеству А”;
л: А — “элемент х не принадлежит множеству А”;
А С В — “А есть подмножество множества В”;
АС В — “А С и А В” (строгое подмножество);
0 — пустое множество;
УТ множество вершин графа Г;
У(Г — множество вершин степени > 2 графа Г;
ЕГ — множество ребер графа Г;
cleg а — степень вершины а;
Д(Г) — максимальная степень вершины графа Г;
|А| — количество элементов (мощность) конечного множества А;
||а;|| — евклидова норма х;
— последовательность {a*, а*+і
[.tJ — наибольшее целое число, не превосходящее х;
1 — конец доказательства;
Введение
Неослабевающий интерес к разнообразным задачам преследования и поиска объясняется тем, что эти задачи возникают во многих областях человеческой деятельности. Ознакомиться с различными подходами к этим проблемам можно в работах [2, 3, 20, 21, 31, 33, 38, 40] и в литературе, указанной в этих работах. Достаточно подробный обзор литературы имеется в [20].
Среди многочисленных задач поиска и преследования важное место занимают задачи, связанные с поиском (преследованием) некоторого объекта, в дальнейшем именуемого убегающим, группой других объектов (возможно, состоящей из одного объекта), в дальнейшем именуемых преследователями, на различных множествах при различных правилах поведения игроков (преследователей и убегающего) и различных условиях успешного завершения поиска (преследования). Круг этих задач весьма широк. Сюда, например, относятся разнообразные дифференциальные игры (см. работы [2, 20, 21, 38, 40]), дискретные задачи поиска (преследования) и многие другие задачи.
Изучаемые в диссертации задачи поиска лежат на стыке нескольких разделов математики: теории конфликтного управления, теории графов и компьютерной математики (Computer Science). Поэтому не удивительно, что исследование этих задач привлекает многих ученых из различных областей науки.
Одна из классических задач конфликтного управления — проблема “Принцесса и Чудовище” рассматривалась Айзексом в монографии [2]. Чудовище хочет поймать Принцессу. Оба находятся в абсолютно темном помещении, формы которого им известны. Чудовище ловит принцессу, если ему удается приблизиться к ней на заданное расстояние. Платой в данной игре является время поимки. В качестве nepBofo шага в решении проблемы, Айзекс предложил рассмотреть случай, когда оба игрока движутся по окружно-
Введение

убегающий обеспечивает уклонение от обнаружения преследователем до [Р}-г° шага включительно. Множество СОЛгТ(П, Г, Р) — состоящее из всех загрязненных в момент Р точек графа Г - будем называть загрязненным в момент Р множеством, а множество СЬЕАН(П, Г, Р) = Г — СОЕтТ(И, Г, Р) — очищенным множеством. Естественно предполагать, что для всех і Є [0,1) граф загрязнен полностью, т.о. Г = СОЛгТ(П,Г,/). Тогда программа П(/'), і Є 1 ,Т. является выигрывающей, если для некоторого Р € 1,Т граф полностью очищен, т.е. СХ£,АЙ(П,Г,г*) = Г.
Существование выигрывающей программы преследователя в этой задаче зависит только от константы р. Для графа Г определим параметр /х(Г) как
іій{/г. при скорости убегающего ц у преследователя на Г не существует выигрывающей программы}.
В третьей главе рассматриваются два варианта описанной задачи. В первом случае (§3.2) преследователь может посетить каждую вершину графа не более одного раза. Наименьшее /х, для которого не существует выигрывающей программы на графе Г, обозначается в этом случае через /ч(Г). Доказывается следующее утверждение: Теорема 3.2.1 Для всякого графа Г Є £ справедливо равенство
*‘Г‘(Г) = ЦГ).
Здесь через Ь(Г) обозначена ширина ленты (см. определение на стр. 12) графа Г.
В середине семидесятых годов Пападимитриу в работе [130] показал, что нахождение ширины ленты графа является ЫР-трудной задачей. Более того, доказано [87], что задача остается КР-трудной и для деревьев с максимальной степенью вершин равной трем.
В §3.3 обсуждается следующий вариант задачи поиска. Предполагается, что преследователь может посещать вершины графа повторно, но не может допускать повторного загрязнения уже посещенных вершин. Другими словами, программа поиска преследователя П, і 6 1,Т, на графе Г является монотонной, если для всяких і* Є 0, Т и и Е Г условие и Є СОДТ(П, Г, г*) влечет и Є СОДТ(Т1, Г, г) для всех г < Р. Обозначим через /х,„(Г) наименьшее р, > 0, при котором на графе Г у преследователя существует монотонная выигрывающая программа.
Рассматривается связь этой задачи поиска с двумя естественны-