Breadth-first search 2
Description
A more efficient program than that of szukanie_wszerz for the breadth-first search The improvement is based on using the difference-pair representation for the list of candidate paths.
Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
Download
Listing
% Figure 11.11 A more efficient program than that of Figure 11.10 for
% the breadth-first search. The improvement is based on using
% the difference-pair representation for the list of candidate paths.
% Procedure extend is as in Figure 11.10.
:- 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.
% solve( Start, Solution):
% Solution is a path (in reverse order) from Start to a goal
solve( Start, Solution) :-
breadthfirst( [ [Start] | Z] - Z, Solution).
breadthfirst( [ [Node | Path] | _] - _, [Node | Path] ) :-
goal( Node).
breadthfirst( [Path | Paths] - Z, Solution) :-
extend( Path, NewPaths),
conc( NewPaths, Z1, Z), % Add NewPaths at end
Paths \== Z1, % Set of candidates not empty
breadthfirst( Paths - Z1, Solution).
extend( [Node | Path], NewPaths) :-
bagof( [NewNode, Node | Path],
( s( Node, NewNode), not member( NewNode, [Node | Path] ) ),
NewPaths),
!.
extend( Path, [] ).