Summary: This paper describes an improved version of two previously published algorithms in the area: $A\sp*$ 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\sp*$ 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.