Доказательство: Рассмотрим автомат хищник с краской Wс(R, V) описанный в лемме 1. Этот автомат, стартуя из любой клетки плоскости расположения, обходит плоскость. Поскольку каждая клетка плоскости может принадлежать траектории некоторой жертвы, автомат Wс, обходя плоскость, проверяют каждую клетку своей зоны обзора, на принадлежность траектории некоторой жертвы, ожидая появления жертвы в ней Nmax тактов подряд. По прошествии этих Nmax тактов будем считать клетку проверенной автоматом.  Поскольку все жертвы принадлежат классу A1, их траектории, соответствующие периодичной части последовательности выходных символов, замкнуты. По условию теоремы, число состояний каждой жертвы n ≤ Nmax. Следовательно, если некоторая клетка принадлежит периодичной части траектории некоторой жертвы, за Nmax тактов эта жертва посетит ее.

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

Если в зоне обзора автомата нет жертв, то Wс действует согласно описанию, за тем исключением, что каждому шагу Wс, предшествует группа Nmax тактов, в течение которых автомат неподвижен. Таким образом, автомат в начальные Nmax тактов неподвижен, далее автомат чередует шаг, соответствующий шагу автомата Wс по лемме 1  с группой шагов по Nmax тактов.

Очевидно, что следую заданному алгоритму обхода, в какой-то момент хищник обнаружит жертву. Кроме того, если хищник обнаружил жертву, и обнаружение произошло не в начальные Nmax тактов, то жертва не обнаруживает хищника. Это следует из того, что обзор жертвы на единицу меньше обзора хищника. Из построения автомата видно, что на каждом такте, за исключением начальных Nmax тактов, не проверенными для Wс могут быть только те клетки, которые находятся на расстоянии R от него. Т. е., на предыдущих тактах автоматом было установлено, что клетки, расположенные на расстоянии меньшем R от W, не принадлежат траектории какой-либо жертвы. Следовательно, если автомат W обнаруживает жертву, то она расположена на расстоянии R от него. Поскольку обзор жертвы R-1, то жертва не обнаруживает хищника.

НЕ нашли? Не то? Что вы ищете?

  Если  в момент ф-1 жертва находится в зоне обзора, а в момент ф уже покинула её, хищник продолжает придерживаться своего алгоритма обхода плоскости. Очевидно, что жертва не обнаружила его, поэтому не меняет траекторию.

Если в момент ф-1 жертвы нет в зоне обзора, а в момент ф она попадает в неё или в моменты ф-1 и ф жертва находится в зоне обзора, хищник начинает преследование.

Преследование автоматом W жертвы происходит следующим образом. Автомат W движется с максимальной скоростью в направлении жертвы, и при каждом ходе он раскрашивает клетку, в которой он находиться последовательно, в занумерованный цвет. Как было доказано в лемме 1, ему нужно не более чем R-V тактов, для того чтобы настичь жертву, а следовательно ему нужно R-V  красок для того, чтобы оставить последовательность красок, по которым он вернется к границе спирали, по которой он обходил плоскость. Ввиду того, что спираль разделена на четыре части красками 1,2, 3,4, автомат может найти точку, откуда он стартовал. Т. е. если на границе спирали он видит краску 4, то он идет на север, пока не увидит краску 3, далее идет запад, до тех пор, пока не увидит краску 2, после чего он занимает место, ближайшей клетки, с краской 1, которая и является точкой старта, откуда он стартовал изначально. С этой клетки начинается обход плоскости заново. Нам нужно обходить плоскость счетное число раз, потому как во время преследования жертвы, хищник мог «спугнуть» других жертв, будучи обнаженными ими и они могли изменить свои траектории.

Очевидно, для реализации автомата требуется конечное число состояний автоматов и (V-R+5) красок. Поскольку каждый раз после поимки жертвы возвращается в начальное расположение, и все жертвы принадлежат классу A1, все жертвы будут пойманы. Теорема доказана.

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

Доказательство:

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

Рассмотрим автомат W из леммы 1. Он обходит плоскость счетное число раз. Ввиду того, что автомат обходит каждую клетку плоскости счетное число раз, то в какой-то такт в его обзор попадет след жертвы.

Первый найденный след жертвы, будет точкой старта, для нового обхода, с новым набором красок. Те, что остались на плоскости автоматом игнорируются и воспринимаются, как белые. Повторяется процесс обхода, только теперь центром спирали будет являться первый найденный след автомата.

