Depth-First vs. est-First Search: New Results *

Best-first search (BFS) expands the fewest nodes among all admissible algorithms us-ing the same cost function, but typically re-quires exponential space. Depth-first search needs space only linear in the maximumsearch depth, but expands more nodes than BFS. Us-ing a random tree, we analytically show that the expected number of nodes expanded by depth-first branch-and-bound (DFBnB) is no more than O(d s N), where d is the goal depth and N is the expected number of nodes ex-panded by BFS. We also show that DFBnB is asymptotically optimal when BFS runs in exponential time. We then consider how to select a linear-space search algorithm, from among DFBnB, iterative-deepening (ID) and recursive best first search (RBFS). Our exper-imental results indicate that DFBnB is prefer-able on problems that can be represented by bounded-depth trees and require exponential computation; and RBFS should be applied to problems that cannot be represented by bounded-depth trees, or problems that can be solved in polynomial time.