Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search
Lists
Only you see this
Abstract
Breadth-first search (BFS) and depth-first search (DFS) are the two most fundamental search algorithms. We derive approximations of their expected runtimes in complete trees, as a function of tree depth and probabilistic goal distribution. We also demonstrate that the analytical approximations are close to the empirical averages for most parameter settings, and that the results can be used to predict the best algorithm given the relevant problem features.
BibTeX
@inproceedings{everitt2015analytical,
author = {Tom Everitt and Marcus Hutter},
title = {{Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search}},
booktitle = {Australasian Conference on Artificial Intelligence},
year = {2015},
doi = {10.1007/978-3-319-26350-2\_14},
}Loading related content...