Depth-First Versus Best-First Search

We present a comparison of three well known heuristic _ search algorithms: best-first search (BFS), iterativedeepening (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.

Authors

• Nageshwara Rao Vempaty

Keywords

No keywords are indexed for this paper.