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

Program source code: depth-first_search.pl

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).

Comments

pl/prolog/pllib/depth-first_search.txt · ostatnio zmienione: 2017/07/17 08:08 (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