Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search

Tom Everitt; Marcus Hutter

doi:10.1007/978-3-319-26350-2_14

Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search

Tom Everitt^*, Marcus Hutter

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

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.

Original language	English
Title of host publication	AI 2015
Subtitle of host publication	Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings
Editors	Jochen Renz, Bernhard Pfahringer
Publisher	Springer Verlag
Pages	157-165
Number of pages	9
ISBN (Print)	9783319263496
DOIs	https://doi.org/10.1007/978-3-319-26350-2_14
Publication status	Published - 2015
Event	28th Australasian Joint Conference on Artificial Intelligence, AI 2015 - Canberra, Australia Duration: 30 Nov 2015 → 4 Dec 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9457
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th Australasian Joint Conference on Artificial Intelligence, AI 2015
Country/Territory	Australia
City	Canberra
Period	30/11/15 → 4/12/15

Access to Document

10.1007/978-3-319-26350-2_14

Cite this

Everitt, T., & Hutter, M. (2015). Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search. In J. Renz, & B. Pfahringer (Eds.), AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings (pp. 157-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9457). Springer Verlag. https://doi.org/10.1007/978-3-319-26350-2_14

Everitt, Tom ; Hutter, Marcus. / Analytical results on the BFS vs. DFS algorithm selection problem. Part I : Tree search. AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings. editor / Jochen Renz ; Bernhard Pfahringer. Springer Verlag, 2015. pp. 157-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{be4e40f8b6e74554916f6df683be3731,

title = "Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search",

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.",

author = "Tom Everitt and Marcus Hutter",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 28th Australasian Joint Conference on Artificial Intelligence, AI 2015 ; Conference date: 30-11-2015 Through 04-12-2015",

year = "2015",

doi = "10.1007/978-3-319-26350-2_14",

language = "English",

isbn = "9783319263496",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "157--165",

editor = "Jochen Renz and Bernhard Pfahringer",

booktitle = "AI 2015",

address = "Germany",

}

Everitt, T & Hutter, M 2015, Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search. in J Renz & B Pfahringer (eds), AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9457, Springer Verlag, pp. 157-165, 28th Australasian Joint Conference on Artificial Intelligence, AI 2015, Canberra, Australia, 30/11/15. https://doi.org/10.1007/978-3-319-26350-2_14

Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search. / Everitt, Tom; Hutter, Marcus.
AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings. ed. / Jochen Renz; Bernhard Pfahringer. Springer Verlag, 2015. p. 157-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9457).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Analytical results on the BFS vs. DFS algorithm selection problem. Part I

T2 - 28th Australasian Joint Conference on Artificial Intelligence, AI 2015

AU - Everitt, Tom

AU - Hutter, Marcus

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84952649168&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-26350-2_14

DO - 10.1007/978-3-319-26350-2_14

M3 - Conference contribution

SN - 9783319263496

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 165

BT - AI 2015

A2 - Renz, Jochen

A2 - Pfahringer, Bernhard

PB - Springer Verlag

Y2 - 30 November 2015 through 4 December 2015

ER -

Everitt T, Hutter M. Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search. In Renz J, Pfahringer B, editors, AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings. Springer Verlag. 2015. p. 157-165. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-26350-2_14

Analytical results on the BFS vs. DFS algorithm selection problem. Part I: Tree search

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this