Tree search lets the same state be expanded many times, so even if a bad path reaches a state first, the good path gets its turn eventually. Graph search adds a closed set: once a state is expanded, it is never expanded again.
This is not a free optimization. It is a bet — the bet that the first time a state is popped, it already carries its optimal g-value. When we delete repeated nodes to avoid repeating work, we are simultaneously burying every path that would have passed through them later.
Admissibility alone cannot back this bet. It guarantees each h(n) never overestimates the true remaining cost — a pointwise, absolute condition. But the priority queue's pop order is decided by relative f-values. A heuristic can be honest at every single node and still lie unevenly, and uneven lies distort the ordering.
Definition. A heuristic h is consistent if for every edge n → n′:
$h(n) \le c(n, n') + h(n')$
with the boundary condition h(goal) = 0. Rearranged: h(n) − h(n′) ≤ c(n, n′) — crossing an edge of cost c, h may drop by at most c. This one inequality wears three different costumes:
| Viewpoint | What violation looks like | Why it matters |
|---|---|---|
| Algebraic — f along a route | f decreases along an edge | Δf = Δg + Δh = c(n,n′) − (h(n) − h(n′)). So f drops ⟺ h drops by more than the edge cost ⟺ consistency violated on that edge. Consistent h ⟹ f is monotone non-decreasing along every path ⟹ pop order = optimal order. |
| Fairness — relative optimism | One node is disproportionately optimistic compared to its neighbor | If f decreases on a route, then relative to the later node's estimate, you were overestimating cost before — and every path through that relatively-overestimated node has been treated unfairly: systematically pushed back in the priority queue. In tree search this only costs time; in graph search, "delayed" becomes "permanently locked out" — a disaster. |
| Geometric — the height map | A cliff: h falls off faster than distance allows | View h as a height map over the state space, zero at the goal. Consistency says the terrain must slope down to the goal with gradient at most 1 everywhere. A violation is a point where the local slope blows past 1 — a spike next to a cliff. |
Note the fairness view carefully: the overestimation is relative, not absolute. The offending node can still satisfy admissibility perfectly — it lies only in comparison to what its neighbor's estimate implies.
Edges: S→A (1), S→B (1), A→C (1), B→C (2), C→G (3). Heuristic: h(S)=2, h(A)=4, h(B)=1, h(C)=1, h(G)=0. Every value is admissible — h(A)=4 ≤ 5 = true cost from A. Optimal path: S→A→C→G, cost 5.
graph LR
S["S<br/>h = 2"] -->|"1"| A["A<br/>h = 4 ⚠️"]
S -->|"1"| B["B<br/>h = 1"]
A ==>|"1 — VIOLATED: need 4 ≤ 1 + 1"| C["C<br/>h = 1"]
B -->|"2"| C
C -->|"3"| G["G<br/>h = 0"]
style A fill:#ffe3e3,stroke:#cc0000,stroke-width:3px
style G fill:#e3f6e3,stroke:#2e7d32,stroke-width:2px
linkStyle 2 stroke:#cc0000,stroke-width:3px
The red node A is the spike on the height map — its h towers at 4 while its neighbor C sits at 1, across an edge that costs only 1. The red edge A→C is where the difference quotient hits 3, blowing past the Lipschitz bound of 1.
| Step | Popped | f | What happens |
|---|---|---|---|
| 1 | S | 0+2=2 | Expands A (1+4=5) and B (1+1=2) |
| 2 | B | 1+1=2 | h(A)=4 shoved A to the back; B jumps the queue. Expands C via B: g=3, f=3+1=4 |
| 3 | C (via B) | 3+1=4 | C enters the closed set carrying a suboptimal g=3. Expands G: f=6+0=6 |
| 4 | A | 1+4=5 | Tries to reach C with g=2 — blocked by the closed set. The optimal path dies here. |
| 5 | G | 6 | Returns cost 6. Wrong. |
The culprit is the edge A→C: h(A)=4, h(C)=1, edge cost 1. The consistency check demands 4 ≤ 1 + 1 — violated by miles. Watch f along the optimal path S→A→C:
graph LR
fS["S<br/>f = 0 + 2 = 2"] -->|"+1 travel, h: 2→4"| fA["A<br/>f = 1 + 4 = 5"]
fA ==>|"+1 travel, h: 4→1"| fC["C via A<br/>f = 2 + 1 = 3 ⬇️"]
fC -.->|"never happens — C already closed"| fG["G<br/>f = 5 + 0 = 5"]
style fC fill:#ffe3e3,stroke:#cc0000,stroke-width:3px
linkStyle 1 stroke:#cc0000,stroke-width:3px
linkStyle 2 stroke:#999999,stroke-dasharray:5
f goes 2 → 5 → 3. There it is — f decreases on a route. A is the node whose optimism is out of proportion with its neighbor; the spike on the height map; the point where the slope constraint gets blown up. Three costumes, one crime.