The exploration efficiency of algorithms like A* is often measured with respect to the number of expanded/generated problem graph nodes, but the actual runtimes depend crucially on how the Open and Closed lists are implemented. In this chapter we look closer at efficient data structures to represent these sets.
For the Open list, different options for implementing a priority queue data structure are considered. We distinguish between integer and general edge costs, and introduce bucket and advanced heap implementations.
For efficient duplicate detection and removal we also look at hash dictionaries. We devise a variety of hash functions that can be computed efficiently and that minimize the number of collisions by approximating uniformly distributed addresses, even if the set of chosen keys is not (which is almost always the case). Next we explore memory-saving dictionaries, the space requirements of which come close to the information-theoretic lower bound and provide a treatment of approximate dictionaries.
Subset dictionaries address the problem of finding partial state vectors in a set. Searching the set is referred to as the Subset Query or the Containment Query problem. The two problems are equivalent to the Partial Match retrieval problem for retrieving a partially specified input query word from a file of k-letter words with k being fixed. A simple example is the search for a word in a crossword puzzle. In a state space search, subset dictionaries are important to store partial state vectors like dead-end patterns in Sokoban that generalize pruning rules (see Ch. 10).
In state space search, string dictionaries are helpful to exclude a set of forbidden action sequences, like UD or RL in the (n-squared-1)-Puzzle, from being generated. Such sets of excluded words are formed by concatenating move labels on paths that can be learned and generalized (see Ch. 10). Therefore, string dictionaries provide an option to detect and eliminate duplicates without hashing and can help to reduce the efforts for storing all visited states. Besides the efficient insertion (and deletion) of strings, the task to determine if a query string is the substring of a stored string is most important and has to be executed very efficiently. The main application for string dictionaries are web search engines. The most flexible data structure for efficiently solving this Dynamic Dictionary Matching problem is the Generalized Suffix Tree.
[MK] Sloane
