Heuristic search in general tree structures
Amitava Bagchi, Anup Kumar Sen · 1986
A search graph has the form of an m-ary tree with bidire:tional arcs of unit cost.In general there are a number of solution paths of different lengths.The shortest solution path has length N. It is assumed that the heuristic estimates of all nongoal nodes, after being appropriately normallzed~ are independent and identically distributed random variables.Under what conditions is the expected number of node expansions polynomial in N ?Earlier efforts at answering this question have considered only special cases.Here an attempt is made to develop general methods of analysis, using the notion of the discrimlnant of a search graph as the starting point.It is hoped that this general approach will encourage similar studies on search graphs other than trees.Section I -Introduction A worst-case analysis of a heuristic search algorithm gives at best only an imperfect picture about its performance characteristics.Unfortunately~ an average case analysis is far more difficult to achieve.The major problem lies in deciding how exactly the averaging is to be done.No completely satisfactory method is currently known.One way out is to take a graph of simple structure which is representative in some sense, and then see how a search algorithm llke A* fares when run on it.This has been done by Huyn, Dechter and Pearl ~4G, and by Pearl C6G.Their graph is an m-ary tree, with bidirectional arcs of unit cost and one goal node at a distance N from the root.It is assumed that the heuristic estimates of nongoal nodes, after being appropriately normalized, are independent, identically distributed random variables.The expected number of node expansions made by A* is then computed.In this idealized modbl, no node is expanded more than once by A* t and a minimal cost solution is always obtained.Detailed proofs can be found in Pearl DTJ.