AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Common Misconceptions Concerning Heuristic Search
Robert C. Holte

Last modified: 2010-08-25


This paper examines the following statements about heuristic search, which are commonly held to be true:
  • More accurate heuristics result in fewer node expansions by A* and IDA*.
  • A* does fewer node expansions than any other equally informed algorithm that finds optimal solutions.
  •  Any admissible heuristic can be turned into a consistent heuristic by a simple technique called pathmax.
  • In search spaces whose operators all have the same cost A* with the heuristic function h(s)=0 for all states, s, is the same as breadth-first search.
  • Bidirectional A* stops when the forward and backward search frontiers meet.
The paper demonstrates that all these statements are false and provides alternative statements that are true.

Full Text: PDF