Must a heuristic be admissible?

Not for every use. Admissibility matters when it is part of a desired search guarantee; other approaches may use estimates that overstate costs.

What happens if h is always zero in A*?

Under the corresponding implementation and assumptions, its priority reduces to accumulated cost, yielding uniform-cost behavior.

Can a more accurate heuristic be slower overall?

Yes. The extra cost of evaluating it can outweigh any reduction in search work.

AI Glossary / Graphs and symbolic AI / Intermediate

Heuristic function

Definition

A heuristic function assigns a numerical estimate that helps guide a search. In shortest-path and classical problem-solving search, h(n) usually estimates the least remaining cost from a node's state to a goal. The search algorithm decides how to use that estimate; the function itself does not specify the entire search procedure.

What it means

A heuristic turns domain knowledge into a value that can rank candidates. For example, straight-line distance can estimate remaining route length when paths cannot be shorter than that distance. The estimate can be inexpensive because it ignores complications such as obstacles or road layout.
The units and meaning must match the task. Distance in meters cannot simply be added to accumulated time in seconds without a justified conversion. Other areas, such as game search, use evaluation functions with different interpretations. This entry focuses on remaining-cost estimates rather than treating every score assigned to a state as the same quantity.

How it works

Define a goal and cost model, then construct a computable estimate for each state. Possible approaches include simplifying the problem, using a relaxed model, or learning estimates from examples. Evaluate both how informative the values are and how expensive they are to compute.
An admissible heuristic never exceeds the true least remaining cost. A consistent heuristic additionally satisfies h(n) less than or equal to the step cost to a successor plus that successor's heuristic, with zero at goals in the usual convention. These properties support particular search guarantees under the algorithm's other assumptions. A* commonly uses g(n) + h(n); greedy best-first search uses h(n) alone.

Three practical examples

A grid-navigation solver uses Manhattan distance when movement is restricted to horizontal and vertical unit-cost steps.
A puzzle solver estimates remaining moves from a simplified version of the puzzle, then checks the conditions supporting a lower-bound claim.
A research comparison measures whether a more informative heuristic reduces search effort enough to justify its extra computation.

Think of it this way

Think of an estimate on a journey planner showing how much travel remains from each candidate stop. The estimate helps choose what to investigate, but it is not the journey already completed or a certificate that the destination has been reached. The analogy is limited because formal search properties depend on inequalities and explicit cost assumptions, not simply a plausible-looking estimate.

Worked example

Use a square grid with horizontal and vertical moves costing 1 each. Let the goal be (4, 5) and the current state be (1, 1). Manhattan distance is |4 - 1| + |5 - 1| = 3 + 4 = 7. Without obstacles, seven moves suffice. Obstacles can force extra moves, but cannot reduce the number of required coordinate changes under this movement model.
After moving from (1, 1) to (2, 1), the heuristic becomes |4 - 2| + |5 - 1| = 6. The consistency check on this edge is 7 less than or equal to 1 + 6, which holds with equality.
Now change the movement rules to allow diagonal moves costing 1. From (1, 1), three diagonal moves and one vertical move reach (4, 5) in four steps. The old Manhattan estimate remains 7 and therefore overestimates the true cost 4. A heuristic's admissibility depends on the problem model; it is not an intrinsic property of a familiar formula independent of the allowed actions.

Illustrative case study

In a fictional game-development exercise, Pine Paths adds diagonal movement to an existing grid navigator. The team keeps its old heuristic and continues describing it as a guaranteed lower bound. A small coordinate example reveals the mismatch.
The developer revises the estimate for the new movement costs and retests hand-checkable maps. The team documents the movement model alongside the heuristic so later rule changes trigger review. This invented case illustrates assumption tracking, not a claim about a particular game's speed or path quality.

Common misconceptions and mistakes

A heuristic value of zero need not prove that a state is a goal; an uninformative zero heuristic can assign zero everywhere. Use the actual goal test. Likewise, an admissible heuristic is not necessarily exact, and a learned estimate is not automatically admissible merely because its average prediction error is small.
Do not assume the same heuristic gives every search algorithm the same guarantees. Greedy search can return an expensive route even with exact remaining-cost estimates because it ignores accumulated cost. For A*, duplicate handling, reopening behavior, and other assumptions also matter when stating optimality claims.

Business use

Heuristic functions make search more directed by incorporating problem knowledge. They can be valuable in routing, planning, scheduling abstractions, and combinatorial problem solving where blind exploration would examine many irrelevant alternatives.
For a project, document the cost units, goal conditions, and assumptions behind the estimate. Compare total runtime as well as node expansions, because calculating the heuristic consumes resources. If guarantees are required, establish the relevant properties rather than relying only on favorable tests. If an aggressive estimate deliberately sacrifices a guarantee, describe that trade-off explicitly and evaluate solution quality under representative conditions.

Check your understanding

Why does Manhattan distance cease to be admissible in the diagonal-move example?

Answer: The new action model reaches the goal in four unit-cost steps, while Manhattan distance still returns seven. The estimate is now larger than the true least remaining cost.

Related terms

Learn next

Check admissibility and consistency on a tiny weighted graph with known shortest paths. Then change one action cost and repeat the checks. Trace how A* combines g and h so that the heuristic's role remains distinct from the search algorithm's bookkeeping.

Sources

Sources: Russell and Norvig, Informed search algorithms lecture slides: https://aima.cs.berkeley.edu/slides-pdf/chapter04a.pdf Poole and Mackworth, Artificial Intelligence: Foundations of Computational Agents, informed search: https://www.cs.ubc.ca/~poole/aibook/3e/html/ArtInt3e.Ch3.S6.html

Previous: Heuristic Next: Heuristic search