Last update: Dec. 7, 1999

Publications on Heuristic Search :

• Alberto Martelli et al. :
  • On the complexity of admissible search algorithms, 1977.
  • Dynamic programming as graph searching: An algebraic approach, with Stefania Gnesi & Ugo Montanari, 1981.

BibTeX references.

This paper analyzes the complexity of heuristic search algorithms, i.e. algorithms which find the shortest path in a graph by using an estimate to guide the search. In particular, algorithm A*, due to Hart, Nilsson and Raphael, is shown to require O(2N) steps, in the worst case, for searching a graph with N nodes, if the so called ``consistency assumption'' does not hold for the estimate. Furthermore, a new search algorithm is presented which runs in O(N2) steps in the worst case and which never requires more steps than A*.

Page created & maintained by Frederic Leymarie, 1999.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu