A best-first search program that only requires space linear in the depth of search (RBFS algorithm).

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: rbfs_algorithm.pl

% Figure 12.13  A best-first search program that only requires 
% space linear in the depth of search (RBFS algorithm). 
 
:- op( 900, fy, not).
 
% not Goal): negation as failure; 
%   Note: This is often available as a built-in predicate,
%   often written as prefix operator "\+", e.g. \+ likes(mary,snakes)
 
not Goal  :-
  Goal, !, fail
  ; 
  true.
 
% Linear-space best-first search; the RBFS algorithm 
% The program assumes 99999 is greater than any f-value
 
% bestfirst( Start, Solution): Solution is a path from Start to a goal
 
bestfirst( Start, Solution) :-
  rbfs( [], [ (Start, 0/0/0) ], 99999, _, yes, Solution).
 
% rbfs( Path, SiblingNodes, Bound, NewBestFF, Solved, Solution):
%   Path = path so far in reverse order
%   SiblingNodes = children of head of Path
%   Bound = upper bound on F-value for search from SiblingNodes
%   NewBestFF = best f-value after searching just beyond Bound
%   Solved = yes, no, or never 
%   Solution = solution path if Solve = yes
%
%   Representation of nodes: Node = ( State, G/F/FF)
%   where G is cost till State, F is static f-value of State, 
%   FF is backed-up value of State
 
rbfs( Path, [ (Node, G/F/FF) | Nodes], Bound, FF, no, _)  :-
  FF > Bound, !.
 
rbfs( Path, [ (Node, G/F/FF) | _], _, _, yes, [Node | Path])  :-
  F = FF,     % Only report solution once, when first reached; then F=FF
  goal( Node).
 
rbfs( _, [], _, _, never, _)  :- !.   % No candidates, dead end!
 
rbfs( Path, [ (Node, G/F/FF) | Ns], Bound, NewFF, Solved, Sol)  :-
  FF =< Bound,                    % Within Bound: generate children
  findall( Child/Cost, 
           ( s( Node, Child, Cost), not member( Child, Path)),
           Children),
  inherit( F, FF, InheritedFF),   % Children may inherit FF
  succlist( G, InheritedFF, Children, SuccNodes),  % Order children
  bestff( Ns, NextBestFF),        % Closest competitor FF among siblings
  min( Bound, NextBestFF, Bound2), !,
  rbfs( [Node | Path], SuccNodes, Bound2, NewFF2, Solved2, Sol),
  continue(Path, [(Node,G/F/NewFF2)|Ns], Bound, NewFF, Solved2, Solved, Sol).
 
% continue( Path, Nodes, Bound, NewFF, ChildSolved, Solved, Solution)
 
continue( Path, [N | Ns], Bound, NewFF, never, Solved, Sol)  :- !,
  rbfs( Path, Ns, Bound, NewFF, Solved, Sol).    % Node N a dead end
 
continue( _, _, _, _, yes, yes, Sol).
 
continue( Path, [ N | Ns], Bound, NewFF, no, Solved, Sol)  :-
  insert( N, Ns, NewNs), !,      % Ensure siblings are ordered by values
  rbfs( Path, NewNs, Bound, NewFF, Solved, Sol).
 
succlist( _, _, [], []).
 
succlist( G0, InheritedFF, [Node/C | NCs], Nodes) :-
  G is G0 + C,
  h( Node, H),
  F is G + H,
  max( F, InheritedFF, FF),
  succlist( G0, InheritedFF, NCs, Nodes2),
  insert( (Node, G/F/FF), Nodes2, Nodes).
 
inherit( F, FF, FF)  :-    % Child inherits father's FF if 
  FF > F, !.               % father's FF greater than father's F
 
inherit( F, FF, 0).
 
insert( (N, G/F/FF), Nodes, [ (N, G/F/FF) | Nodes]) :-
  bestff( Nodes, FF2),
  FF =< FF2, !.
 
insert( N, [N1 | Ns], [N1 | Ns1])  :-
  insert( N, Ns, Ns1).
 
bestff( [ (N, F/G/FF) | Ns], FF).   % First node - best FF
 
bestff( [], 99999).      % No nodes - FF = "infinite"