Пример 5.3.3.
Goal
Clauses
Predicates
Domains
Пример 5.3.2.
Поиск в глубину и итеративное углубление
Goal
Clauses
Predicates
Domains
Пример 5.3.1
/*Программа: поиск с возвратами */
s=symbol
l= s*
ap (l, l, l)
eq (l, l)
udob (l, l, l)
preemn (s, l)
gs(s)
solve (l, l, l, l)
sol
sol:-solve ([s], [], [], P), write (“sol =”,P),nl.
solve ([X|N], C, T, P):- C1= [X|C], gs(X), P= C1.
solve ([X|N], C, T, P):- C1= [X|C], preemn (X, L), udob (C1, L, L1),
udob (N, L1, L2), udob (T, L2, L3), eq(L3, []),udob ([X], C1,C2),
udob ([X], N,N1), T1= T, solve (N1,C2,T1,P1), P=P1.
solve ([X|N], C, T, P):- C1= [X|C], preemn (X, L), udob (C1, L, L1),
udob (N, L1, L2), udob (T, L2, L3), ap(L3, [X|N], N1),
T1=T, solve (N1,C1,T1,P1), P=P1.
solve ([],C,T,P):- P= resh.net, write(P),nl.
sol
Глубину вершины в корневом графе определим рекурсивно: глубина корня дерева равна нулю.
Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует.
Таким образом, вершиной, имеющей наибольшую глубину в дереве перебора, в данный момент служит та, которая должна в этот момент быть раскрыта. Стратегия поиска в глубину использует два списка вершин: отк (открыт- соответствует списку N в стратегии поиска с возвратами, реализован как стек) зак (закрыт- соответствует объединению списков C и Tв стратегии поиска с возвратами) и определяется следующей последовательностью шагов:
1.Поместить начальную вершину в список, называемый отк.
2.Если список отк пуст, то на выход дается сигнал
о неудаче поиска, в противном случае перейти к шагу (3).
3.Взять первую вершину из списка отк и перенести
ее в список, называемый зак. Эту вершину назвать п.
4.Раскрыть вершину п, построив все непосредственно сле
дующие за ней вершины. Поместить их (в произвольном по
рядке) в начало списка отк и построить указатели, иду
щие от них к вершине п.
5.Если одна из этих вершин целевая, то на выход выдать
решение, просматривая для этого соответствующие указатели,
в противном случае переходить к шагу 2. Соответствующая программа имеет вид.
/*Программа: поиск в глубину*/
s=symbol
l= s*
ap (l, l, l)
eq (l, l)
udob (l, l, l)
preemn (s, l)
gs(s)
solve (l, l, l) /*Первый аргумент- список отк, второй- зак*/
sol
sol:-solve ([s], [], P), write (“sol =”,P),nl.
solve ([X|L1], M, P):- gs(X), P= [X|M].
solve ([X|N], M, P):- M1= [X|M], preemn (X, L), udob (L1, L, L2),
udob (M1, L2, L3), ap(L3, L1,L4), solve (L4,M1, P1), P=P1.
solve ([],M ,P):- P= resh.net, write(P),nl.
sol
Если пространство состояний задачи является корневым деревом, то программа может быть упрощена, с учетом следующего. Чтобы найти путь решения Sol от заданной вершины S до некоторой целевой вершины, необходимо реализовать в программе следующие операции:
■ если S— целевая вершина, то Sol = [S];
■ иначе, если существует вершина- преемник V1 вершины V, такая, что имеется путь S1
от вершины V1 до целевой, то Sol = [V I S1].
Эта формулировка представляется следующей программой.
/*Программа поиск в глубину 1*/