Evrpoisk(Start,Solve):-

max_f(Fmax), % Fmax > любой f-оценки

propag([],l(Start,0/0),Fmax,_,yes,Solve).

propag(P,l(B,_),_,_,yes,[B|P]):-

goal(B). % рассматриваемый лист – цель поиска.

Propag(P,l(B,F/G),Extr,Tree1,Is_solv,Solve):-

F=<Extr, % получение дерева из приемников листа

Bagof(B1/C,(after(B,B1,C),not(member(B1,P))),Successers),

!,suc_list(G,Successers,TT),

Opt_f(TT,F1),

Propag(P,tr(B,F1/G,TT),Extr,Tree1,Is_solv,Solve).

Propag(P,l(B,F/G),Extr,Tree1,never,Solve):-

F=<Extr. % Нет приемников – тупик

propag(P,tr(B,F/G,[T|TT]),Extr,Tree1,Is_solv,Solve):-

F=<Extr, % Продолжить дерево

Opt_f(TT,OF),

Min(Extr,OF,Extr1),

propag([B|P],T,Extr1,T1,Is_solv1,Solve),

continue(P,tr(B,F/G,[T1,TT]),Extr,Tree1,Is_solv1,Is_solv,Solve).

propag(_,tr(_,_,[]),_,_,never,_):-!. % Тупиковое дерево - нет решений

Propag(_,Tree,Extr,Tree,no,_):-

f(Tree,F),F>Extr. % Рост остановлен

Continue(_,_,_,_,yes,yes,Solve).

continue(P,tr(B,F/G,[T1,TT]),Extr,Tree1,no,Is_solv,Solve):-

Insert(T1,TT,NTT),

Opt_f(NTT,F1),

Propag(P,tr(B,F1/G,NTT),Extr,Tree1,Is_solv,Solve).

continue(P,tr(B,F/G,[T1,TT]),Extr,Tree1,never,Is_solv,Solve):-

Opt_f(TT,F1),

Propag(P,tr(B,F1/G,TT),Extr,Tree1,Is_solv,Solve).

suc_list(_,[],[]).

suc_list(G0,[B/C|BB],TT):-

G is G0+C,

h(B,H), % Эвристика h(B)

F is G+H,

Suc_list(G0,BB,TT1),

Insert(l(B,F/G),TT1,TT).

/**************************************************

*Вставка дерева Т в список деревьев ТТ с сохранением *

* упорядоченности по f-оценкам *

***************************************************/

insert(T,TT,[T|TT]):-

F(T,F),

Opt_f(TT,F1),

F=<F1,!.

insert(T,[T1|TT],[T1|TT1]):-

Insert(T,TT,TT1).

/******Проверка принадлежности элемента списку******/

member(X,[X|Q]).

member(X,[H|Q]):-member(X,Q).

/******* Получение f-оценки *********/

f(l(_,F/_),F). % f-оценка листа

f(tr(_,F/_,_),F). % f-оценка дерева

opt_f([T|_],F):- % наилучшая f-оценка для

f(T,F). % списка деревьев

opt_f([],Fmax):- % нет деревьев:

max_f(Fmax). % плохая f-оценка

Min(X,Y,X):-

X=<Y,!.

Min(X,Y,Y).

/**********************************************************

* База фактов тестового примера: *

* состояние дуг исходного графа after; *

* функция h оценки удаленности вершин от целевой вершины;*

* целевая вершина – goal; *

* максимальное значение max_f(Fmax) оценки функции f *

**********************************************************/

after(s,a,2). % База фактов:

after(s,e,2). % Исходный граф

After(a,b,2).

After(b,c,2).

After(c,d,3).

After(e,f,5).

After(f,g,2).

After(d,t,3).

After(g,t,2).

after(b,v,1). %Тупиковая вершина

goal(t). % Целевая вершина

h(a,5). % Значение эвристической

h(e,7). % функции h для оценки вершин

H(b,4).

H(f,4).

H(t,0).

H(d,3).

H(g,2).

H(c,4).

H(v,1).

max_f(20). % Макимальное значение f-оценки

% Пример запроса к программе

%?-evripoisk(s,Path).

Path=[t,g,f,e,s] ->;

Path=[t,d,c,b,a,s] ->;

False

ЗАДАНИЕ 3.1

Проследите трассировку для указанных в данном разделе программ.

ЗАДАНИЕ 3.2

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

4.ПРОСТРАНСТВО СОСТОЯНИЙ.

ЦЕЛЬ. Знакомство с одной общей схемой для представления задач, называемой пространством состояний.