Complexity Analysis of Admissible Heuristic Search

Proceedings of the National Conference on Artificial Intelligence (AAAI-98), Madison, WI, July, 1998, pp. 305-310.

[AAAI-98]

.ps (204k) .ps.gz (50k) .pdf (139k)

We analyze the computational complexity of "Admissible Heuristic Search", under some reasonable hypotheses. An expanded version of our analysis appears in the paper Time Complexity of Iterative-Deepening-A*.