PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Martelli A. On the complexity of admissible search algorithms. In: Artificial Intelligence, (8) pp. 1 - 13. North-Holland Publishing Company, 1976.
 
 
Abstract
(English)
This paper analyzes the complexity of heuristic search algorithms, i.e algorithms which find the shortest path in a graph by using and 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(Nē) steps in the worst case and which never requires more steps than A*.
Subject


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional