Skip navigation
Skip navigation
A change is coming. Click to see a sneak peek of the new Open Research Repository.

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

Request a Copy

link to publisher version

  • Altmetric Citations

Everitt, Tom; Hutter, Marcus

Description

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...[Show more]

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/103801
dc.description.abstractThe 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
dc.publisherSpringer International Publishing AG
dc.relation.ispartofseries28th Australasian Joint Conference on Artificial Intelligence AI 2015
dc.rightsAuthor Everitt now added 13Jan16
dc.sourceImplementing Modal Tableaux Using Sentential Decision Diagrams
dc.titleAnalytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph 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.ariespublicationu4334215xPUB1540
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.startpage166
local.bibliographicCitation.lastpage178
local.identifier.doi10.1007/978-3-319-26350-2_15
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2016-06-14T09:03:37Z
local.identifier.scopusID2-s2.0-84952662841
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Everitt_Analytical_Results_on_the_BFS_2015.pdf361.66 kBAdobe PDF    Request a copy
Show simple item record


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

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator