Designing Admissible Heuristics
What you'll learn: How to craft admissible heuristics by relaxing the original problem constraints to make it easier to solve.
The Core Idea
An admissible heuristic never overestimates the true cost to reach the goal. But how do you actually create one? The most powerful technique is problem relaxation: take your original problem and remove some of its constraints or rules. Solving this easier, relaxed version gives you an admissible heuristic for the original problem.
Why Relaxation Works
When you relax a problem, you're essentially allowing "shortcuts" that weren't permitted before. The relaxed problem is easier (or cheaper) to solve than the original, so its solution cost is always ≤ the original problem's cost. This guarantees admissibility.
Example: The 8-Puzzle
In the 8-puzzle, tiles can only slide into the blank space. Two famous heuristics come from relaxation:
-
Manhattan distance: Relax the rule that tiles must slide legally. Pretend each tile can teleport directly to its goal position. Count the total distance all tiles must travel. This "teleportation version" is easier, so its cost underestimates the real sliding cost.
-
Misplaced tiles: Relax even further—assume any tile can jump to its goal in one move. Count how many tiles aren't home yet. Even more optimistic, still admissible.
The Pattern
- Identify constraints in your problem
- Remove one or more constraints
- Solve (or estimate) the relaxed problem
- Use that cost as your heuristic
The less you relax, the more informed (closer to actual cost) your heuristic becomes—but it may be harder to compute.
Key Takeaway: Admissible heuristics are designed by solving relaxed versions of problems where constraints are removed, guaranteeing they never overestimate the true cost.