Depth-First Versus Best-First Search

Nageshwara Rao Vempaty, Vipin Kumar, Richard E. Korf

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.