Proof: every consistent heuristic is also admissible

September 6, 2009

Proof: Let $h (x)$ be any consistent heuristic, and let $c (x, y)$ be the corresponding step cost of moving from the state x to another state y. Then $h (x) \leq c (x, y) + h (y)$ by the definition of consistency. To show that h is admissible, we must show that $h (x) \leq p (x)$ where p is the path cost of x.

Suppose there is no path from x to the goal state. In this case, $p (x)$ is infinite, and satisfies that $h (x) \leq p (x)$ for any finite $h (x)$ .

Now suppose that there is some path form x to a goal state g. Let us call intermediate nodes of a shortest path $w_{1}, w_{2}, \dots w_{n}$ . So the shortest path from x to g is expressed as $(x, w_{1}, w_{2}, \dots w_{n}, g)$ .

Now consider $h (w_{n})$ . Since h is consistent, $h (w_{n}) \leq c (w_{n}, g) + h (g) = c (w_{n}, g)$ since $h (g) = 0$ . Similarly, $h (w_{n - 1}) \leq c (w_{n - 1}, w_{n}) + h (w_{n}) \leq c (w_{n - 1}, w_{n}) + c (w_{n})$ . By induction on n, we obtain $h (w_{k}) \leq c (w_{k}, w_{k + 1}) + \dots + c (w_{n - 1}, w_{n}) + c (w_{n}, g)$ for any k between 1 and n-1. But because $(x, w_{1}, w_{2}, \dots w_{n}, g)$ is a shortest path, $p (w_{k}) = c (w_{k}, w_{k + 1}) + \dots + c (w_{n - 1}, w_{n}) + c (w_{n}, g)$ so that $h (w_{k}) \leq p (w_{k})$ as desired.

Q.E.D.

R. Niwa

We ought never to allow ourselves to be persuaded of the truth of anything unless on the evidence of our own reason – René Descartes

Proof: every consistent heuristic is also admissible