Алгоритм построения пути в лабиринте с минимальным количеством изгибов

Определения

• Лабиринт

▎Билет 1. Алгоритм построения пути в лабиринте с минимальным количеством изгибов

SEARCH: §4. Пути в лабиринте.

▎Задача

Построения пути в лабиринте с минимальным числом изгибов. Иначе говоря, ломаная,

соединяющая две заданные точки, должна иметь наименьшее число звеньев среди всех

ломаных, которые также соединяют заданные точки.

▎Математическая модель

Для представления направлений используем четыре вспомогательных вектора:

• d₁ = (1, 0) — вправо
• d₂ = (0, 1) — вверх
• d₃ = (-1, 0) — влево
• d₄ = (0, -1) — вниз Эти векторы служат для перехода от точки p к новой точке p + dₖ . ▎Хранение информации о направлениях Для хранения информации о том, как достигнута каждая точка, используем число P[u] : P[u] = 20 ⋅ (k + 1) + a₁ ⋅ 2⁰ + a₂ ⋅ 2¹ + a₃ ⋅ 2² + a₄ ⋅ 2³ где aᵢ = 1 , если точка помечена по i -му направлению, и aᵢ = 0 в противном случае. ▎Алгоритм

1. Инициализация: Начинаем с точки входа v , которая образует нулевой фронт распространения волны.
2. Формирование фронтов: • Объявляем все точки, до которых можно дойти из v без поворотов, точками первого фронта. • Для каждой такой точки запоминаем направление, по которому пришли.
3. Распространение волны: Для каждого нового фронта k+1 : • Относим в него все точки, до которых можно дойти от любой точки k -го фронта по прямой. • Храним все направления, по которым они могут быть достигнуты. • Распространение волны завершаем либо в тот момент, когда мы достигнем точки выхода w, либо когда ни одной новой точки нельзя достигнуть. В первом случае искомый путь существует и может быть построен с помощью расставленных ранее меток, отвечающих за направление прихода в точку; во втором случае ни одного пути от входа v до выхода w не существует.
4. Движение по направлению: • Мы начинаем построение пути с конечной точки w. Для этого число P[w] mod 20 раскладываем по степеням двойки и фиксируем какое-нибудь число i такое, что присутствует в этом разложении. Это означает, что точка w помечена по i-му направлению. • Двигаемся теперь из w по направлению, противоположному i-му, до тех пор, пока не встретим точку u такую, что двоичное разложение числа P[u] mod 20 не содержит (P.S анализируем сначала следующую, прежде чем перейти, она может вести в тупик, в неё не совершаем переход, пока не удостоверимся, что она содержит ). Это означает, что точка U помечена по другому направлению. • Выбираем теперь какое-нибудь новое значение i, для которого раскладываем по степеням двойки и фиксируем какое-нибудь число i такое, что входит в разложение числа P[u] mod 20, и продолжаем процесс из точки u.
5. Завершение: • Алгоритм завершает работу в момент, когда P[u] (mod 20) = 0 , поскольку единственной точкой, удовлетворяющей этому условию, является точка входа v . ▎Восстановление пути Для восстановления пути начинаем с конечной точки w :
6. Вычисляем P[w] (mod 20) и раскладываем по степеням двойки.
7. Находим i , такое что 2ⁱ⁻¹ присутствует в разложении. Это означает, что точка w помечена по i -му направлению.
8. Продолжаем в обратном порядке, используя сохранённые направления, пока не достигнем точки входа v . ▎Асимптотика Алгоритм имеет временную сложность: O(n ⋅ m) где n и m — размеры лабиринта. В худшем случае необходимо просмотреть все точки лабиринта P , прежде чем будет найден требуемый путь или можно будет утверждать, что искомого пути не существует. Лабиринт содержит n ⋅ m точек, а количество операций, необходимых для обработки каждой точки, ограничено сверху константой.