A heuristic search algorithm with modifiable estimate

摘要

This paper describes an improved version of two previously published algorithms in the area: A∗ and B. The new approach is based on considering the estimate ĥ(n) on node n as a variable rather than as a constant. The new algorithm thus improves the estimate as it goes on, avoiding some useless node expansions. It is proved to never expand more nodes than B or A∗ and to expand a much smaller number of them in some cases.Another result of the paper is a proof that no overall optimal algorithm exists if the cost of an algorithm is measured by the total number of node expansions.