Дипломная работа на тему «Преследование жертв автоматов-жертв автоматом-хищником с красками» (стр. 2 )

Момент времени 2τ (τ єN0) называется моментом хода жертв с номером τ. Момент (2τ+1) называется моментом хода хищников с номером τ. Промежуток времени [2τ, (2τ+1)] называется тактом с номером τ. Время взаимодействия автоматов будем измерять в тактах.

Преследование хищником независимой системы жертв происходит следующим образом. Фиксируются начальные (в нулевой момент времени) расположения хищника и жертв на плоскости. В нулевой момент каждая жертва Ui воспринимает в качестве входного символа пару (0,F2),где Ui - конфигурация F2 задает клетки зоны обзора Ui, в которой находится хищник. В момент 2τ (τєN) каждая жертва Ui воспринимает в качестве входного символа пару (F1,F2), задающую клетки зоны обзора Ui, в которых находятся хищник в моменты (2τ-1) и 2τ. В каждый момент 2τ (τєN0) жертва Ui, в соответствии со своими функциями переходов и выходов, определяет свое следующее состояние, выходной символ b, и перемещается на вектор b.

В момент (2τ+1) (τєN0) хищник Wс воспринимает в качестве входного символа пару (F1,F2), задающую клетки зоны обзора Wс, в которых находятся жертвы в моменты 2τ и (2τ+1), и, в соответствии со своими функциями переходов и выходов, определяет свое следующее состояние, выходной символ b, и перемещается на вектор b.

Хищник Wс “ловит” жертву, если жертва в некоторый момент времени оказалась в окрестности хода хищника. Пойманная жертва исчезает с плоскости. Wс “ловит” независимую систему жертв, если в процессе преследования Wс ловит каждую жертву.

Пусть автомат Ά с перемещается по плоскости и его выходные символы в такты t, t+1,…, T равны bt, bt+1,…, bT, соответственно. Вектором перемещения Ά с за промежуток времени [t,T] называется вектор s= bt + bt+1 + … + bT.

В работе [2] показано, что автомат, двигающийся так, что в его зону обзора не попадают другие автоматы, имеет периодическую последовательность выходных символов и периодическую последовательность переходов.

Движение автомата Wс(R, V)с краской не периодично.

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

Далее будем считать, что обзор жертвы всегда не больше обзора хищника, а скорость жертвы всегда меньше скорости хищника. Иначе при разумном поведении жертвы, она никогда не будет поймана.

Под целочисленным вектором (отрезком) будем понимать вектор (отрезок) начало и конец которого имеют целочисленный координаты. Направлением s будем называть любой целочисленный вектор s.

Будем говорить, что клетка u принадлежит целочисленному отрезку (лучу) a, если этот отрезок (луч) пересекает внутреннюю часть клетки. Клетками отрезков (лучей) с направляющими векторами (0,1), (1,0), (0,-1), (-1,0), будем считать клетки лежащие справа для вектора (0,1), слева для (0,-1), сверху для (1,0), снизу для (-1,0) от отрезка (луча, прямой), пересекаемые более чем в одной точке.

Нулевым направлением будем называть вектор (0,0).

Рассмотрим некоторое ненулевое направление s. Пусть es –минимальный целочисленный вектор сонаправленный с вектором s. Тогда вектор es будем называть минимальным шагом в направлении s.

Будем говорить, что жертва (хищник) U принадлежит классу А1, если

1. Её (его) вектор перемещения нулевой.

2. Существует натуральное число k, такое что, если хищник(жертва) не появлялся в зоне обзора U за последние k тактов, то жертва (хищник) осуществляет периодическое движение без предпериода с нулевым вектором перемещения.

Теорема 1:

Для каждого лабиринта ,, , , , существует 1 автомат с одной краской Wc (1,1), который его обходит.

