Автор: Белоус Ю.А., Грунский И.С.
Источник: «Математичне та програмне забезпечення інтелектуальних систем» - 2012 / Х Ювілейна Міжнародна науково – практична конференція. — Дніпропетровськ, Дніпропетровський національний університет імені Олеся Гончара — 2012, С. 24‐25.
Предложен жадный алгоритм решения следующей задачи: пусть задано слово обхода v по внешнему контуру прямоугольного выпуклого лабиринта без дыр в коде Фримена n, s, o, w. Требуется построить систему прямоугольников, покрывающих этот лабиринт без их пересечения. Алгоритм заключается в пошаговом выделении из v максимального по площади прямоугольника, расположенного в северо – западном углу лабиринта. В этот прямоугольник входит или верхняя горизонтальная граница лабиринта, содержащая рабочую точку, или крайняя западная вертикальная линия границы лабиринта. Затем формируется новый обход оставшейся части лабиринта и новая его рабочая точка. Это выполняется до тех пор, пока v не станет пустым.
Шаг работы алгоритма:
1. Анализируем «северный» прямоугольник. Из начала слова v выделяем ok до смены буквы, и из конца слова – nl до смены буквы, т.е. получим слово v = ok v' nl. Из начала слова v' выделяем st до смены буквы. Вычисляем площадь прямоугольника Sn = k * (min (l,t)).
2. Анализируем «западный» прямоугольник. Если слово v'= v'’wi, где i > 0, то из конца слова v' выделяем wr до смены буквы. Вычисляем площадь прямоугольника Sw = l * (min (k,r)).
3. Если Sn > Sw, то переходим к пункту 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 = ok st v'' or nl, заменяем новым словом v = ok+r st-l v" и формируем координаты новой рабочей точки (-r,l).
6.2. Угол выпуклый. Формируем новый обход: исходное слово v = ok st v'' wr nl, заменяем новым словом v = ok-r st-l v" и формируем координаты новой рабочей точки (r,l).
7. l > t. Формируем прямоугольник П(k,t). Проверяем угол на выпуклость/вогнутость. Если угол выпуклый – переходим к пункту 7.1, а иначе к пункту 7.2.
7.1. Угол выпуклый. Формируем новый обход: имеющееся слово v = ok st wr v'' nl, заменяем новым словом v = ok-r v" nl-t и формируем координаты новой рабочей точки (0,t).
7.2. Угол вогнутый. Формируем новый обход: имеющееся слово v = ok st or v'' nl, заменяем новым словом v = ok+r v" nl-t и формируем координаты новой рабочей точки (0,t).
8. Получаем П(k,min(l,t)), новое слово обхода v оставшейся части лабиринта и новую рабочую точку.
9. Sw>Sn. Выделяем «западный» прямоугольник и полагаем, что рабочая точка РТ равна (0,0). Для этого переходим к пункту 10.
10. Производим вычисления аналогичные пунктам 4‐8 с учетом того, что выделяется прямоугольник П(min (k,r), l) и получаем новое слово обхода оставшейся части лабиринта и новую рабочую точку.