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

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

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

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

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 theirf-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 tof-values insert(T,Ts,[T|Ts]) :- f(T,F), bestf(Ts,F1), F =< F1, !. insert(T,[T1|Ts],[T1,Ts1]) :- insert(T,Ts,Ts1). % extractf-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.