A case study of revisiting best-first vs. depth-first search

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