Depth-first search
Description
A depth-first search program that avoids cycling.
Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
Download
Listing
% Figure 11.7 A depth-first search program that avoids cycling.
:- 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( Node, Solution):
% Solution is an acyclic path (in reverse order) between Node and a goal
solve( Node, Solution) :-
depthfirst( [], Node, Solution).
% depthfirst( Path, Node, Solution):
% extending the path [Node | Path] to a goal gives Solution
depthfirst( Path, Node, [Node | Path] ) :-
goal( Node).
depthfirst( Path, Node, Sol) :-
s( Node, Node1),
not member( Node1, Path), % Prevent a cycle
depthfirst( [Node | Path], Node1, Sol).