ECAI 2004 Conference Paper

[full paper]

A Case Study of Revisiting Best-First vs. Depth-First Search

Andreas Auer, Hermann Kaindl

Best-first search usually has exponential space requirements on difficult problems. Depth-first search can solve difficult problems with linear space requirements, but it cannot utilize large additional memory available on today’s machines. Therefore, we revisit the issue of when best-first or depth-first search is preferable to use. Through algorithmic improvements, it was possible for the first time to find optimal solutions of certain difficult problems (the complete benchmark set of Fifteen Puzzle problems) using traditional best-first search (with the Manhattan distance heuristic only). Our experimental results show that this search can solve them overall faster than any of the previously published approaches (using this heuristic). Note that this kind of search was believed to be incapable of solving randomly generated instances of the Fifteen Puzzle within practical resource limits because of its exponential space requirements. So, our case study suggests that changes in hardware and algorithmic improvements together can revise the previous assessment of best-first search.

Keywords: Search, heuristic search, best-first search, bidirectional search

Citation: Andreas Auer, Hermann Kaindl: A Case Study of Revisiting Best-First vs. Depth-First Search. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.141-145.