by
Graham Reihana(grei007@aucklanduni.ac.nz)
Auer, A., Kaindl, H.: A case study of revisiting best-first vs. depth-first search. In: Proceedings ECAI-04, Valencia (Spain) (2004) 141–145.
Best-First Search, Depth-First Search, Fifteen Puzzle Problem, Iiterative-Deepening-A*, Bi-Directional Search, Max-Heuristic.
H. Kaindl and G. Kainz. Bidirectional heuristic search reconsidered. Journal of Artificial Intelligence Research (JAIR), 7:283-317, 1997.
H. Kaindl, G. Kainz, A. Leeb, and H.
Smetana. How to use limited memory in heuristic search. In
Proc. Fourteenth International Joint Conference on Artificial Intelligence
(IJCAI-95), pages 236-242. San Francisco, CA: Morgan
Kaufmann Publishers, 1995.
J.B. Kwa, BS*: An Admissible Bidirectional Staged Heuristic Search Algorithm, Artificial Intelligence 38 (1989) 95-109.
Using the benchmark of Fifteen puzzle problems, this paper shows that traditional best-first search algorithms can now find optimal solns by using dynamically improved heuristics. The use of the algorithm GenericBS* which is a generic BS* algorithm shows how one can solve difficult problems faster overall without having to increase the memory size of your computer..
This paper is well organised and straight forward to understand. The authors present a strong argument to explain how best-first search algorithms with algorithmic improvements can now solve the fifteen puzzle problem, where in the past it was impossible to do using the manhattan distance heuristic. However this paper doesn't present any running times of the algorithms used.