Задача ?обход лабиринта?
Задача обхода лабиринта ? неформальное название частного случая задачи ?проверка связности неориентированного графа?. Случай этот частный, потому что (как правило) в задаче требуется либо проверить достижимость одной вершины графа из другой, либо вдобавок найти минимальный путь.
- Классическая формулировка
Лабиринт задан массивом M?N, каждый элемент массива соответствует участку лабиринта, проходимые участки отмечены, скажем, 1, непроходимые ? 0. Перемещаться можно только по соседним по вертикали или горизонтали проходимым участкам. Требуется, допустим, проверить, можно ли добраться из левого верхнего участка лабиринта в правый нижний (или указать минимальный путь).
Задача имеет множество маскировочных вариаций: лабиринт может быть многомерный или треугольный, вместо карты лабиринта может предлагаться таблица связности, ограничиваться направление и т. д.
Все эти формулировки имеют в себе вот такое общее:
- В задаче фигурируют объекты и связи между ними; требуется проверить, ведет и цепочка связей от одного заданного объекта к другому
Собственно, это и есть граф, объекты ? его вершины, а связи ? ребра
Связи объектов заданы явно: объем входных данных сопоставим с количеством связей и количеством объектов
- Например, ?классическая формулировка? ограничивает количество объектов, а таблица связности ? количество связей.
- Ни связи, ни объекты не изменяются после их задания
? Понятие ?состояние? при обходе графа включает в себя только идентификатор текущей вершины (объекта)
Предлагаемое решение, называемое в народе ?методом заливки?, является упрощенным алгоритмом Дейкстры. Это название возникло оттого, что изначально при его работе модифицировались исходные данные ? по принципу, сходному с алгоритмом закрашивания связной области пикселей растрового изображения.
Для решения нам понадобится:
- Копия исходных данных или новая структура на их основе:
- Каждая вершина имеет служебное поле ?шаг просмотра?, которое изначально нулевое и модифицируется алгоритмом
- ?План разведки?:
- Изначально пустой стек, способный хранить идентификаторы вершин
Алгоритм решения:
Добавляем в план разведки идентификатор вершины-входа в лабиринт; ее шаг просмотра делаем равным 1
- Производим разведку, пока план разведки не пуст:
Увеличиваем шаг просмотра на 1
- Забираем очередную вершину из плана разведки (ее там не остается)
- По всем ребрам, исходящим из данной вершины:
- Устанавливаем в этой вершине текущий шаг разведки
- Если ребро ведет в выход, успешно заканчиваем разведку
- Если ребро ведет в проходимую вершину с нулевым шагом разведки (неразведанную):
- Добавляем ее в план разведки
- Если шаг разведки у вершины выхода нулевой, то пути нет
Если он ненулевой ? это длина минимального пути (+1, да
)
Определение минимального пути
Иногда требуется не только оценить длину пути, но и вывести его. Это легко сделать с помощью поля ?шаг разведки?, в случае неориентированного графа, т. е. когда связь A?B означает также и связь B?A . Построим путь с конца:
- Назначим поле-выход ?текущим?, путь сделаем пустым списком
Пока шаг разведки текущего поля больше 1 (т. е. оно не вход):
Из всех ребер, ведущих в текущее поле выберем любое, шаг разведки которого на 1 меньше текущего шага разведки. Такое поле есть по построению.
- Добавим в начало пути ребро между выбранным и текущим полем
- Назначим выбранное поле текущим
В случае ориентированного графа нам понадобится еще одно поле вершины ? ?обратный путь? ? в которое при добавлении в план разведки мы будем записывать идентификатор предыдущей вершины.
Немного анализа:
- Расход памяти
- Копия исходных данных плюс план разведки, сравнимый по объему с количеством объектов.
- Вычислительная сложность
- Количество просмотров атрибута проходимости и поля ?шаг разведки? сопоставимо с произведением количества объектов и максимального количества связей, которое может иметь один объект. Количество операций добавления и снятия со стека, как и количество модификаций поля ?шаг разведки?, не больше количества объектов.