Оптимизация поиска выхода из лабиринта представляется относительно простой задачей. Но она подразумевает накопление данных, обучение, если угодно.
Как только возникает потребность накапливать данные, стоит исходить из того, что этих данных станет много и придётся прибегнуть к технологиям из области баз данных.
Здесь представлена робкая попытка разобраться в теме.
1. Лабиринт.
Не будем заниматься онтологией понятия лабиринт, "koń, jaki jest, każdy widzi".
Для нас это специализированный граф, одна или несколько вершин которого (выходы) отмечены особым образом, задача достичь такой вершины.
1.1. Построение лабиринтов.
Известно изрядное количество методов генерации лабиринтов. В наших целях сгодится любой, не порождающий циклов. Наличие циклов требует специальных усилий по их обнаружению и устранению, не привнося ничего полезного в результат.
Для создания лабиринтов выбран метод “растущего дерева”, в основном за простоту:
выбираем стартовую клетку
изначально каждая клетка лабиринта закрыта со всех сторон
в цикле
проверяем, каких соседей текущей клетки мы еще не посещали
если таких кандидатов несколько, случайно выбираем одного и переходим туда, ломая перегородку между ними
остальных кандидатов заносим в стек
если кандидатов нет (тупик), достаем следующего из стека
если стек пуст, лабиринт построен
1.2. Статистика отдельных клеток.
Когда работаешь с данными, полезно понимать, с чем имеешь дело. Хотя бы в общих чертах, классифицировать объекты, собрать статистику... Этим и займёмся. Для начала введём код клетки - маску её открытых сторон.
Код вычисляется так:
если она открыта сверху, добавляем 1
... справа, добавляем 2
... снизу, добавляем 4
... слева, добавляем 8
Как видим, статистика неравномерна: клеток, закрытых со всех сторон нет, открытых со всех сторон порядка двух десятков, больше всего проходных клеток - открытых сверху и снизу или справа и слева.
1.3. Статистика пар клеток.
Имеются соседние клетки, между которыми нет преграды.
Код пары клеток вычисляется так:
младшие 4 разряда - код первой клетки
два разряда на направление - вверх (0), вправо (1), вниз (2) и влево (3)
старшие 4 разряда - код второй клетки
Фиг.3 & 4 показывают, что несмотря не некоторые отличия, разные лабиринты в целом имеют близкие распределения пар клеток.
Для наглядности, посмотрим на распределение межклеточных переходов.
X - код исходной клетки
Y - код клетки прибытия
наверх вправо
вниз влево
2 Навигация
Решим несколько задач, постепенно усложняя условия.
2.1. Поиск выхода.
По условиям, у нас есть вся информация о лабиринте а также известно начальное положение, нужно лишь добраться до выхода (пусть это точка (0, 0)).
Для поиска выхода воспользуемся “волновым алгоритмом Ли” т.к. лабиринт фактически планарный граф с ребрами одной длины. Волновой алгоритм - вырожденный случай алгоритма Дейкстры (Dijkstra).
Кратчайший путь из точки (93, 94) в точку (0, 0) составляет 2530 шагов, всего в поиске посещено 6 686 клеток из 10 000.
Искомый путь - из правого верхнего (практически) к левому нижнему углу.
2.2. Поиск выхода из неизвестной точки.
Условия те же, что и в предыдущем случае, схема лабиринта доступна, но неизвестно начальное положение. Попробуем определить его и сведём тем самым задачу к уже решенной.
Находясь в некоторой клетке мы можем видеть лишь какие стороны доступны для прохода и вычислить код клетки.
Пусть исходная клетка та же (93, 94), тот же лабиринт 100х100
Код стартовой точки равен 10 (есть проход справа и слева) и согласно ранее приведённой статистике, таких точек в лабиринте около полутора тысяч. Не очень то это помогает установить своё местоположение.
Введем расширенный код клетки, в котором задействованы также и соседние клетки:
младшие 4 разряда - код клетки
следующие 4 разряда - код соседа сверху, если вверх прохода нет, то 0
..
разряды с 16 по 19 - код соседа слева, …
Для клетки (93, 94) расширенный код равен 0x6090A.
В лабиринте 100х100 клеток с таким расширенным кодом оказалось 138. Уже лучше, но всё равно многовато. Дальнейший порядок действий таков: подобно волновому алгоритму, станем расширять контекст вокруг стартовой точки и отсеивать кандидатов, пока не останется только один.
Перейдём на соседнюю правую клетку и подсчитаем расширенный код для нее.
(94, 94) => 0xA0069, таких клеток в лабиринте 106.
А вот пар справа налево 0x6090A, 0xA0069 нашлось четыре десятка.
Далее подсчитаем расширенный код для клетки левой от исходной (92,94): 0x9A06 и проверим наличие троек (0x9a06, 0x6090A, 0xA0069)
Таковых нашлось всего 15 штук.
(40,15),(41,15),(42,15)
(73,20),(74,20),(75,20)
(72,21),(73,21),(74,21)
(35,3),(36,3),(37,3)
(50,31),(51,31),(52,31)
(4,33),(5,33),(6.33)
(50,38),(51,38),(52,38)
(42,40),(43,40),(44,40)
(61,5),(62,5),(63,5)
(1,86),(2,86),(3,86)
(3,87),(4,87),(5,87)
(92,94),(93,94),(94,94)
(33,95),(34,95),(35,95)
(35,96),(36,96),(37,96)
(81,96),(82,96),(83,96)
Хорошо, проверяем еще одну клетку - вправо и вверх от исходной (расширенный код - 0x9906)
(40,15),(41,15),(42,15) (42,16) => 0x9A06
(73,20),(74,20),(75,20) (75,21) => 0x9A06
(72,21),(73,21),(74,21) (74,22) => 0x9A06
(35,3),(36,3),(37,3) (37,4) => 0x9C06
(50,31),(51,31),(52,31) (52,32) => 0x9C06
(4,33),(5,33),(6.33) (6, 33) => 0x9A06
(50,38),(51,38),(52,38) (52,39) => 0x9A06
(42,40),(43,40),(44,40) (44,41) => 0x9C06
(61,5),(62,5),(63,5) (63,6) => 0x9D06
(1,86),(2,86),(3,86) (3,87) => 0x9A06
(3,87),(4,87),(5,87) (5,88) => 0x9906
(92,94),(93,94),(94,94) (94,95) => 0x9906
(33,95),(34,95),(35,95) (35,96( => 0x9A06
(35,96),(36,96),(37,96) (37,97) => 0x9906
(81,96),(82,96),(83,96) (83,97) => 0x9C06
Осталось три кандидата. Проверяем точку влево и вниз от исходной,
у нас её расширенный код равен 0x30069
(3,87),(4,87),(5,87) (3,86) => 0xA0069
(92,94),(93,94),(94,94) (92,93) => 0x30069
(35,96),(36,96),(37,96) (35,95) => 0x953
Остался один вариант, исходная точка найдена, это (93,94).
Путь из этой точки уже найден, см Фиг.7.
Мы исходили из того, что известно направление (есть компас). Но в случае его отсутствия принципиально ничего не меняется, просто кандидатов становится больше в 4 раза.
Итак, за ограниченное число шагов c помощью. расширения контекста (обследовали окрестности 5 клеток) удалось точно установить своё положение. Теперь, для поиска выхода можно запускать волновой алгоритм.
2.3. Поиск выхода вслепую.
Если раньше была доступна топология лабиринта, то сейчас попробуем выбраться, не имея никаких знаний о нем. А также нет возможности определить собственное положение внешними средствами.
Воспользоваться здесь волновым алгоритмом невозможно т.к. он требует большого количества переходов между ячейками на фронте волны. Обладая топологией лабиринта можно себе это позволить т.к. волна эфемерна, передвижение ничего не стоит, повторять тот же путь ногами слишком дорого.
В данных условиях практически применяют два метода:
Алгоритм Тремо. Согласно ему,
оставляются метки в начале и конце линейных участков лабиринта.
если был обнаружен тупик, то при возврате запрещаем вход в него
на развилке выбираем случайный неотмеченный путь
Правило правой (левой) руки.
касаемся рукой стены
идём вперёд так, чтобы рука всегда касалась стены
если в лабиринте нет циклов, рано или поздно приходим к выходу
Поскольку для построения лабиринта использовался алгоритм растущего дерева, не порождающий циклы, воспользуемся вторым вариантом как более простым, не требующим оставлять метки в лабиринте и интуитивно более понятным.
Стартуем из той же точки, исходная ориентация - лицом на север, движемся по правой руке.
Общая длина пройденного пути более 14 тысяч шагов (всего в лабиринте 10 000 клеток), т.е. значительная часть времени была потрачена на прохождение тупиков.
Избавимся от них.
Результат идентичен оному на Фиг.7 с использованием волнового алгоритма. Правда, блуждали примерно вдвое дольше. Это особенность метода растущего дерева. Дерево (в данном случае) имеет корень в точке (41,67) и для того, чтобы попасть в точку выхода (0,0) с хорошей вероятностью (½ что попали в разные от корня ветки) придётся подняться по дереву до корня, а потом спуститься до нужной точки.
Как ни парадоксально, путь, найденный по правилу левой руки не отличается найденного ранее “правого”. По той же самой причине. Данный лабиринт - дерево, уложенное в квадрат 100х100. Подняться до корня можно только одним способом и неважно, держаться за стеночку правой или левой рукой. Возможно, при этом пришлось пройти разные тупики, но их мы отсекаем.
2.4. Поиск выхода вслепую опять и опять.
Но что, если постоянно приходится выбираться из одного и того же лабиринта, о котором изначально ничего не известно. Первый раз вслепую. Но дальше, неужели каждый раз необходимо обходить большую часть клеток?
Очевидно нет, у нас есть пока непонятно как устроенный индекс, благодаря которому, появляется возможность обучаться. Определимся что именно стоит хранить в этом индексе.
Общая логика такова - найдя выход из лабиринта, получаем привязку всех пройденных точек. Как было показано ранее, достаточно хранить расширенные коды посещенных клеток, чтобы с большой вероятностью можно было определить, известна нам эта точка или нет.
План такой:
начинаем проходить лабиринт согласно правилу одной из рук
придя в новую клетку, вычисляем её расширенный код
проверяем, встречался ли такой код в известной нам части лабиринта
если встречался (возможно, несколько раз)
проверяем соседние клетки, известные нам по раннему опыту - пытаемся пройти по тому пути, который ранее приводил к выходу
если удалось, записываем вновь пройденную часть пути в индекс
иначе, возвращаемся к обходу лабиринта по правилу одной из рук
Не попасть на посещенную часть лабиринта невозможно, выход один. А даже если бы их было несколько, это принципиально ничего не меняет.
Стоит определиться, какую именно часть пройденного пути стоит сохранять в индексе. Технически, есть возможность сохранять информацию о всей пройденной части лабиринта. Альтернатива - только путь, ведущий к выходу, без тупиков. Принципиально они мало отличаются, но второй вариант требует меньше ресурсов.
Конкретно в вышеописанном случае, путь (93,94) => (0,0) стоит 2530 шагов, тогда как всего посещено 6 686 клеток. В двумерном случае лабиринта без циклов. В лабиринте с циклами путь может быть существенно короче а пройденная часть очень большой. В случае больших размерностей ситуация усугубляется. Так что выбор редакции - сохраняем только найденный путь.
Для каждой клетки:
расширенный код
координаты
расширенный код следующей клетки на пути к выходу. Этот пункт необязателен, но очень полезен для быстрой фильтрации кандидатов.
координаты следующей точки на пути к выходу
Теперь, попав в новую клетку:
вычисляем её расширенный код
ищем кандидатов с таким же кодом в индексе
находим следующую клетку
делаем шаг в том же направлении
сверяем ее расширенный код,
если совпало, находим следующую клетку
…
Попробуем.
На Фиг.13 показан уже знакомый нам путь из точки (93,94), на котором проводилось обучение и новый путь (синий) из точки (50,50).
общее число сделанных шагов до выхода на известный маршрут - 3786
длина пути - 909
вышли на ранее найденный путь в точке (0,30)
расширенный код этой точки - 5a67
в процессе поиска этот код встретился нам 7 раз и 6 раз это было ложное срабатывание
благодаря выходу на известную часть пути удалось сэкономить 76 шагов
76 сэкономленных шагов, не очень много. Попробуем еще раз, теперь из точки (30,30).
общее число сделанных шагов до выхода на известный маршрут - 1390
длина пути - 614
общее число сделанных шагов без обучения - 8886
выход на известный маршрут в точке (32,0)
первый же кандидат привел нас к выходу
На этот раз обучение сэкономило 84% усилий.
И, очевидно, чем больше использовано обучающих маршрутов, тем весомее будет выигрыш.
3. Промежуточные итоги
Обобщим сказанное и сформулируем требования к хранилищу информации .
нужно временное хранилище для текущего поиска, хранения пройденного пути, кодов клеток, …Требование к нему - после нахождения выхода из лабиринта мы должны быть способны восстановить путь, включая координаты и коды клеток
постоянное хранилище для хранения успешно пройденных маршрутов
маршрут хранится в виде пар: переходов из клетки в клетку
в каждом таком переходе находятся контексты обеих клеток - координаты, код, расширенный код
зная конкретную точку, можно найти переход из нее и раскрутить весь остаток пути
должна быть возможность по контексту клетки (как минимум по расширенному коду) получить всех кандидатов на переходы из подобных клеток
Далее предполагается порезвиться на задачах комбинаторной оптимизации.
