% best first search  algorithm for trees
% using function f(n) = g(n) + h(n) where h is heuristic function

% suppose tree arcs represented as arc(Nd1,Nd2)

% goal(N) true if N is goal

% store f values plus paths in first argument
% return value when goal npode found

best_first_search(Start,Sol) :-
   bfs([0-[Start]],Sol).

bfs([_-[Node|Path]| _],[Node|Path]) :-
     goal(Node).

bfs([_-[Node|Path]|RstOpen],Sol) :-
    findall(Val1-[Next,Node|Path],(arc(Node,Next),f([Next,Node|Path],Val1)),New),
    append(New,RstOpen,TmpOpen),
    move_smallest(TmpOpen,NewOpen),
    bfs(NewOpen,Sol).

% move path with smallest f value to the front

move_smallest([],[]).
move_smallest([Val-L|Ls],[S|R]) :-
   find_smallest(Ls,Val-L,S,R).

find_smallest([],T,T,[]).
find_smallest([V1-L|Ls],V-T,S,[V-T|R]) :-
     V1 < V,!,find_smallest(Ls,V1-L,S,R).
find_smallest([V1-L|Ls],V-T,S,[V1-L|R]) :-
     find_smallest(Ls,V-T,S,R).

% example tree

arc(1,2).
arc(1,3).
arc(2,4).
arc(2,5).
arc(3,6).
arc(3,7).
arc(5,8).
arc(6,9).

% goals to be found

goal(9).
goal(8).

% specified heuristic function

h(1,2).
h(2,2).
h(3,2).
h(4,2).
h(5,2).
h(6,10).
h(7,2).
h(8,2).
h(9,2).

% computing f-function

f([X|Xs],N) :-
   length(Xs,L),
   h(X,H),
   N is L+1+H.

/* test with

best_first_search(1,Sol)

*/