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

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

in_width(Paths,Solution)

истинна только тогда, когда в множестве Paths существует такой путь,который может быть продолжен вплоть до целевой вершины.

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

[[StartNode]].

Чтобы выполнить поиск в ширину при заданном множестве путей-кандидатов, нужно:

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

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

Пример 3. Решение задачи манипулирования кубиками методом поиска в ширину.

tgoal([[a,b,c],[],[]]). tgoal([[],[a,b,c],[]]). tgoal([[],[],[a,b,c]]).

after(Stolbs,[Stolb1,[Up1|Stolb2]|Rest]):-

delete([Up1|Stolb1],Stolbs,Stolbs1), delete(Stolb2,Stolbs1,Rest).

delete(X,[X|L],L).

delete(X,[Y|L],[Y|L1]):- delete(X,L,L1).

member(X,[X|_]).

member(X,[_|Tail]):- member(X,Tail).

conc([],L,L).

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

solve(Start,Solution):- in_width([[Start]],Solution).

in_width([[Node|Path]|_],[Node|Path]):- tgoal(Node).

in_width([[B|Path]|Paths],Solution):- findall(S, new_node(B,S,Path), NewPaths),

% NewPaths - ациклические продолжения пути [B|Path]

conc(Paths,NewPaths,Paths1),!, in_width(Paths1,Solution);

in_width(Paths,Solution). % случай, когда у B нет преемника

new_node(B,S,Path):- after(B,B1), not(member(B1,[B|Path])), S=[B1,B|Path].

write_list([X|Rest]):-write("\n",X),readchar(_), write_list(Rest).

write_list([]).

?- solve([[c,a,b],[],[]],Solution), write_list(Solution).

Содержание работы

1. Выполнить рассмотренные примеры.

2. Составить программу, которая решает задачу соответствующего варианта.

3. Подобрать тестовые данные, проверяющие работу программы.

4. Составить отчет о проделанной работе.