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

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

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

Рассмотрим поиск в ширину на модельном графе (рис. 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] на один шаг, и ширина вызывается с новым списком путей T1.

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

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

go(X,Y),

not(member(Y,T)).

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

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