AAAI Publications, Fifth Annual Symposium on Combinatorial Search

Font Size: 
Implementing Fast Heuristic Search Code
Ethan Andrew Burns, Matthew Hatem, Michael J. Leighton, Wheeler Ruml

Last modified: 2012-07-13

Abstract


Published papers rarely disclose implementation details. In this paper we show how such details can account for speedups of up to a factor of 28 for different implementations of the same algorithm. We perform an in-depth analysis of the most popular benchmark in heuristic search: the 15-puzzle. We study implementation choices in C++ for both IDA* and A* using the Manhattan distance heuristic. Results suggest that several optimizations deemed critical in folklore provide only small improvements while seemingly innocuous choices can play a large role. These results are important for ensuring that the correct conclusions are drawn from empirical comparisons

Full Text: PDF