% a simple greedy best first search.  A state's successors are
% generated, sorted by their heuristic funtion and then tried
% (redursively) from best to worst.

% works in SWI-Prolog.  
% Written by Tim Finin, http://umbc.edu/~finin/, finin@Umbc.edu

:- ensure_loaded(showPath).

go :- bestfs.

betfs :- 
  bestfs(Path), 
  showPath(Path).

% bestfs(-): find a start sate and then a path to a goal state.

bestfs(Path) :- 
  start(S), 
  bfs(S,ReversedPath),
  reverse(ReversedPath,Path).

% success if we've found a goal.

bestfs(S,[S]) :- goal(S), !.


% otherwise, find successors and their heuristic score, sort and then
% try them from best to worst.  If a solution is found, prepend S to the
% it's path and return.

bestfs(S,[S|Path]) :-
  findall(HSS-SS,
          (arc(S,SS), h(SS,HSS)),
          L),
  keysort(L,SortedL),
  member(_-NextS,SortedL),
  bestfs(NextS,Path).