Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search

Tom Everitt, Marcus Hutter

Abstract

The algorithm selection problem asks to select the best algorithm for a given problem. In the companion paper (Everitt and Hutter 2015b), expected runtime was approximated as a function of search depth and probabilistic goal distribution for tree search versions of breadth-first search (BFS) and depth-first search (DFS). Here we provide an analogous analysis of BFS and DFS graph search, deriving expected runtime as a function of graph structure and goal distribution. The applicability of the method is demonstrated through analysis of two different grammar problems. The approximations come surprisingly close to empirical reality.
BibTeX
@inproceedings{everitt2015analytical,
  author = {Tom Everitt and Marcus Hutter},
  title = {{Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search}},
  booktitle = {Australasian Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1007/978-3-319-26350-2\_15},
}

Loading related content...

Figure