% notational change
% N/C  ---> [N,C]
% from the on in Bratko book  (Figure 12.3)


% some global settings
 
limit(9999).
goal(jyvaskyla).

% the model 

s(helsinki,hanko,127).
s(helsinki,turku,165).
s(helsinki,tampere,173).
s(helsinki,kouvola,136).
s(turku,hanko,141).
s(turku,tampere,153).
s(turku,vaasa,332).
s(tampere,turku,157).
s(tampere,vaasa,244).
s(tampere,jyvaskyla,151).
s(vaasa,jyvaskyla,283).
s(kouvola,jyvaskyla,188).
s(jyvaskyla,vaasa,283).

% a heuristic estimate function
% a non goal city is at least the distance from its
% closest neighbourgh city from the goal city

h(A,0) :-
    goal(A),
    !.

h(A,GLB) :-
    bagof(D,s(A,_,D),Ds),
    !,
    glb(Ds,0,GLB).

h(A,666). % bigger than any distance between too adjacent cities


grlobo([],Glb,Glb-1).
grlobo([H | T],Old,Glb) :-
    H > Old,
    !,
    grlobo(T,H,Glb).
grlobo([H | T],Old,Glb) :-
    grlobo(T,Old,Glb).

glb([],_,222) :- !.    
glb(L,Old,GLB) :-
    grlobo(L,Old,GLB).

distance(_,[],D,D).
distance(C,[H | T],D1,D3) :-
    s(H,C,Dist),
    D2 is D1 + Dist,
    distance(H,T,D2,D3).

distance([H | T],D) :-
    distance(H,T,0,D).

main(P,D) :-
    bestfirst(helsinki,P),
    distance(P,D).

% 23.9.2003, mmeri



%   FIGURE 12.3 from Bratko

%      BEST-FIRST SEARCH

bestfirst( Start, Solution) :-
    limit(Limit),
    expand( [], l( Start, [0,0]),  Limit, _, yes, Solution).
        
%  Assume Limit (use 9999 ) is greater than any f-value

% expand( Path, Tree, Bound, Tree1, Solved, Solution) if
%   Path is path between start node of search and subtree Tree,
%   Tree1 is Tree expanded within Bound,
%   if goal found then Solution is solution path and Solved = yes

%  Case 1: goal leaf-node, construct a solution path

expand( P, l( N, [_,_]), _, _, yes, [N|P])  :-
   goal(N).

%  Case 2: leaf-node, f-value less than Bound
%  Generate successors and expand them within Bound.

expand( P, l( N, [F , G]), Bound, Tree1, Solved, Sol)  :-
   F =<  Bound,
   (  bagof( [M,C], ( s(N,M,C), \+member(M,P) ), Succ), 
      !,                                    % Node N has successors
      succlist( G, Succ, Ts),
      bestf( Ts, F1),
      expand( P, t(N,[F1,G],Ts), Bound, Tree1, Solved, Sol)
      ;
      Solved = never                       % N has no successors - dead end
   ).

%  Case 3: non-leaf, f-value less than Bound
%  Expand the most promising subtree; depending on 
%  results, procedure continue will decide how to proceed.

expand( P, t(N,[F,G],[T|Ts]), Bound, Tree1, Solved, Sol)  :-
   F  =<  Bound,
   bestf( Ts, BF), min( Bound, BF, Bound1),
   expand( [N|P], T, Bound1, T1, Solved1, Sol),
   continue( P, t(N,[F,G],[T1|Ts]), Bound, Tree1, Solved1, Solved, Sol).

%  Case 4: non-leaf with empty subtrees
%  This is a dead end which will never be solved

expand( _, t(_,_,[]), _, _, never, _) :- !.

%  Case 5:  f-value greater than Bound
%  Tree may not grow.

expand( _, Tree, Bound, Tree, no, _)  :-
   f( Tree, F), F > Bound.

% continue( Path, Tree, Bound, NewTree, SubtreeSolved, TreeSolved, Solution)

continue( _, _, _, _, yes, yes, Sol).

continue( P, t(N,[F,G],[T1|Ts]), Bound, Tree1, no, Solved, Sol)  :-
   insert( T1, Ts, NTs),
   bestf( NTs, F1),
   expand( P, t(N,[F1,G],NTs), Bound, Tree1, Solved, Sol).

continue( P, t(N,[F,G],[_|Ts]), Bound, Tree1, never, Solved, Sol)  :-
   bestf( Ts, F1),
   expand( P, t(N,[F1,G],Ts), Bound, Tree1, Solved, Sol).

% succlist( G0, [ [Node1,Cost1], ...], [ l(BestNode,[BestF,G]), ...]):
%   make list of search leaves ordered by their F-values

succlist( _, [], []).

succlist( G0, [[N,C] | NCs], Ts)  :-
   G is G0 + C,
   h( N, H),                             % Heuristic term h(N)
   F is G + H,
   succlist( G0, NCs, Ts1),
   insert( l(N,[F,G]), Ts1, Ts).

% Insert T into list of trees Ts preserving order w.r.t. f-values

insert( T, Ts, [T | Ts])  :-
   f( T, F), bestf( Ts, F1),
   F  =<  F1, !.

insert( T, [T1 | Ts], [T1 | Ts1])  :-
   insert( T, Ts, Ts1).


% Extract f-value

f( l(_,[F,_]), F).        % f-value of a leaf

f( t(_,[F,_],_), F).      % f-value of a tree

bestf( [T|_], F)  :-    % Best f-value of a list of trees
   f( T, F).

bestf( [], L) :-
    limit(L).            % No trees: bad f-value
  
min( X, Y, X)  :-
   X  =<  Y, !.

min( X, Y, Y).

% -------------------------------------------------------------------

% Figure 12.3  A best-first search program.