Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 46 ยท Informed Search

Admissible and Consistent Heuristics

Learn admissible and consistent heuristics, dominance, relaxed problems and pattern databases, and test your own heuristics against true costs in Python.

A* comes with a guarantee: if the heuristic is safe, the first solution it pops is the cheapest. This lesson defines what "safe" means, gives you a second, slightly stronger condition, and shows how to design heuristics that meet both. You will also learn how to test a heuristic in code instead of trusting your intuition. Heuristics are where most of the engineering effort in a real A* system goes, so this is the most practical lesson of the chapter.

Admissible heuristics

Let h*(n) be the true cheapest cost from state n to a goal. A heuristic h is admissible if it never overestimates:

0 โ‰ค h(n) โ‰ค h*(n) for every state n.

Admissible heuristics are optimistic: they say "it can't cost less than this", never "it costs at least this much more than you think". Straight-line distance is the textbook example. A road can't be shorter than the straight line between its ends, so the line never overestimates. The proof you saw in the previous lesson relied on exactly this property, and the demonstration with an inflated h(A) showed what goes wrong without it.

Admissibility is a fact about every state, and a single violation is enough to lose the guarantee. That is why it is worth testing exhaustively when the state space is small enough.

Consistent heuristics

Admissibility has a stronger sibling. A heuristic is consistent (or monotone) if, for every state n and every successor nโ€ฒ reached by an action with step cost c:

h(n) โ‰ค c(n, nโ€ฒ) + h(nโ€ฒ)

This is a triangle inequality: the estimate at n can never be more than the cost of one step plus the estimate at the next state. In other words, the estimate may fall by at most the real cost of a step.

graph LR
    N(("n<br/>h(n)")) -- "step cost c" --> M(("n'<br/>h(n')"))
    M -. "h(n')" .-> G(("goal"))
    N -. "h(n) must not exceed c + h(n')" .-> G

Consistency is the triangle inequality: going to nโ€ฒ first and then estimating can never beat estimating from n directly.

Two facts connect the ideas:

  • Every consistent heuristic is admissible (given h(goal) = 0). Chain the inequality along an optimal path to the goal.
  • Not every admissible heuristic is consistent, but nearly all the natural ones are, and you have to work a little to invent an admissible one that is not.

Consistency has a practical payoff. With a consistent heuristic, the f values along any path never decrease, and the first time A* expands a state it has already found the cheapest way there. The "explored set" version of A* can then ignore repeated states safely. With an admissible-but-inconsistent heuristic, the algorithm must be willing to reopen states when it finds a cheaper route later, which our heap-and-best-g implementation does naturally; it just can do more work.

Testing heuristics in code

For small problems you can compute h* for every state and check both properties exhaustively. The 8-puzzle has only 181,440 reachable states, so one breadth-first search outward from the goal gives the true cost of all of them. (Moves are reversible, so distance from the goal equals distance to the goal.) Then audit four heuristics: misplaced tiles, Manhattan distance, Manhattan doubled (an obvious overestimate) and a "patchy" one that returns Manhattan distance only when the blank is on an even square and 0 otherwise.

Python Auditing heuristics against the true cost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the audit like a report:

  • Misplaced tiles and Manhattan distance are admissible and consistent: zero violations. Their averages (7.11 and 14.00) sit well below the true average of 21.97, as an optimistic estimate should.
  • 2 ร— Manhattan overestimates on 157,176 of the 181,440 states. It also breaks consistency. A* with this heuristic is fast, but its answers are no longer guaranteed optimal.
  • Patchy never exceeds the true cost, so it is admissible, but its value jumps up and down as the blank moves. It fails the consistency check on about half of all moves. It would still find optimal answers, but only because the implementation reopens states.

If you can't enumerate all states, test on a sample: solve a few hundred random instances optimally (with a trusted heuristic or breadth-first search) and assert h(state) <= true_cost(state) for every state along the optimal paths. A failing assertion is cheap proof that a heuristic is broken.

Dominance: which heuristic is better?

