Methods of Search

Methods of Search

References: Depth-first search Bratko section 11.2

Breadth-first search Bratko section 11.3

Best-first search Bratko edtion 3, chapter 12

In the missionaries and cannibals example, the state space is explored in an order determined by Prolog. In some situations, it might be necessary to alter that order of search in order to make search more efficient. To see what this might mean, here are two alternative methods of searching a tree.

Depth first search begins by diving down as quickly as possible to the leaf nodes of the tree (or graph). Traversal can be done by:

visiting the node first, then its children (pre-order traversal):a b d h e i j c f k g
visiting the children first, then the node (post-order traversal):h d i j e b k f g c a
visiting some of the children, then the node, then the other children (in-order traversal)h d b i e j a f k c g

Breadth-first search traverses the tree or graph level-by-level, visiting the nodes of the tree above in the order a b c d e f g h i j k.

Implementing Depth-First Search

Hereafter, assume that we have a graph, represented using the edge predicate, and that a node N is a goal node if goal(N) is true.

solve(Node, Solution) :-
  depthfirst([], Node, Solution).

% depthfirst(Path, Node, Solution).
depthfirst(Path, Node, [Node|Path]) :-
  goal(Node).
depthfirst(Path, Node, Sol) :-
  edge(Node, Node1),
  not(member(Node1, Path)),
  depthfirst([Node|Path], Node1, Sol).

: edge(1, 2).         %        1
: edge(1, 3).         %       / \ 
: edge(2, 4).         %      2   3
: edge(3,5).          %      |   |
: edge(5,6).          %      4   5
: goal(6).            %          |
: solve(1, Soln)?     %          6 <- goal
Soln = [6, 5, 3, 1]

Implementing Breadth-First Search

% 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 the paths.

breadthfirst([[Node|Path]|_], [Node|Path]) :-
  goal(Node).
  % Always first check if goal reached

% If not, then extend this path by all
% possible edges, put these new paths on the
% end of the queue (Paths1) to check, and do
% breadthfirst on this new collection of
% paths, Paths1:
breadthfirst([Path|Paths], Solution) :-
  extend(Path, NewPaths),
  conc(Paths, NewPaths, Paths1),
  breadthfirst(Paths1, Solution).

% extend([N|Rest], NewPaths).
% Extend the path [N|Rest] using all edges
% through N that are not already on the path.
% This produces a list NewPaths.
extend([Node|Path], NewPaths) :-
  findall([NewNode, Node|Path],
          (edge(Node, NewNode),
           not(member(NewNode,[Node|Path]))),
          NewPaths),
  !.
extend(Path,[]). %findall failed: no edge

edge(1, 2). edge(1, 3). edge(2, 4).
edge(3, 5). edge(5, 6).
goal(3).

Best-first search (A* algorithm).

In some situations, we have partial knowledge of the structure of the search space that can be applied to guide search.

We can inspect all the currently-available transitions, and rank them on the basis of our partial knowledge. Here high rank means that the transition looks promising in relation to the goal.

We'll describe the best-first algorithm in terms of a specific example involving distances by straight line and by road from a start point s to a goal point t:

Let us define, for any node N, g(N) to be the distance travelled from the start node s to reach N. Note that this is a known quantity by the time you reach N, but that in general it could vary depending on the route taken through state space from s to N.

In our example scenario, we don't know the distance by road from N to t, but we do know the straightline distance. Let us call this distance h(N). As our heuristic to guide best-first search, we use f(N) = g(N) + h(N). That is, we will search first from the node that we have found so far that has the lowest f(N).

Let's see how this will work in hand-simulation:

To understand the code for bestfirst, we need to know about some representations used by the program:

edge(N1, N2, Cost) signifies an edge between vertices N1 and N2 with cost (or distance) Cost.

h(N, H) signifies that the h value of node N is H (i.e. h(N) = H).

lf(N, F/G) represents a single node tree - a leaf - N is a node in the state space, G is g(N), and F is f(N) = G + h(N).

t(N, F/G, Subs) represents a tree with non-empty subtrees - Subs is a list of the subtrees, and F is the updated f-value of N, that is the f-value of the most promising successor of N. Subs is ordered according to increasing f-values of the subtrees.

Thus at the moment that the node s has been expanded, the search tree looks like this: t(s, 7/0, [lf(a,7/2), lf(e,9/2)]).

The key procedure in bestfirst search is expand:

expand(P, Tree, Bound, Tree1, Solved, Solution).

This expands the current (sub)tree as long as the f-value <= Bound.

P Path between start node and Tree.

Tree Current search (sub)tree.

Bound f-limit for expansion of Tree.

Tree1 Tree expanded within Bound; consequently, the f-value of Tree1 is > Bound (unless a goal node has been found during the expansion).

Solved Indicator whose value is yes, no or never.

Solution A solution path from the start node through Tree1 to a goal node within Bound (if such a goal node exists).

The code below is from p265-6 of the 3rd edition of Ivan Bratko's book "Prolog Programming for Artificial Intelligence", Addison-Wesley 2001. (However, I changed the functor for the 2-place terms l(Start, 0/0) and other instances of this kind of term to lf(Start, 0/0) because it may be difficult to distinguish between l ("el") and 1 ("one") in some fonts.)

