Depth-first search 2
Description
Depth-first search, This program does not avoid infinite cycling.
Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
Download
Listing
% Figure 13.8: Depth-first search for AND/OR graphs. This program
% does not avoid infinite cycling. Procedure 'solve' finds a solution
% tree, procedure 'show' displayes such a tree. 'show' assumes that
% each node on output only takes 1 characetr.
% Depth-first AND/OR search
% solve( Node, SolutionTree):
% find a solution tree for Node in an AND/OR graph
:- op( 500, xfx, :).
:- op( 600, xfx, ---> ).
solve( Node, Node) :- % Solution tree of goal node is Node itself
goal(Node).
solve( Node, Node ---> Tree) :-
Node ---> or:Nodes, % Node is an OR-node
member( Node1, Nodes), % Select a successor Node1 of Node
solve( Node1, Tree).
solve( Node, Node ---> and:Trees) :-
Node ---> and:Nodes, % Node is an AND-node
solveall( Nodes, Trees). % Solve all Node's successors
% solveall( [Node1,Node2, ...], [SolutionTree1,SolutionTree2, ...])
solveall( [], []).
solveall( [Node|Nodes], [Tree|Trees]) :-
solve( Node, Tree),
solveall( Nodes, Trees).
% Displaying a solution tree
show(Tree) :- % Display solution tree
show(Tree,0), !. % Indented by 0
% show( Tree, H): display solution tree indented by H
show( Node ---> Tree, H) :- !,
write(Node), write(' ---> '),
H1 is H + 7,
show( Tree, H1).
show( and:[T], H) :- !, % Display single AND tree
show(T,H).
show( and:[T|Ts], H) :- !, % Display AND-list of solution trees
show( T, H),
tab(H),
show( and:Ts, H).
show( Node, H) :-
write(Node), nl.