Стратегия поиска в ширину

В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует рис. 1.2.

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

если голова первого пути – это целевая вершина, то взять путь в качестве решения, иначе

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

В случае примера рис. 1.2 этот процесс будет развиваться следующим образом:

Начинаем с начального множества кандидатов:

[ [a] ]

Порождаем продолжение пути [a]:

[ [b, a], [c, a] ]

Удаляем первый путь из множества кандидатов и порождаем его продолжения:

[ [d,b,a], [e,b,a] ]

Добавляем список продолжений в конец списка кандидатов:

[ [c,a], [d,b,a], [e,c,a] ]

Удалим [c,a], а затем добавляем все его продолжения в конец множества кандидатов:

[ [d,b,a], [e,b,a], [f,c,a], [g,c,a] ]

После того, как пути [d,b,a] и [e,b,a] будут продолжены, измененный список кандидатов примет вид

[ [f,c,a], [g,c,a], [h,d,b,a], [i,e,b,a], [j,e,b,a] ]

В этот момент обнаруживается путь [f,c,a], содержащий целевую вершину f. Этот путь выдается в качестве решения.

Рассмотрим текст программы поиска в ширину.

after – состояние дуг исходного графа

but – целевые вершины.

conc([],L,L).

conc([X|L1],L2,[X|L3]):-conc(L1,L2,L3).

member(X,[X|Q]).

member(X,[H|Q]):-member(X,Q).