Автор: Белоус Ю.А., Грунский И.С.
Источник: «Проблемы информатики и моделирования» (ПИМ-2014) / Тезисы XII международной научно – технической конференции. — Харьков, НТУ «Харьковский Политехнический Институт» — 2014. Запланировано к участию в конференции 15.10.2014 г.
В работе рассматривается проблема распознавания лабиринта блуждающим по нему агентом: пусть задано слово в алфавите «n, s, o, w» обхода прямоугольного выпуклого лабиринта. Требуется найти алгоритм перемещения агента по лабиринту и получение при этом представления однозначно определяющего лабиринт.
Принцип работы алгоритма заключается в определении поля лабиринта, т.е. наименьшего по площади прямоугольника, в который вписывается лабиринт и выделения из него прямоугольника максимального по площади. После выделения прямоугольника он удаляется из лабиринта. Получаем новый лабиринт. Доказано, что он является выпуклым лабиринтом без дыр и мостов. Для него строится новое слово и новое поле. Выполняется до тех пор, пока слово обхода не станет пустым. Поле П((x,y)w,h) характеризуется координатой (x,y)=(0,0) северо-западного угла, шириной w и длиной h.
В результате по слову обхода получаем систему прямоугольников, покрывающих лабиринт. Доказано, что эта система однозначно определяет лабиринт и зачастую требует меньшей памяти для своего хранения.
Полученная система прямоугольников является разбиением исходного лабиринта. Примеры показывают, что зачастую целесообразно лабиринт представлять системой пересекающихся прямоугольников, которые образуют покрытие лабиринта. Оптимальный выбор такого покрытия является сложной комбинаторной проблемой, требующей своего исследования.