О РАСПОЗНАВАНИИ ПРЯМОУГОЛЬНОГО ЛАБИРИНТА БЛУЖДАЮЩИМ ПО НЕМУ АГЕНТОМ

Актуальной проблемой математической информатики в теоретическом и прикладном аспектах является проблема распознавания неизвестной среды (лабиринта) блуждающим по нему агентом (см. фундаментальный обзор [1]). Теоретическая важность и актуальность этой проблемы определяется так же тем, что распознавание лабиринтов является из центральных проблем теории автоматов [2]. В настоящей работе рассматривается следующий вариант этой проблемы:

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

Агент находится в вершине лабиринта. Агент видит возможные направления движения, различает внутренние точки лабиринта и граничные, лежащие на внешнем контуре. Агент может двигаться от вершины к вершине лабиринта, помечая движение последовательностью знаков кода Фримена, в котором n – север, s – юг, o – восток, w – запад.

Требуется найти алгоритм перемещения агента по лабиринту и получение при этом представления, однозначно определяющего лабиринт.

Предлагается следующий метод решения этой задачи.

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

2. Агент обходит лабиринт по внешнему контуру по часовой стрелке и получает слово обхода – последовательность движений и слово координат пройденных вершин [3]. Через µ(t) обозначается направление движения А из вершины t.

Для определения координат углов лабиринта А движется по слову до смены буквы:

1) при µ(s)=n^k координата y:=y+k, а x остаётся неизменным;

2) при µ(s)=o^t координата x:=x+t, а y остаётся неизменным;

3) при µ(s)=s^p координата y:=y-p, а x остаётся неизменным;

4) при µ(s)=w^q координата x:=y-q, а y остаётся неизменным;

3. По p и q определяем поле лабиринта, т.е. наименьший по площади прямоугольник, в который вписывается лабиринт.

Для нахождения границ поля находим координаты с минимальным и максимальным значением по x и по y среди координат углов, соответственно. Сумма их модулей является длиной и шириной поля. Сдвигаем поле и лабиринт в нем так, чтобы северо-западный угол поля получил координату (0,0) соответствующим образом меняя координаты вершин лабиринта. Таким образом поле П((x,y)w,h). Характеризуется координатой (x,y)=(0,0) северо-западного угла, шириной w и длиной h.

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

Пункт 4 выполняется до тех пор, пока слово обхода p не станет пустым.

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

Из вышесказанного следует, что в пункте 4 можно выбирать не только северную, но и любую другую границу поля. Очевидно, что полученная система прямоугольников существенно зависит от такого выбора на каждом шаге. В [4] предложен жадный алгоритм такого выбора. В п. 4 при этом строится четыре прямоугольника, выбирая северную, южную, восточную, западную стороны текущего поля. Затем среди четырех прямоугольников выбирается максимальный по площади.

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

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

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

1. Кудрявцев В.Б. Системы автоматов в лабиринтах / В.Б. Кудрявцев, Г. Килибарда, Ш. Ушумлич // Интеллектуальные системы – М. : Изд-во мех.-мат. ф-та МГУ. – Т. 10, вып. 1-4. – С. 449-564.

2. Кудрявцев В.Б. Анализ и синтез автоматов по их поведению / В.Б. Кудрявцев, И.С. Грунский, В.А. Козловский // Там же – С. 345 - 448.

3. Стародубцева Ю.Н. Распознавание шахматного лабиринта с помощью коллектива автоматов // Ю.Н. Стародубцева // V міжнар. наук.-практ. конф. молод. учених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія» (12-13 травня 2011 р.). Том 1. – Донецьк, 2011. – С. 109-113.

4. Белоус Ю.А. Жадный алгоритм разложения прямоугольного лабиринта без дыр в систему прямоугольников / Ю.А. Белоус, И.С. Грунский // Х Ювілейна міжн. наук. – практ. конф. «Математичне та програмне забезпечення інтелектуальних систем» (Дніпропетровськ 21-23 листопада 2012 року). – Дніпропетровськ, Дніпропетровський нац. університет імені Олеся Гончара 2012. – С. 24 – 25.