Abstract
We present a comparison of three well known heuristic search algorithms: best-first search (BFS), iterative-deepening (ID), and depth-first branch-and-bound (DFBB). We develop a model to analyze the time and space complexity of these three algorithms in terms of the heuristic branching factor and solution density. Our analysis identifies the types of problems on which each of the search algorithms performs better than the other two. These analytical results are validated through experiments on different problems. We also present a new algorithm, DFS, which is a hybrid of iterative deepening and depth-first branch-and-bound, and show that it outperforms the other three algorithms on some problems.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991 |
| Publisher | AAAI press |
| Pages | 434-440 |
| Number of pages | 7 |
| ISBN (Electronic) | 0262510596, 9780262510592 |
| State | Published - 1991 |
| Event | 9th National Conference on Artificial Intelligence, AAAI 1991 - Anaheim, United States Duration: Jul 14 1991 → Jul 19 1991 |
Publication series
| Name | Proceedings of the 9th National Conference on Artificial Intelligence, AAAI 1991 |
|---|---|
| Volume | 1 |
Conference
| Conference | 9th National Conference on Artificial Intelligence, AAAI 1991 |
|---|---|
| Country/Territory | United States |
| City | Anaheim |
| Period | 7/14/91 → 7/19/91 |
Bibliographical note
Funding Information:*This research was supported by Army Research Office grant # 28408-MA-SD1 to the University of Minnesota and by the Army High Performance Computing Research Center at the University of Minnesota. +This research was supported by an NSF Presidential Young Investigator Award, and a grant from Rockwell International.
Publisher Copyright:
Copyright © 1991, AAAI (www.aaai.org). All rights reserved.