Поиск в ширину

Goal

Clauses

Predicates

Domains

s=symbol

l= s*

r= real

ap (l, l, l)

eq (l, l)

udob (l, l, l)

preemn (s, l)

gs(s)

solve (l, l, l, r, r)

sol

sol:-solve ([s], [], P,0,H), write (“sol =”,P),nl.

solve ([X|L1], M, P,Y,H):- gs (X), P= [X|M].

solve ([X|N], M, P,Y,H):- M1= [X|M], Y1= Y+1, Y1< H, preemn (X, L),

udob (L1, L, L2), udob (M1, L2, L3), ap(L3, L1,L4), solve (L4,M1, P1), P=P1.

solve ([X|N], M, P,Y,H):- N=[X1|N1], M1= [X1|M] , preemn (X1, 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

Параметр Н в этой программе представляет предельную глубину поиска.

В стратегии поиска в ширину исследуются в первую очередь те вершины, которые являются ближайшими к на­чальной вершине, см. рис. 5.11.

т

Рис.5.11. Схема поиска в ширину

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