@@ Linia 1: / Linia 1: @@
+====== Depth-first search ======
+{{tag>searching}}
+===== 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 =====
+Program source code: {{depth-first_search.pl}}
+===== Listing =====
+<code prolog>
+% 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).
+</code>
+===== Comments =====

pl/prolog/pllib/depth-first_search.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)

AIwiki

Menu