Breadth-first search

Description

An implementation of breadth-first search.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Download

Program source code: breadth-first_search.pl

Listing

% Figure 11.10   An implementation of breadth-first search.
 
:- 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( Start, Solution):
%    Solution is a path (in reverse order) from Start to a goal
 
solve( Start, Solution)  :-
  breadthfirst( [ [Start] ], Solution).
 
% breadthfirst( [ Path1, Path2, ...], Solution):
%   Solution is an extension to a goal of one of paths
 
breadthfirst( [ [Node | Path] | _], [Node | Path])  :-
  goal( Node).
 
breadthfirst( [Path | Paths], Solution)  :-
  extend( Path, NewPaths),
  conc( Paths, NewPaths, Paths1),
  breadthfirst( Paths1, Solution).
 
extend( [Node | Path], NewPaths)  :-
  bagof( [NewNode, Node | Path],
         ( s( Node, NewNode), not member( NewNode, [Node | Path] ) ),
         NewPaths),
  !.
 
extend( Path, [] ).              % bagof failed: Node has no successor

Comments

pl/prolog/pllib/breadth-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