Różnice między wybraną wersją a wersją aktualną.
| — |
pl:prolog:pllib:depth-first_search_2 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== Depth-first search 2 ====== | ||
| + | {{tag>trees searching operators}} | ||
| + | ===== 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 ===== | ||
| + | <code prolog> | ||
| + | % 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. | ||
| + | </code> | ||
| + | ===== Comments ===== | ||
