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

Program source code: depth-first_search_2.pl

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.

Comments

pl/prolog/pllib/depth-first_search_2.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0