Implementing Fast Heuristic Search Code - Burns, Ethan; Hatem, Matthew; Leighton, Michael; Ruml, Wheeler (Proceedings of the International Symposium on Combinatorial Search, 2012)
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