РАСПОЗНАВАНИЕ ШАХМАТНОГО ЛАБИРИНТА С ПОМОЩЬЮ АГЕНТА

Аннотация

В данной работе предложен новый алгоритм распознавания шахматного лабиринта с помощью передвигающегося по нему агента. Агент обходит лабиринт по внешнему контуру и составляет выражение в элементарных движениях, описывающее внешний контур лабиринта. Далее составляется формула лабиринта в виде структуры прямоугольников. Такой подход снижает сложность распознавания шахматных лабиринтов.

Введение

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

Целью работы является создание нового алгоритма для распознавания шахматных лабиринтов с помощью агента, который позволил бы снизить сложность распознавания.

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

1. Постановка задачи

В данной работе в качестве шахматного лабиринта рассматривается плоский неориентированный конечный связный граф G = (V_G , X_G), множество вершин V_G которого есть подмножество множества Z² точек декартовой плоскости с целочисленными координатами, а множество ребер X_G обладает следующим свойством: две любые вершины могут быть соединены ребром только тогда, когда расстояние между ними равно единице [3]. Ребра в графе могут быть двух типов: параллельные оси абсцисс или оси ординат.

Процесс распознавания графа можно разбить на две части:

• обход графа по внешнему контуру и составление выражения, описывающего внешние границы графа;
• преобразование полученного выражения в формулу, описывающую граф с помощью простейших геометрических фигур.

Для распознавания применяется агент, имеющий один камень и одну краску. Агент может воспринимать и анализировать локальную информацию об 1-окрестности вершины, в которой он находится, передвигаться по ребрам графа в четырех координатных направлениях, помечать вершину камнем и снимать пометку, помечать ребра краской.

Направления движения агента по ребрам графа: а - движение вдоль оси х, -а - движение против оси х, b - движение вдоль оси у, - b - движение против оси у. Агент обладает конечной, но бесконечно наращиваемой памятью.

Алгоритм движения агента по внешнему контуру графа

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

Агент обходит внешнюю границу по часовой стрелке следующим образом:

1. Eсли в текущей вершине доступно три направления (см. рис. 1 а) движения, то агент продолжает движение в том же направлении;

2. Eсли в текущей вершине доступно два направления (см. рис. 1 б), то агент выбирает каждый раз крайнее правое ребро: в положении 1 это движение вправо, в положении 2 - движение вверх;

3. Eсли в текущей вершине доступно четыре направления (см. рис. 1 в), то агент выбирает каждый раз крайнее левое ребро: в положении 1 это движение влево, в положении 2 - вверх.