A Formal Basis for the Heuristic Determination of Minimum Cost Paths

Inside the paper

The problem

Finding a least-cost route through a large graph can require exploring many alternatives. A useful estimate of the remaining cost can guide that search, but the estimate must be handled carefully if the result is to remain optimal.

The idea

The paper studies a search that ranks frontier nodes by the cost already incurred plus an estimate of the remaining cost. It states conditions under which this procedure finds a minimum-cost path and compares its search effort with alternatives.

How it works

• Begin at the starting node and keep track of discovered nodes whose outgoing paths have yet to be examined.
• Select a node with the smallest estimated total route cost, then generate its successors and update their best known paths.
• If a better route to a previously encountered node appears, revise its path information and return it to consideration when needed.
• An estimate that does not exceed the true remaining cost supports the admissibility result under the paper’s assumptions.

What it showed

The authors prove that the stated search returns a minimum-cost solution under its conditions. They also analyze when another admissible algorithm with the same heuristic information cannot expand fewer nodes, with qualifications involving ties and consistency.

Read it for

Start with Section II for the algorithm and its admissibility argument. Section III develops the more subtle optimality comparison, while Section IV discusses the assumptions and practical implications; the proofs can be revisited after tracing a small graph by hand.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.