Martelli, A.

On the complexity of admissible search algorithms


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 .