TY - GEN

T1 - Depth-first vs. best-first search

T2 - Proceedings of the 11th National Conference on Artificial Intelligence

AU - Zhang, Weixiong

AU - Korf, Richard E.

PY - 1993

Y1 - 1993

N2 - Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS. Using 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 · N), where d is the goal depth and N is the expected number of nodes expanded 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 experimental results indicate that DFBnB is preferable 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.

AB - Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS. Using 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 · N), where d is the goal depth and N is the expected number of nodes expanded 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 experimental results indicate that DFBnB is preferable 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.

UR - http://www.scopus.com/inward/record.url?scp=0027704773&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027704773

SN - 0262510715

T3 - Proceedings of the National Conference on Artificial Intelligence

SP - 769

EP - 775

BT - Proceedings of the National Conference on Artificial Intelligence

PB - Publ by AAAI

Y2 - 11 July 1993 through 15 July 1993

ER -