Теорема 2: Для любого Nmax N, существует хищник-автомат с краской Wс (R, V), который ловит любую независимую систему жертв U=(U1, …, Um)(R-1,V-1), такую, что каждая жертва принадлежит классу А1, и max{n1, n2,…, nm} ≤ Nmax, где ni – количество состояний Ui.

Далее будут рассматриваться автоматы преследование автоматов с красками.

Изначально предполагаем, что все клетки плоскости белого цвета, либо цвета 0.

Следом назовем множество клеток, окрашенных в фиксированную краску.

Краска жертвы отлична от краски хищника. Автомат хищник распознает след оставленный жертвой.

Будем говорить, что жертва U принадлежит классу A2, если

1) При наличии в зоне обзора своей краски ведут себя так же, как и при ее отсутствии («не видят» ее).

2) Жертва движется по плоскости без предпериода.

3) Число состояний жертвы не больше чем N.

4) В каждый фиксированный такт оставляет след.

Теорема 3: Для любой жертвы U (R-1,V-1), принадлежащей классу A2, существует автомат хищник с краской W (R, V), который ловит эту жертву.

Соседними, к клетке (, ) будем называть клетки, которые расположены от нее на расстоянии 1, т. е. | – xj | + | – yj | = 1, где xj, yj є Z.

Будем говорить, что жертва U(1,1) принадлежит классу A3 если у каждой клетки следа (, ) есть не более 2-х соседних клеток следа, т. е. след жертвы будет представлять собой непересекающеюся кривую на плоскости.

Теорема 4:

Для любой жертвы из A3 существует автомат хищник с краской W (2,2), который ловит жертву.

Глава 2

Поведение автоматов с красками на одномерной ленте

Обозначим множества натуральных и целых чисел, как и , соответственно. Положим . Множество клеток, на которые плоскость разбивается целочисленной решеткой, обозначим . Определим подмножество – бесконечную в обе сторону ленту, разбитую на клетки: (рис. 1).

(рис. 1).

Каждой клетке бесконечной в обе стороны ленты сопоставлена координата её. Отрезок из клеток, находящихся от клетки на расстоянии, не превосходящем r, назовем r-окрестностью клетки

Будем считать, что задана нумерация клеток множества - слева направо, т. е. первая клетка отрезка – самая левая, последняя – самая правая.

Последовательность клеток "х1,...,хt,...., называется физически реализуемой автоматом со скоростью V, если каждая клетка в этой последовательности удалена от предыдущей клетки не более, чем на расстояние |х(t+1)-x(t)|<=V.

Весь период непериодического движения автомата будем называть, сознательным движением автомата.

Определим движение автомата как последовательность его выходных символов b(1),…b(i)…, где b(i) – целые числа. Выходные символы b(i) - принимающие неотрицательное значение будем для удобства обозначать символом А(i), а b(i) принимающие отрицательные значения - будем обозначать В(i)

Лемма 3.

Существует физически реализуемая траектория на полосе, которую не может реализовать автомат с красками.

Доказательство вспомогательных утверждений.

Лемма 1.

Существует автомат с краской, который обходит плоскость.

Построим автомат в явном виде:

Входные данные берутся с обзора R=1

A	Q	Ψ	Φ
NSWE		(↑,1)
NWE		(→,2)
NSE		(↓,3)
SE		(↓,4)
SWE		(←,4)
SW		(←,1)
NSW		(↑,1)
NW		(↑,1)
NW		(↑,2)
NWE		(→,2)
NE		(→,2)
NE		(→,3)
NSE		(↓,3)
SE		(↓,3)
SE		(↓,4)
SE		(↓,4)
SW		(←,4)
W		(←,1)
NW		(↑,2)
NE		(→,3)

Лемма 2: Существует такой автомат хищник с красками Wс(R, V) такой, что если Wс во время своего функционирования обнаруживает некоторую жертву U’ при некоторых начальных расположениях хищника и жертв, то Wс ловит жертву U’ при тех же начальных расположениях.