×

zbMATH — the first resource for mathematics

External A*. (English) Zbl 1132.68698
Biundo, Susanne (ed.) et al., KI 2004: Advances in artificial intelligence. 27th annual German conference in AI, KI 2004, Ulm, Germany, September 20–24, 2004, Proceedings. Berlin: Springer (ISBN 978-3-540-23166-0/pbk). Lecture Notes in Computer Science 3238. Lecture Notes in Artificial Intelligence, 226-240 (2004).
Summary: In this paper we study External A*, a variant of the conventional (internal) A* algorithm that makes use of external memory, e.g., a hard disk. The approach applies to implicit, undirected, unweighted state space problem graphs with consistent estimates. It combines all three aspects of best-first search, frontier search and delayed duplicate detection and can still operate on very small internal memory. The complexity of the external algorithm is almost linear in external sorting time and accumulates to \(O(\text{sort}(|E|) + \text{scan}(|V|))\) I/O operations, where \(V\) and \(E\) are the set of nodes and edges in the explored portion of the state space graph. Given that delayed duplicate elimination has to be performed, the established bound is I/O optimal. In contrast to the internal algorithm, we exploit memory locality to allow blockwise rather than random access. The algorithmic design refers to external shortest path search in explicit graphs and extends the strategy of delayed duplicate detection recently suggested for breadth-first search to best-first search. We conduct experiments with sliding-tile puzzle instances.
For the entire collection see [Zbl 1131.68004].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI