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

1.1. История вопроса.

Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской в работе [5]. В этой работе рассматривается взаимодействие двух конечных автоматов W и Z («хищника» и «жертвы») в шахматных лабиринтах, имеющих вид квадрата со стороной I. Две клетки такого лабиринта считаются соседними, если они имеют общую сторону. Каждый из автоматов W и Z способен обозревать клетки, соседние той, в которой он находится (все такие клетки, вместе с клеткой в которой на-ходрттся сам этот автомат, образуют его зону обзора). В зависимости от состояния своей зоны обзора (т.е. от наличия и расположения в зоне обзора клеток границы квадрата и от наличия и расположения в зоне обзора автомата-противника), хищник и жертва могут перемещаться за один такт в одну из соседних клеток, либо стоять на месте. Хищник и жертва делают ходы поочередно. Считается, что хищник поймал жертву, если ohpi оказались в соседних клетках.

При фиксированном произвольном размере I стороны квадрата, в котором происходит преследование, изучаются два вопроса.

1. Для каждого ли автомата Z существует автомат W, ловяющий Z в данном лабиринте при произвольных начальных расположениях W и Z?

2. Существует ли универсальный автомат-хищник W, ловящий любую жертву Z в данном лабиринте при при произвольных начальных расположениях W и Z?

На эти вопросы в работе [5] получены следующие ответы. Установлено, что для любых l, n е N существует W с числом состояний 0(п • Z2), который ловит за время 0(п ¦ 14) любой автомат-жертву Z с числом состояний не большим п, в квадрате со стороной, не большей при любом начальном расположении W и Z. Установлено, что не существует автомата W, ловящего любой Z в произвольном квадрате с фиксированной длиной стороны 1,1 >8.