Implementing Fast Heuristic Search Code
| Autor: | Ethan Burns, Matthew Hatem, Michael Leighton, Wheeler Ruml |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Proceedings of the International Symposium on Combinatorial Search. 3:25-32 |
| ISSN: | 2832-9163 2832-9171 |
| DOI: | 10.1609/socs.v3i1.18245 |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|