If two admissible heuristics satisfy hโ‚‚(n) โ‰ฅ hโ‚(n) for every state, we say hโ‚‚ dominates hโ‚. Because both are still at most h*(n), the larger one is closer to the truth. Every node that A* expands with hโ‚‚ is also expanded with hโ‚ (up to ties), so the dominating heuristic never loses and usually wins big. The last line of the audit confirms that Manhattan distance dominates misplaced tiles on all 181,440 states, which is why the previous lesson saw about 349 expansions on average for Manhattan against about 2,324 for misplaced tiles.

If neither heuristic dominates the other, you don't have to choose. The maximum of several admissible heuristics is itself admissible, and it dominates each of its parts: h(n) = max(hโ‚(n), hโ‚‚(n)). You pay the cost of computing both, and get the best of each.

Designing heuristics by relaxation

Where do admissible heuristics come from? The most reliable source is a relaxed problem, a version of the problem with some rules removed, so that it is easy to solve. Every solution of the real problem is also a solution of the relaxed one, so the cheapest relaxed solution costs no more than the cheapest real solution. The exact cost of the relaxed problem is therefore an admissible heuristic for the real one.

Real problem Relaxation (a rule removed) Heuristic you get
8-puzzle A tile may jump to any square Number of misplaced tiles
8-puzzle A tile may slide onto an occupied square Manhattan distance
Road routing Roads may be ignored Straight-line distance
Warehouse robot on a grid Walls and other robots vanish Manhattan distance
Task scheduling Ignore resource limits Longest chain of dependent tasks

Relaxed-problem heuristics are also automatically consistent, as long as the relaxed problem's cost obeys the triangle inequality, which shortest-path costs always do. The art lies in choosing a relaxation that is easy enough to solve fast but close enough to the original to be informative.

Pattern databases

Pattern databases take relaxation further. Instead of dropping a rule, they forget details. For the 8-puzzle, keep only the positions of the blank and tiles 1 to 4, and treat tiles 5 to 8 as indistinguishable. This abstract puzzle has just 9 ร— 8 ร— 7 ร— 6 ร— 5 = 15,120 states. Solve all of them once, by breadth-first search outward from the abstract goal, and store the cost of each in a table. Every real move maps to an abstract move, so the abstract cost never exceeds the real cost: the table lookup is an admissible heuristic that costs one dictionary access.

Python A tiny pattern database for the 8-puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The database has exactly 15,120 entries. On these eight puzzles the pattern heuristic starts higher than Manhattan distance (16.8 against 12.8 on average) and cuts the average number of expansions from 838 to 364. Taking the maximum of both gives 204. Building the table costs a moment of precomputation, but it is paid once and then reused for every puzzle, which is why pattern databases power the strongest solvers for the 15-puzzle, Rubik's Cube and many planning problems. Real systems use several disjoint patterns whose costs can be added without breaking admissibility, a refinement you will not need until the puzzles get much bigger.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A heuristic is admissible if:

    Admissible means 0 <= h(n) <= h*(n) for every state, where h*(n) is the true cost to the nearest goal.
  2. 2. Which statement about consistency and admissibility is correct?

    Consistency (h(n) <= c + h(n')) chained along an optimal path to a goal with h = 0 implies admissibility. The reverse fails, as the 'patchy' heuristic in the audit shows.
  3. 3. Heuristic h2 dominates h1 when both are admissible and:

    A larger admissible estimate is closer to the true cost, so A* with the dominating heuristic expands no more nodes (up to ties).
  4. 4. Why is the exact cost of a relaxed problem an admissible heuristic?

    Removing rules only adds options. The cheapest option in the larger set cannot be more expensive than the cheapest in the smaller one.

Summary

  • An admissible heuristic never overestimates the true cost; it guarantees that A* returns optimal solutions.
  • A consistent heuristic satisfies h(n) โ‰ค c(n, nโ€ฒ) + h(nโ€ฒ); it implies admissibility and means no state ever needs reopening.
  • You can audit a heuristic by computing true costs by breadth-first search from the goal on small spaces, or by sampling optimal solutions on larger ones.
  • Dominance tells you which of two admissible heuristics is better, and the maximum of admissible heuristics is admissible.
  • Relaxing a problem's rules, or abstracting away details as in pattern databases, is the standard way to invent good heuristics.

Next, see what to do when A* runs out of memory in IDA*, Beam Search and Weighted A*.