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

dc.contributor.authorEveritt, Tom
dc.contributor.authorHutter, Marcus
dc.coverage.spatialCanberra, Australia
dc.date.accessioned2016-06-14T23:21:15Z
dc.date.created30 November to 4 December 2015
dc.identifier.isbn9783319263496
dc.identifier.urihttp://hdl.handle.net/1885/103802
dc.description.abstractBreadth-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
dc.publisherSpringer International Publishing AG
dc.relation.ispartofseries28th Australasian Joint Conference on Artificial Intelligence AI 2015
dc.sourceImplementing Modal Tableaux Using Sentential Decision Diagrams
dc.titleAnalytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2015
local.identifier.absfor080199 - Artificial Intelligence and Image Processing not elsewhere classified
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationu4334215xPUB1541
local.type.statusPublished Version
local.contributor.affiliationEveritt, Tom, College of Engineering and Computer Science, ANU
local.contributor.affiliationHutter, Marcus, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage157
local.bibliographicCitation.lastpage165
local.identifier.doi10.1007/978-3-319-26350-2_14
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2016-06-14T09:03:38Z
local.identifier.scopusID2-s2.0-84952649168
CollectionsANU Research Publications

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:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator