Breadth First Search
Here is simple code for breadth first search. It is taken from the book
of Ivan Bratko.
% Solution is an acyclic path (in reverse order)
% from Start to a goal
solve(Start, Solution) :-
breadthfirst( [[Start]], Solution).
% breadthfirst(+[Paths], -Solution).
% Paths is the list of paths being explored
% Node is it.
breadthfirst([ [Node|Path]| _OtherPaths], [Node|Path]) :-
goal(Node). % you have to write goal(+Node).
breadthfirst([Path |Paths], Solution) :-
append(Paths, newpaths, Paths1),
extend([Node|Path], NewPaths) :-
bagof( [NewNode, Node, |Path],
(successor(Node, NewNode), not member(NewNode, [Node|Path])),
For more details on (\+)/2. This is a form of " not ".
It must be used with care.
For details on the cut (!/0)
For details on bagof/3.
Note in particular that bagof fails when the goal has no solutions.
On the other hand findall/3 does not.
Last Changed: 1999/10/07