Abstract
This paper provides a theoretical and empirical foundation for the multiplicative speedup observed when combining independent additive heuristics in search algorithms. We demonstrate that for independent heuristics, the reduction in nodes expanded is the product of individual reductions, a principle validated across multiple domains including Towers of Hanoi and Multiple Sequence Alignment.
Introduction
In heuristic search algorithms like IDA*, the efficiency of finding a solution depends heavily on the quality of the heuristic function $h(n)$. A common technique to improve $h(n)$ is the use of "additive heuristics," where a problem is partitioned into disjoint components and the costs for these components are summed. While researchers have long known that adding these estimates creates a stronger heuristic, this paper formally quantifies the performance gain. It establishes that if the heuristics are independent, their benefits multiply, explaining why disjoint pattern databases (PDBs) are exceptionally effective for complex combinatorial problems.
Methodology
The authors approach the problem through both theoretical proof and empirical validation. They define "independence" for heuristics: knowing the value of $h_1$ tells you nothing about the value of $h_2$. Using the concept of equilibrium distributions (the distribution of heuristic values at deep levels of a search tree), they prove that for unit-cost trees with a uniform branching factor, the search reduction factor is multiplicative. Furthermore, they show that the sum of two independent heuristics results in a heuristic distribution that is the mathematical convolution of the individual distributions, allowing for precise performance modeling.
Experimental Results
Towers of Hanoi
The theory was tested on the 16-disc 4-peg Towers of Hanoi, where disjoint PDBs are truly independent. The results confirmed the multiplicative rule with high accuracy.
As shown in Table 1, at depth 21, a single 8-disc PDB is predicted to expand approximately 107 million nodes. In contrast, the sum of two independent 8-disc PDBs is predicted to expand only 4,396 nodes. This massive reduction illustrates the multiplicative power of independent heuristics, as the reduction factor remains constant across various depths.
Multiple Sequence Alignment (MSA)
The theory was further validated using Multiple Sequence Alignment, a bioinformatics problem involving non-unit edge costs and directed graphs.
In Figure 1, the experimental data for MSA shows a constant vertical distance on a log scale for each additional heuristic added. This constant spacing confirms that each independent heuristic contributes a consistent multiplicative reduction factor to the search space, even in domains that slightly violate theoretical assumptions like uniform branching.
The Cost of Dependency: The 15-Puzzle
The 15-puzzle served as a critical counter-example. Here, disjoint sets of tiles are dependent because they compete for the same physical board positions. In these experiments, assuming independence when it did not exist led to a 75% error in predicting search performance. The convolution model significantly underestimated the number of nodes because it failed to account for the correlation between heuristic values, where small values are more likely to occur simultaneously when heuristics are dependent.
Conclusion
This research provides a formal explanation for the effectiveness of additive heuristics, showing that independence leads to multiplicative search space reduction. While the principle holds broadly, the strict requirement for independence is often violated in real-world problems. Future work should focus on analyzing and predicting performance for dependent additive heuristics, which are more common in practical applications.
Summary updated