Понятно, что в какой-то момент автомат найдет второй след, который будет находиться на границе спирали обхода. Через эти два следа можно построить вектор перемещения жертвы. То, как можно наикратчайшим путем от границы 4-х цветной спирали добраться до её центра, уже было показано в доказательстве теоремы 2. Ввиду того, что у автомата жертвы не более N состояний, то, хищнику, просто нужно запомнить не более чем N* (V-1) состояний, между двумя найденными следами, которые определяют вектор перемещения жертвы. Далее, автомат просто движется по вектору перемещения жертвы, в одном из направлений.

Если на следующей точке вектора он видит след, то он продолжает движение по вектору в этом направлении. Если следа не обнаружил, то останавливается в этой точке и ждет N тактов.  Если жертва не появилась, он идет в другом направлении, придерживаясь этого алгоритма. Ввиду того, что жертва принадлежит классу A2. Теорема доказана.

Теорема 4:

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

Доказательство:

Как было доказано в теореме 1: автомат с краской может обойти плоскость, то есть существует такт, в который в обзор автомата попадет либо сама жертва, либо её след. Если в обзор попала сама жертва, то автомат начинает преследование, и как было доказано в лемме 2, жертва будет поймана. В том, случае, когда хищник встречает след, ввиду того, что траектория жертвы несамопересекающаяся у нее будет не более двух направлений. Хищник выбирает любое и начинает двигаться по следу с максимальной скоростью. Возможно 2 случая:
1) Жертва будет настигнута на конце следа

2)  След закончиться

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

Лемма 3.

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

Доказательство.
Рассмотрим следующую физически реализуемую траекторию:

Изначально, Ac(V, R) и N состояниями расположен в нулевой координате. Нужно используя следующий набор выходных символов A(1),…A(i),B(1),… A(1),…A(i),B(1),… такой что (i -1 > R) дойти до клетки с координатой ([N*(С+1)^2R/(i+1)]+1)*(i-1)*V и вернутся в точку старта.

В обзор автомата попадает 2*R клеток ленты.

Рассмотрим случай поведения автомата без краски. В обзор будут попадать только белые клетки, соответственно, для сознательного движения, каждый шаг будет использоваться отличное состояние. Разобьем весь путь автомата на промежутки типа A(1),…A(i),B(1). За этот промежуток автомат без краски сумеет преодолеть расстояние равное (i - 1)*V. Сколько таких промежутков сможет осуществить автомат с N состояниями сознательно? – [N/(i +1)]. За такой промежуток времени автомат проходит расстояние равное (i - 1)*V, Т. е. автомат в [N/(i - 1)]*(i - 1)*V координате уже не сможет посчитать следующий промежуток A(1),…A(i),B(1) и он зациклится. Т. е. Он не сможет используя данную выходную последовательность добраться до координаты ([N/(i + 1)] + 1)*(i - 1)*V и вернутся в точку старта.

В случае с красками, автоматом отличает С красок, которые он имеет и белую, в которую по определению закрашена лента изначально. В обзоре попадают 2*R клеток. Можно получать (С+1)^2R не повторяющихся комбинаций красок в этой зоне обзора. Т. е. сперва фиксируем 2R-1 краску, и получаем, что можно С+1 способ раскраски. Фиксируем 2R – 2 красок и получаем (С+1)(С+1) способов. Раскрашивая все клетки обзора, можно получить (С+1)^2R отличных наборов раскрашенных клеток. Это дает нам то, что автомат с красками может с одним состоянием ((С+1)^2R – 1)*V клетку вправо сознательно. Для этого ему нужно будет красить клетки всевозможными комбинациями(С+1)^2R красок. Т. е. (С+1)^2R состояний автомата без краски становятся эквивалентны 1 состоянию автомата с краской.

Заменим количество состояний у автомата без краски на N*(С+1)^2R/(i+1) и получим [N*(С+1)^2R/(i+1)]*(i-1)*V оценку, после которой автомат с краской не сможет вычислить свой такт. Т. е. он не сможет используя вышеописанные выходные символы дойти до координаты с номером ([N*(С+1)^2R/(i+1)]+1)*(i-1)*V и вернуться в точку старта.

Лемма Доказана.

Список использованной литературы:

[1] , , “Ведение в теорию автоматов”, Москва, Наука, 1985, стр. 8-31.

[2] “Об автоматной модели преследования”, Дискретная математика, т.19, вып.2., стр. 131-160, 2007 г.

[3] «Преследование автоматов-жертв малочисленными коллективами автоматов-хищников», дипломная работа, Ташкент 2009г.



Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6