A generalization for heuristically-ordered search: algorithms ρ, results about termination and admissibility
Henri Farreny · 2002
We propose a formal generalization for various works dealing with heuristically-ordered search in state graphs. The formalization and the generalization focus on the notion of path length, on the characteristics of the state graphs, on the procedures that control the choices of the states to be expanded, on the rules that govern the update operations, on the properties of the evaluation functions. Consequently, we present the family of algorithms /spl rho/ and the sub-family of algorithms A/spl tilde/, which includes Nilsson's A or A* algorithms and many of their descendants such as HPA, B, A/spl epsiv/*, A/sub /spl epsiv//, C, BF*, B', IDA*, D, A**, and SDW. We present general theorems, about the termination at a goal and the admissibility or sub-admissibility, that widely extend the corresponding results previously published concerning all the above-mentioned algorithms.