A case study of revisiting best-first vs. depth-first search
Andreas Auer, Hermann Kaindl · European Conference on Artificial Intelligence · 2004
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 search approach 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.