Implementing Fast Heuristic Search Code

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