Множества начальных вершин, прямой и обратный поиск

Пусть начальное состояние не единственное. При поиске в глубину будем последовательно вызывать процедуру из каждого начального состояния:

solve([H|T]):-

depth(H,Sol).

solve([_|T]):-

solve(T).

При поиске в ширину образуем из начальных вершин начальные пути и соберем их в список: L0 — список начальных вершин, W0 — список начальных путей.

solve(L0):-

findall(Was,make_way(X,L0,Way),W0),

width(W0,Sol).

make_way(X,L0,[X]):-

member(X,L0).

Если начальных состояний довольно много, а конечное одно, удобно производить поиск обратный поиск — от конечного к начальному. Если ходы в пространстве не обратимы, то вместо процедуры go может потребоваться обратная процедура go 1. Кроме того, поиск в ширину можно сделать двунаправленным — для просмотра меньшей области пространства.

Рисунок 3. Обратный и двунаправленный поиск в ширину

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

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