A heuristic search algorithm with modifiable estimate

✍ Scribed by László Mérõ

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 646 KB
• Volume: 23
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(84)90003-1

✦ Synopsis

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 fz(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.