Analytical results on the BFS vs. DFS algorithm selection problem: Part II: Graph search

Tom Everitt; Marcus Hutter

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

Analytical results on the BFS vs. DFS algorithm selection problem: Part II: Graph search

Tom Everitt^*, Marcus Hutter

^*Corresponding author for this work

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

8 Citations (Scopus)

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.

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	166-178
Number of pages	13
ISBN (Print)	9783319263496
DOIs	https://doi.org/10.1007/978-3-319-26350-2_15
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_15

Cite this

Everitt, T., & Hutter, M. (2015). Analytical results on the BFS vs. DFS algorithm selection problem: Part II: Graph search. In J. Renz, & B. Pfahringer (Eds.), AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings (pp. 166-178). (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_15

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

@inproceedings{010aaf409ef3407b9a6f066ba60e1ff5,

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

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

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\_15",

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 = "166--178",

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 II: Graph 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. 166-178, 28th Australasian Joint Conference on Artificial Intelligence, AI 2015, Canberra, Australia, 30/11/15. https://doi.org/10.1007/978-3-319-26350-2_15

Analytical results on the BFS vs. DFS algorithm selection problem: Part II: Graph 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. 166-178 (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 Paper › peer-review

TY - GEN

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

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

AU - Everitt, Tom

AU - Hutter, Marcus

PY - 2015

Y1 - 2015

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

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

UR - https://www.scopus.com/pages/publications/84952662841

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

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

M3 - Conference Paper

SN - 9783319263496

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

SP - 166

EP - 178

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 II: Graph search. In Renz J, Pfahringer B, editors, AI 2015: Advances in Artificial Intelligence - 28th Australasian Joint Conference, Proceedings. Springer Verlag. 2015. p. 166-178. (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_15

Analytical results on the BFS vs. DFS algorithm selection problem: Part II: Graph search

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this