Abstract
Heuristic search algorithms like IDA* rely on accurate estimates of the distance to a goal to prune search spaces effectively. Pattern Databases (PDBs) have emerged as a dominant method for generating these heuristics by precomputing exact solutions to subproblems. While it is intuitively understood that larger PDBs lead to faster searches, this paper provides a rigorous mathematical framework to quantify this space-time tradeoff. We demonstrate that a single PDB of size $s$ reduces search effort by a factor of approximately $s / \log_b s$, and that taking the maximum of multiple PDBs yields even more significant, near-linear improvements.
Introduction
In the domain of heuristic search, the efficiency of algorithms like A and IDA is heavily dependent on the quality of the heuristic function $h(n)$. Pattern Databases (PDBs) store the exact costs of solving specific sub-problems in a lookup table. For example, in the Rubik's Cube, a PDB might store the number of moves required to correctly position a subset of the corner cubies.
Prior to this work, the relationship between PDB size and search performance was largely based on empirical observation or informal "inverse linear" arguments—the idea that doubling the memory would roughly halve the time. This paper formalizes these intuitions, providing a predictive model based on the branching factor $b$ and the database size $s$.
Modeling Heuristic Performance
The foundation of this analysis is the Korf-Reid-Edelkamp formula, which predicts the number of nodes expanded by IDA* at a depth $d$ given a heuristic's equilibrium distribution. The equilibrium distribution $P(x)$ is the probability that a randomly chosen state in the search space has a heuristic value of $x$.
To derive a closed-form expression, the author models the PDB construction process. A PDB is typically built using a backward breadth-first search from the goal state. In a search space with branching factor $b$, the number of states at distance $x$ from the goal grows as $b^x$. By substituting this exponential growth model into the performance formula, the paper derives the expected number of nodes expanded, $E(b, d, s)$.
Single Pattern Databases: The $s / \log_b s$ Factor
A key finding of the paper is the correction of the "inverse linear" hypothesis. If search effort were strictly inversely proportional to PDB size, the speedup factor would be simply $s$. However, the derived model shows that a single PDB actually performs slightly better than this, with a speedup factor of approximately $s / (\log_b s + 1)$.
As shown in the experimental data for the Rubik's Cube (Figure 2), the model $E(b, 12, s)$ provides a strong baseline for predicting IDA* performance across PDBs ranging from 14 million to over 500 million entries. The "7 edges" PDB, the largest tested, reduced the search effort by several orders of magnitude compared to smaller corner-based PDBs.
The Synergy of Multiple Databases
One of the most powerful techniques in heuristic search is taking the maximum value from several different PDBs. The paper proves that this "maxing" strategy is more efficient than using a single PDB of the same total size. Mathematically, taking the maximum of $k$ independent heuristics shifts the probability distribution toward higher values. This "compresses" the distribution, leading to a much higher average heuristic value and, consequently, more aggressive pruning of the search tree.
Figure 3 illustrates this effect. Moving from a single 6-edge PDB to the maximum of two reduces the actual node expansions from approximately 8 million to just 226,000—a 35-fold improvement. This demonstrates that the benefits of multiple PDBs are near-linear or even super-linear in certain regimes, provided the PDBs are sufficiently independent.
Empirical Validation and Limitations
The models were validated using the 3x3x3 Rubik's Cube, a problem with a high branching factor (~13.35) and a massive state space. While the theoretical predictions closely match the experimental results, the author notes two important caveats:
- Independence: The multiple-PDB model assumes the databases are independent. In practice, PDBs for the same problem often share state information, which introduces positive correlation and slightly reduces the effectiveness of the "max" operation.
- Graph vs. Tree: The model assumes a tree-like search space. In problems with many cycles (transpositions), the effective branching factor may decrease at greater depths, a phenomenon not fully captured by the current formula.
Conclusion
This work replaces heuristic intuition with a solid mathematical framework for PDB performance. By showing that the speedup is roughly $s / \log_b s$ and highlighting the dramatic gains from using multiple PDBs, it provides search researchers with the tools to make informed decisions about memory allocation and heuristic design. Future work aims to extend this analysis to additive PDBs, which often outperform "maxed" PDBs by summing non-overlapping subproblem costs.
Summary updated