It has been reported to me that the code contains errors. It is not clear whether these errors arise from my transcription of the code to this web format, or whether they are present in the original code in the book. This web page was developed for teaching purposes at UNSW. Since I haven't taught this course for several years, I don't plan to debug the code any time soon. However, it seems appropriate to warn you that the code is buggy. It might help to check out what Bratko has to say. It may be difficult to get hold of the 3rd edition these days: the 4th edition was published in 2012, and the code appears on pp285-6 of the 4th edition.

bestfirst(Start, Solution) :-
  expand([], l(Start, 0/0), 9999, _, yes, Solution).
   % Assume 9999 is > any f-value.
% Case 1: goal leaf-node, construct a solution path:
expand(P, lf(N,_),_,_,yes,[N|P]) :- goal(N).

% Case 2: leaf-node, f-value less than Bound
% Generate successors and expand them within Bound
expand(P, lf(N, F/G), Bound, Tree1, Solved, Sol) :-
  F =< Bound,
  (findall(M/C, (edge(N,M,C), not(member(M,P))), Succ),
   !,                      % Node N has successors
   succlist(G, Succ, Ts),  % Make subtrees Ts
   bestf(Ts, F1),          % f-value of best successor
   expand(P, t(N,F1/G, Ts), Bound, Tree1, Solved, Sol)
   ;
   Solved = never          % N has no successors - dead end
  ).

% Case 3: non-leaf, f-value < Bound
% Expand the most promising subtree; depending on results,
% procedure continue will decide how to proceed
expand(P, t(N,F/G,[T|Ts]), Bound, Tree1, Solved, Sol) :-
  F =< Bound,
  bestf(Ts, BF), min(Bound, BF, Bound1),
  expand([N|P], T, Bound1, T1, Solved1, Sol),
  continue(P, t(N,F/G,[T1|Ts]), Bound, Tree1, Solved1, Solved,
Sol).

% Case 4: non-leaf with empty subtrees
% This is a dead end that will never be solved
expand(_,t(_,_,[]),_,_,never,_) :- !.

% Case 5: value > Bound. Tree may not grow.
expand(_, Tree, Bound, Tree, no, _) :-
  f(Tree, F), F > Bound. % f extracts F value from Tree
% Helper predicates:

% continue(Path, Tree, Bound, NewTree, SubtreeSolved,
%     TreeSolved, Solution).
continue(_,_,_,_,yes,yes,Sol).
continue(P,t(N,F/G,[T1|Ts]),Bound,Tree1,no,Solved,Sol) :-
  insert(T1,Ts,NTs),
  bestf(NTs,F1),
  expand(P,t(N,F1/G,NTs),Bound,Tree1,Solved,Sol).
continue(P,t(N,F/G,Ts,Bound,Tree1,Solved,Sol) :-
  bestf(Ts,F1),
  expand(P,t(N,F1/G,Ts),Bound,Tree1,Solved,Sol).

% succlist(G0,[Node/Cost1,...],[lf(BestNode,BestF/G,...]).
%     Make list of search leaves ordered by their f-values.
succlist(_,[],[]).
succlist(Go,[N/C|NCs],Ts) :-
  G is G-+C,
  h(N,H),
  F is G+H,
  succlist(G0,NCs,Ts1),
  insert(lf(N,F/G),Ts1,Ts).

% insert T into list of trees Ts preserving order with
% respect to f-values
insert(T,Ts,[T|Ts]) :-
  f(T,F), bestf(Ts,F1),
  F =< F1, !.
insert(T,[T1|Ts],[T1,Ts1]) :-
  insert(T,Ts,Ts1).

% extract f-value
f(lf(_,F/_),F).
f(t(_,F/_,_),F).

bestf([T|_],F) :- f(T,F).
bestf([],9999).

Admissibility of A* search

A search algorithm is admissible if it always produces an optimal solution. In our case, this would mean finding an optimal solution as the first solution. For each node n, let h*(n) denote the cost of an optimal path from n to a goal node.

Theorem: An A* algorithm that uses a heuristic function h that satisfies h(n) <= h*(n) for all n in the state space, is admissible.

Summary

We introduced the concepts of states and operators and gave a graph traversal algorithm that can be used as a problem solving tool.

We applied this to solve the "missionaries and cannibals" problem.

We described depth-first search, breadth-first search, and best-first search.

This page was created in July 2001.

References:	Depth-first search	Bratko section 11.2
	Breadth-first search	Bratko section 11.3
	Best-first search	Bratko edtion 3, chapter 12

P	Path between start node and Tree.
Tree	Current search (sub)tree.
Bound	f-limit for expansion of Tree.
Tree1	Tree expanded within Bound; consequently, the f-value of Tree1 is > Bound (unless a goal node has been found during the expansion).
Solved	Indicator whose value is `yes`, `no` or `never`.
Solution	A solution path from the start node through Tree1 to a goal node within Bound (if such a goal node exists).