Рекурсивная процедура поиска в ширину

Поиск в ширину в пространстве состояний. Поиск путей-кандидатов

Поиск в глубину хорошо работает в таких пространствах состояний, где и тупики, и решения удалены примерно на одно и то же расстояние от начала поиска. Наиболее плохой случай для поиска в глубину следующий: какая-то ветвь графа состояний очень протяженная или бесконечная, а решения находятся на других ветках, на небольшом расстоянии от начала поиска.

Для таких пространств более эффективен поиск в ширину. Если в глубине на каждом шаге имеется ровно один путь-кандидат в решение, то в ширине таких путей-кандидатов несколько.

Рассмотрим поиск в ширину на модельном графе (рис. 2).

Рисунок 2. Модельный граф для поиска в ширину

Начнем поиск в ширину из вершины 1 — имеем начальный путь [1]. Просмотрели вершины 2, 3, 4 смежные с вершиной 1 — получили пути-кандидаты [[2, 1], [3, 1], [4, 1]]. Каждый из них в свою очередь может дать несколько продолжений и т.д.

Будем на каждом шаге хранить список путей-кандидатов. Новой будет считаться любая вершина, не содержащаяся в текущем пути, поэтому, добавив к главной цели fail, можно сгенерировать все пути в порядке возрастания их длин.

Первым аргументом процедуры width будет текущий список путей-кандидатов, вторым — окончательный путь-решение. Каждый новый путь становится головой списка путей кандидатов.

width(Ways,Sol), где Ways — список путей, Sol — решение.

Граничное условие рекурсии

width([[Z|Was]|T],[Z|Was]):-

end(Z).

[ Z|Was ] — путь-решение, который окончился целевой вершиной Z.

width([[X|Was]|T],Sol):-

findall(Way,continue(X,Was,Way),LC),

conc(T,LC,T1),!,

width(T1,Sol).

Findall собирает в список LC все продолжения пути [ X | Was ] на один шаг, и ширина вызывается с новым списком путей T 1.

Продолжение пути на один шаг производится в процедуре continue.

continue(X,T,[Y,X|T]):-

go(X,Y),

not(member(Y,T)).

Если вершина X тупиковая, то findall вернет список LC= []. Путь [ X | Was ] будет удален из списка путей-кандидатов и произойдет вызов width с T 1= T.

Если все пути-кандидаты тупиковые и не содержат целевых вершин, то width будет вызвана с пустым списком и вернет неудачу. Так как отсечение блокирует возвраты, то неудачу вернет и самый первый вызов width из solve.

Дата добавления: 2015-06-27