Пример 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 */

Дата добавления: 2014-01-07