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

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

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

Лабиринт задан массивом 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. Назначим выбранное поле текущим

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

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

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

FrBrGeorge/LabyrinthWalk (last edited 2018-10-28 12:18:36 by FrBrGeorge)