2015-10-22
645
В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину, что иллюстрирует рис. 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).
After(a,b).
After(a,c).
After(b,d).
After(b,e).
After(c,f).
After(c,g).
After(d,h).
After(e,i).
After(e,j).
After(f,k).
Goal(f).
Goal(j).
Solv(Start,Solv):-
large([[Start]],Solv).
large([[N|T]|_],[N|T]):-
Goal(N).
large([[B|T]|TT],Solv):-
bagof([B1,B|T],(after(B,B1),not(member(B1,[B|T]))),NT),
conc(TT,NT,TT1),!,large(TT1,Solv);
Large(TT,Solv).
