ЖАДНЫЙ АЛГОРИТМ РАЗЛОЖЕНИЯ ПРЯМОУГОЛЬНОГО ЛАБИРИНТА БЕЗ ДЫР В СИСТЕМУ МАКСИМАЛЬНЫХ ПРЯМОУГОЛЬНИКОВ

Аннотация

Разработан алгоритм выделения максимальных по площади прямоугольников из шахматного лабиринта.

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

Постановка проблемы

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

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

Анализ литературы

В работе [2] рассматривается проблема распознавания шахматного лабиринта с помощью коллектива автоматов. Исходными данными является неизвестный шахматный лабиринт. Предлагаются алгоритмы работы автомата – исследователя (АИ) и автомата – экспериментатора (АЭ), которые позволяют распознать шахматный лабиринт в виде комплекса прямоугольных областей. Результат распознавания представляется в виде формулы, описывающей лабиринт с помощью структуры прямоугольников и их расположения относительно друг друга.

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

Цель статьи – создание нового алгоритма для распознавания лабиринтов с более экономным представлением слова обхода лабиринта по внешнему контуру.

Постановка задачи исследования

Пусть задано слово обхода v по внешнему контуру прямоугольного выпуклого лабиринта без дыр в коде Фримена n, s, o, w. Требуется построить систему прямоугольников:

1) покрывающих этот лабиринт без их пересечения;

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

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

Ребра лабиринта отмечены направлением перехода от вершины к вершине: n – север, s – юг, o – восток, w – запад.

Решение задачи и результаты исследования.

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

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

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

Алгоритм:

1. Анализируем «северный» прямоугольник. Из начала слова v выделяем o^k до смены буквы, и из конца слова – n^l до смены буквы, т.е. получим слово v = o^k v' n^l. Из начала слова v' выделяем s^t до смены буквы. Вычисляем площадь прямоугольника S_n = k * (min (l,t)).

2. Анализируем «западный» прямоугольник. Если слово v'= v"wⁱ, где i > 0, то из конца слова v' выделяем w^r до смены буквы. Вычисляем площадь прямоугольника S^w = l * (min (k,r)).

3. Если S_n > S_w, то переходим к пункту 4, иначе к пункту 9.

4. Выделяем «северный» прямоугольник и полагаем, что рабочая точка РТ равна (0,0). Для этого переходим к пункту 5.

5. Если l < t, то переходим к пункту 6. Если l > t, то переходим к пункту 7.

6. l < t. Формируем прямоугольник П(k,l), который описывается количеством k ребер по оси x и количеством l ребер по оси y. Проверяем угол на выпуклость/вогнутость. Если угол вогнутый – переходим к пункту 6.1, иначе к пункту 6.2.

6.1. Угол вогнутый. Формируем новый обход: имеющееся слово v = o^k s^t v" o^r n^l, заменяем новым словом v = o^k+r s^t-l v" и формируем координаты новой рабочей точки (-r,l).

6.2. Угол выпуклый. Формируем новый обход: исходное слово v = o^k s^t v'' w^r n^l, заменяем новым словом v = o^k-r s^t-l v" и формируем координаты новой рабочей точки (r,l).

7. l > t. Формируем прямоугольник П(k,t). Проверяем угол на выпуклость/вогнутость. Если угол выпуклый – переходим к пункту 7.1, а иначе к пункту 7.2.

7.1 Угол выпуклый. Формируем новый обход: имеющееся слово v = o^k s^t w^r v'' n^l, заменяем новым словом v = o^k-r v" n^l-t и формируем координаты новой рабочей точки (0,t).

7.2. Угол вогнутый. Формируем новый обход: имеющееся слово v = o^k s^t o^r v'' n^l, заменяем новым словом v = o^k+r v" n^l-t и формируем координаты новой рабочей точки (0,t).

8. Получаем П(k,min(l,t)), новое слово обхода v оставшейся части лабиринта и новую рабочую точку.

9. S_w > S_n. Выделяем «западный» прямоугольник и полагаем, что рабочая точка РТ равна (0,0). Для этого переходим к пункту 10.

10. Производим вычисления аналогичные пунктам 4 – 8 с учетом того, что выделяется прямоугольник П(min (k,r), l) и получаем новое слово обхода оставшейся части лабиринта и новую рабочую точку.

Доказано, что в результате полученная система прямоугольников удовлетворяет условиям 1 и 2. Таким образом, алгоритм корректен. Этот алгоритм является естественным развитием алгоритмов из [3,5]. Исследование алгоритма показало, что он дает задание лабиринта более просто, чем исходное слово v.

Выводы

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

Список литературы

1. Кудрявцев В.Б. Автоматы в лабиринтах / В.Б. Кудрявцев, Г. Килибарда, Ш. Ушумлич // Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (23-27 октября 2006 г.). – М. : Издательство механико-математического факультета МГУ. – Т. 1, ч. 1. – С. 159-163.

2. Кудрявцев В.Б., Калибарда Г., Ушумлич Ш. Независимые системы автоматов в лабиринтах / В.Б. Кудрявцев, Калибарда Г., Ушумлич Ш. // «Дискретная математика» 2003 г., т. 15, вып. 2. – C. 3 – 39.

3. Кудрявцев В.Б., Калибарда Г., Ушумлич Ш. Независимые системы автоматов в лабиринтах / В.Б. Кудрявцев, Калибарда Г., Ушумлич Ш. // «Дискретная математика» 2003 г., т. 15, вып. 3. – C. 3 – 40.

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

5. Белоус Ю.А., Грунский И.С. Разложение прямоугольного лабиринта без дыр в систему прямоугольников // Ю.А. Белоус, И.С. Грунский / Тезисы XII международной научно – технической конференции «Проблемы информатики и моделирования» (Харьков 2012 года). – Харьков, НТУ «Харьковский Политехнический Институт». – С. 3.

6. Грунская В.И. О восстановлении плоских шахматных лабиринтов по словам / В.И. Грунская // Материалы VIII Международного семинара «Дискретная математика и ее приложения» (2-6 февраля 2004 г.). – М. : Издательство механико-математического факультета МГУ, 2004. – С. 264-267.

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