On the optimality of A∗

摘要

After discussing difficulties with previous proofs of A∗'s optimality, new proofs are presented. In addition, examples are used to show: (1) that the value of (hn) may be a function of the state of the search as well as the available heuristic information and (2) that there exist admissible search algorithms which can not be simulated by any A∗ algorithm.