Skip navigation
Skip navigation

Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search

Everitt, Tom; Hutter, Marcus

Description

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

CollectionsANU Research Publications
Date published: 2015
Type: Conference paper
URI: http://hdl.handle.net/1885/103802
Source: Implementing Modal Tableaux Using Sentential Decision Diagrams
DOI: 10.1007/978-3-319-26350-2_14

Download

File Description SizeFormat Image
01_Everitt_Analytical_Results_on_the_BFS_2015.pdf413.96 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator