This paper extends existing analyses of the performance of heuristic search in several directions. First we show experimentally that, with minor modifications, an existing analysis of IDA* also applies to A*. Furthermore, we apply a related model to predict the performance of IDA*, using only the branching factor of the problem, the search depth, and the size of a pattern database, to the 15 puzzle. Finally, we extend this existing model to additive disjoint pattern databases. The reduction in the number of nodes expanded for IDA* using multiple additive pattern databases is the product of the reductions achieved by the individual databases. We experimentally verify this result using the 4-peg Towers of Hanoi problem. This is the first analysis of the performance of disjoint additive pattern databases.
We introduce a model for predicting the performance of IDA* using pattern database heuristics, as a function of the branching factor of the problem, the solution depth, and the size of the pattern databases. While it is known that the larger the pattern database, the more efficient the search, we provide a quantitative analysis of this relationship.
We consider the asymptotic time complexity of heuristic search algorithms, such as A* (Hart et al 1968), iterative-deepelfing-A* (IDA*) (Korf 1985), depth-first branch-and-bound (DFBnB), that are guaranteed to return optimal solutions. All these algorithms use the same cost function, f(n) g(n) h(n), applied to each node n of the search space, where g(n) is the cost of reaching node n from the initial state, and h(n) is an estimate of the cost of reaching a goal from node n. h(n) is admissible if it never overestimates the cost of reaching a goal from node n. These algorithms are only guaranteed to find an optimal solution, if their heuristic function is admissible (Hart et al 1968). The time complexity of these algorithms depends primarily on the quality of the heuristic function. For example, if the heuristic returns zero for every state, these algorithms become brute-force searches, with time complexity that is exponential in the solution cost. Alternatively, if the heuristic always returns the exact cost to reach a goal, the time complexity is linear in the solution depth, assuming ties among f values are broken in favor of smaller h values (Pearl 1984). Realistic cases fall between these two extremes.
In the past several years, significant progress has been made in finding optimal solutions to combinatorial problems. In particular, random instances of both Rubik's Cube, with over states, and the sliding-tilepuzzle, withalmost states, have been solved optimally. This progress is not the result of better search algorithms, but more effective heuristic evaluation functions. In addition, we have learned how to accurately predict the running time of admissible heuristic search algorithms, as a function of the solution depth and the heuristic evaluation function. One corollary of this analysis is that an admissible heuristic function reduces the effective depth of search, rather than the effective branching factor.
We integrate a number of recent advances in heuristic search, and apply them to the four-peg Towers of Hanoi problem. These include frontier search, disk-based search, multiple compressed disjoint additive pattern database heuristics, and breadth-first heuristic search. The main new idea we introduce here is the use of pattern database heuristics to search for any of a number of explicit goal states, with no overhead compared to a heuristic for a single goal state. We perform the first complete breadth-first searches of the 21 and 22-disc four-peg Towers of Hanoi problems, and extend the verification of a "presumed optimal solution" to this problem from 24 to 30 discs, a problem that is 4096 times larger.