Open List Implementations in A*
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 213-218
DOI: 10.1609/socs.v19i1.43090 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Remo Christen und 2 weiteren Autor:innen.
Abstract (Originalsprache)
A* is the most important algorithm in optimal heuristic search. For its implementation, details beyond the scope of textbook descriptions become relevant. One such detail is how A* deals with duplicate states. A common approach is to modify a state's open list entry when a cheaper path to that state is found, updating its key. A binary heap often serves as the underlying data structure despite its suboptimal asymptotic runtime. More complex structures with better asymptotic runtime such as Fibonacci heaps are said to not pay off. A wide-spread alternative is to delay duplicate detection until expansion, allowing multiple entries for the same state on the open list. So far, the effect of these choices has not been studied in isolation for domain-independent planning. We compare early duplicate detection using a binary heap, Fibonacci heap, pairing heap, or bucket priority queue to delayed duplicate detection in order to evaluate whether early duplicate detection can be worth it.
Zitieren
APA
Christen, R., Pommerening, F., & Helmert, M. (2026). Open List Implementations in A*. Proceedings of the International Symposium on Combinatorial Search, 19(1), 213-218. https://doi.org/10.1609/socs.v19i1.43090
Vancouver
Christen R, Pommerening F, Helmert M. Open List Implementations in A*. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):213-218. doi:10.1609/socs.v19i1.43090
BibTeX
@article{Christen2026,
author = {Christen, Remo and Pommerening, Florian and Helmert, Malte},
title = {Open List Implementations in A*},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {213--218},
doi = {10.1609/socs.v19i1.43090}
}
EUVIMED