Martelli A. On the complexity of admissible search algorithms. Internal note IEI-B75-15, 1975. |

Abstract (English) |
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 0(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 0(N)2 steps in the worst case and which never requires more steps than A*. | |

Subject |

1) Download Document PDF |

Open access Restricted Private