Задача «обход лабиринта»

Задача обхода лабиринта — неформальное название частного случая задачи «проверка связности неориентированного графа». Случай этот частный, потому что (как правило) в задаче требуется либо проверить достижимость одной вершины графа из другой, либо вдобавок найти минимальный путь.

Классическая формулировка

Лабиринт задан массивом M×N, каждый элемент массива соответствует участку лабиринта, проходимые участки отмечены, скажем, 1, непроходимые — 0. Перемещаться можно только по соседним по вертикали или горизонтали проходимым участкам. Требуется, допустим, проверить, можно ли добраться из левого верхнего участка лабиринта в правый нижний (или указать минимальный путь).

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

Все эти формулировки имеют в себе вот такое общее:

1. В задаче фигурируют объекты и связи между ними; требуется проверить, ведёт и цепочка связей от одного заданного объекта к другому

   • Собственно, это и есть граф, объекты — его вершины, а связи — рёбра

2. Связи объектов заданы явно: объём входных данных сопоставим с количеством связей и количеством объектов

   • Например, «классическая формулировка» ограничивает количество объектов, а таблица связности — количество связей.
3. Ни связи, ни объекты не изменяются после их задания

   • ⇒ Понятие «состояние» при обходе графа включает в себя только идентификатор текущей вершины (объекта)

Предлагаемое решение, называемое в народе «методом заливки», является упрощённым алгоритмом Дейкстры. Это название возникло оттого, что изначально при его работе модифицировались исходные данные — по принципу, сходному с алгоритмом закрашивания связной области пикселей растрового изображения.

Для решения нам понадобится:

1. Копия исходных данных или новая структура на их основе:
   • Каждая вершина имеет служебное поле «шаг просмотра», которое изначально нулевое и модифицируется алгоритмом
2. «План разведки»:
   • Изначально пустой стек, способный хранить идентификаторы вершин

Алгоритм решения

1. Добавляем в план разведки идентификатор вершины-входа в лабиринт; её шаг просмотра делаем равным 1

2. Производим разведку, пока план разведки не пуст:

   1. Увеличиваем шаг просмотра на 1

   2. Забираем очередную вершину из плана разведки (её там не остаётся)
   3. По всем рёбрам, исходящим из данной вершины:
      1. Устанавливаем в этой вершине текущий шаг просмотра
      2. Если ребро ведёт в выход, успешно заканчиваем разведку
      3. Если ребро ведёт в проходимую вершину с нулевым шагом просмотра (неразведанную):
         1. Добавляем её в план разведки
3. План разведки пуст. Если шаг просмотра у вершины-выхода нулевой, то пути нет

4. Если он ненулевой — это длина минимального пути (+1, да )

Определение минимального пути

Иногда требуется не только оценить длину пути, но и вывести его. Это легко сделать с помощью поля «шаг просмотра», в случае неориентированного графа, т. е. когда связь A→B означает также и связь B→A . Построим путь с конца:

1. Назначим поле-выход «текущим», путь сделаем пустым списком

2. Пока шаг просмотра текущего поля больше 1 (т. е. оно не вход):

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

   2. Добавим в начало пути ребро между выбранным и текущим полем
   3. Назначим выбранное поле текущим

В случае ориентированного графа нам понадобится ещё одно поле вершины — «обратный путь» — в которое при добавлении в план разведки мы будем записывать идентификатор предыдущей вершины.

Немного анализа

Расход памяти

Копия исходных данных плюс план разведки, сравнимый по объёму с количеством объектов.

Вычислительная сложность

Количество просмотров атрибута проходимости и поля «шаг просмотра» сопоставимо с произведением количества объектов и максимального количества связей, которое может иметь один объект. Количество операций добавления и снятия со стека, как и количество модификаций поля «шаг просмотра», не больше количества объектов.