Об автоматной модели преследования

• Автор: Волков, Николай Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 117 с.

Содержание
1. Введение
1.1. История вопроса
1.2. Краткое содержание работы
1.2.1. Постановка задачи
1.2.2. Основные результаты
1.2.3. Структура диссертации
2. Основные определения и вспомогательные понятия
2.1. Формальная постановка задачи
2.1.1. Лабиринты, в которых происходит преследование . .
2.1.2. Взаимодействие автоматов
2.1.3. Рассматриваемые проблемы
2.2. Вспомогательные понятия
2.2.1. Вспомогательные определения
2.2.2. Композиции автоматов
2.2.3. Построение вспомогательных автоматов
3. Преследование независимой системой хищников жертв
3.1. Траектории автомата в исследуемых лабиринтах
3.2. Невозможность поимки жертв независимой системой хищников на плоскости
4. Преследование коллективом хищников жертв в бесконечных лабиринтах
4.1. Поимка автоматов-жертв с периодическим поведением
4.1.1. Леммы о перемещении автоматов
4.1.2. Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов
4.1.3. Доказательство возможности поимки жертв с периодическим поведением
4.2. Поимка автоматов-жертв с непериодическим поведением . .
4.2.1. Леммы о перемещении автоматов в квадранте
4.2.2. Вычисление коллективом автоматов еще ряда арифметических функций от параметров, заданных расстановкой автоматов
4.2.3. Вычисление параметров жертвы по ее коду
4.2.4. Доказательство возможности поимки непериодических жертв в квадранте

4.3. Доказательство основной теоремы
5. Преследование коллективом хищников жертв внутри квадрата
5.1. Поимка данной системы автоматов-жертв
5.2. Построение автоматов-жертв, убегающих
от данного коллектива хищников
5.3. Доказательство теоремы о преследовании внутри квадрата .
Список литературы

1. Введение
1.1. История вопроса
Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской в работе [5]. В этой работе рассматривается взаимодействие двух конечных автоматов IV и Z («хищника» и «жертвы») в шахматных лабиринтах, имеющих вид квадрата со стороной I. Две клетки такого лабиринта считаются соседними, если они имеют общую сторону. Каждый из автоматов W и Z способен обозревать клетки, соседние той, в которой он находится (все такие клетки, вместе с клеткой в которой находится сам этот автомат, образуют его зону обзора). В зависимости от состояния своей зоны обзора (т.е. от наличия и расположения в зоне обзора клеток границы квадрата и от наличия и расположения в зоне обзора автомата-противника), хищник и жертва могут перемещаться за один такт в одну из соседних клеток, либо стоять на месте. Хищник и жертва делают ходы поочередно. Считается, что хищник поймал жертву, если они оказались в соседних клетках.
При фиксированном произвольном размере I стороны квадрата, в котором происходит преследование, изучаются два вопроса.
1. Для каждого ли автомата Z существует автомат IV, ловяющий Z в данном лабиринте при произвольных начальных расположениях У/ и Zrl
2. Существует ли универсальный автомат-хищник Иф ловящий любую жертву в данном лабиринте при при произвольных начальных расположениях IV и г?
На эти вопросы в работе [5] получены следующие ответы. Установлено, что для любых 1,п & N существует V/ с числом состояний 0[п ■ I2), который ловит за время 0(п ■ 14) любой автомат-жертву Z с числом состояний не большим п, в квадрате со стороной, не большей I, при любом начальном расположении W я Z. Установлено, что не существует автомата ¥, ловящего любой Z в произвольном квадрате с фиксированной длиной стороны 1,1 >8.
1.2. Краткое содержание работы
1.2.1. Постановка задачи
В данной работе, так же, как и в работе [5], рассматривается автоматный аналог ситуации преследования хищниками своих жертв. В качестве пространства преследования рассматриваются несколько типов лабиринтов,

(Ко о К)(1,2,3) -А Кг = (Ль Л, Л3 ).
К, стартуя из канонического расположения, переходит в слабую треугольную 1-расстановку. И, если К стартует из слабой треугольной а-расстановки (а € М), то Л обходит соответствующий этой расстановке треугольник, и К переходит в следующую за ней слабую треугольную (а + 2)-расстановку.
Такой коллектив, как легко видеть, обходит полуплоскость Ь, т.е. удовлетворяет условиям леммы. Лемма доказана.
Лемма 4Л. Существуют коллективы К2 = (Л!ъ А!2, А )(У, V) и = — (Л", Л2 )(У, V), такие что Уг = 2,3, Кг, при любом I £ К, стартуя из произвольного канонического расположения на РД), обходит £;(/), причем А (или Л[) проходит через каждую клетку счетное число раз.
1) Доказательство. Построим коллективы К2 и АГ3, удовлетворяющие условию леммы. Перечень автоматов коллектива К2 и их алфавитов.
О (А> {ч1 91, - - ■, 94», (А> (9о, 9»), (А> {9о> 9?})-
Из канонического расположения коллектив идет к нижнему борту.
2) А. Ы, НйДЛ) = 0)), - ы, (о. -1)).
3) Л2, (д2, (Рь0н(А) ~ 0))> —* (^о> (0, — !))•
4) (Ч0> (Рьон(А) ~ 0)), —> (дог (0, —1)).
Дойдя до нижнего борта, Л3 делает шаг вправо, и все автоматы меняют свои состояния.
5) А, ОЙ, (Р1н(А) = 1)), - ОЙ, (0,0)).
6) А, ОЙ, (Рьогь(А) = 1)), - (9?, (0,0)).
7) Л3, (д§, (Рь0н(А) — 1)), —* (9?, (1,0)).
Автомат Л'х обходит слева направо участок ^-полосы, ограниченный вертикальными прямыми, проходящими через расположения Л!2 и Л3.
8) А, ОЙ, (П2он(Л) = 0)), - (?1> (0,1)).
9) Л'ь Ой, (ПЛА) = 1) л (Аид) = 0)), (д2 (0, -1)).
10) А, Ой, (Р1н(А) = 0)), - (ч1 (0, -1)).
11) Л'ь (я1 (Р1Н(А) = 1)Л(Р^(Л1) = 1)А(Ро(Л'1, Л'з) = 0)), - (д}, (1, 0)).
12) л;, (я1 (РиА) = 1) А ША,Аз) = 0)), - (д, (1,0)).
Когда Л( оказывается в одной клетке с Л3, они вместе делают шаг вправо.
13) л;, (<й, (Р620ГМ) = 1)А(Р^(Д1) = 1)Л(Р0(Д, Л') = 1)), — (д3 (1,0)).
14) Л'ь (д2 (РиА) = 1) л (Ро(А, А) = 1)), - Ой. (1, 0)).
15) Л'з, (д?, (РЩА) = 1) л (Р((А, А,ч) = 1)), - Ой, (1,0)).
16) А^ (д?, (Ро(Л3) Л'ь д2) = 1)), —>• (??, (1,0)).
После этого Л^ снова обходит (в этот раз справа налево) участок