EUVIMEDEUVIMED entdecken
Crossref

Open List Implementations in A*

Remo Christen, Florian Pommerening, Malte Helmert

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →