Implementing Fast Heuristic Search Code
Ethan Burns, Matthew Hatem, Michael Leighton, Wheeler Ruml
2021Proceedings of the International Symposium on Combinatorial Search46 citationsDOIOpen Access PDF
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
Topics & Concepts
Benchmark (surveying)HeuristicImplementationComputer scienceCode (set theory)Incremental heuristic searchFactor (programming language)Scheme (mathematics)Search algorithmTheoretical computer scienceMachine learningArtificial intelligenceComputer engineeringAlgorithmBeam searchProgramming languageMathematicsSet (abstract data type)Mathematical analysisGeodesyGeographyConstraint Satisfaction and OptimizationAI-based Problem Solving and PlanningArtificial Intelligence in Games