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