Course contentsShow
← Computer Science
Lesson 2759 of 2,87261. AI and Search AlgorithmsFree lesson

Combining Heuristics: Max and Sum

Explore methods for combining multiple heuristics while maintaining admissibility.

Combining Heuristics: Max and Sum

What you'll learn: How to merge multiple admissible heuristics into a single, more informed heuristic while preserving optimality guarantees in A* search.

The Problem with Single Heuristics

When solving complex search problems, you often have multiple admissible heuristics available. For example, in navigation you might have both Manhattan distance and Euclidean distance, or in puzzle-solving you might have different pattern database heuristics. The question is: can you combine them to get better guidance?

Two Safe Combination Methods

The Max Approach

Taking the maximum of multiple admissible heuristics always yields another admissible heuristic:

h(n) = max(h₁(n), h₂(n), ..., hₖ(n))

Why it works: If each heuristic underestimates the true cost (admissible), then the largest underestimate is still an underestimate. Think of it like having multiple conservative price estimates for a car—the highest conservative estimate is still conservative.

The Sum Approach (With Caution)

Adding heuristics is not always safe:

h(n) = h₁(n) + h₂(n)

This only maintains admissibility if the heuristics measure independent, additive subgoals. For instance, if h₁ estimates cost to collect all keys and h₂ estimates cost to reach all doors, and these don't overlap, summation might work. However, if both heuristics estimate aspects of the same underlying cost, you'll overestimate—breaking admissibility.

Which to Choose?

Max is safer and commonly used. It never overestimates and gives you the most informed among your options at each state. Sum can be more powerful but requires careful analysis to ensure the heuristics truly capture disjoint costs.

Key Takeaway: The max of multiple admissible heuristics is always admissible and often more informative; summing heuristics risks inadmissibility unless they measure independent subproblems.