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

Будем говорить, что автомат обходит плоскость, если для любой клетки u плоскости существует такт t, такой что клетка u попадает в зону обзора автомата.

Рассмотрим две системы автоматов Wc(R, V) (хищник) и U=(U1,…,Un)(R’,V’) (жертвы), где R и R’ - обзоры, а V и V’ – скорости хищника и жертв, соответственно. Здесь U – независимая система автоматов.

Положим N’ =(R’ +1)2 +(R’)2 – размер зоны обзора жертвы. Для каждого i =1,…,n строку (a1,…,aN’), такую, что для любого k =1,…,N’

1, если в k-й клетке зоны обзора Ui находится хищник;

ak =

0, иначе;

назовем Ui - конфигурацией. Каждая Ui –конфигурация однозначно задает клетки зоны обзора Ui, в которых находится хищник.

Положим N =(R +1)2 +(R)2 – размер зоны обзора хищника. Cтроку (a1,…,aN), такую, что для любого k =1,…,N

1, если в k-й клетке зоны обзора W находится жертва;

ak =

0,  белый цвет;

               

2..m+1,  окрашена в один из цветов 1..m

назовем W-конфигурацией. W–конфигурация однозначно задает клетки зоны обзора W, в которых находится жертва.

Расположения на плоскости жертв и хищника и состояния хищников однозначно задают все Ui – конфигурации и Wс - конфигурация. Множество всех Ui – конфигураций при всевозможных расположениях жертв и хищника и состояний хищника обозначим как F’. Аналогично, Wс – конфигураций обозначим как F. Входным алфавитом каждой жертвы Ui  является множество всех пар вида (F1,F2),где F1є({0}UF’), а F2єF’. Входным алфавитом хищника Wс является множество всех пар вида (F1,F2), где F1, F2єF.

Момент времени 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).