# Pruning for A* heuristics

Note: this post extends the concept of multiple-path pruning presented in Poole, David L. and Mackworth, Alan K. (2017).

Say we’re running A* in a graph from $$s$$ to $$t$$. $$d(s,t)$$ is the distance we are looking for.

An A* heuristic has to satisfy $$h(u) \leq d(u, t)$$ to be admissible: the estimated distance to the end should never be larger than the actual distance to guarantee that the algorithm finds a shortest path.

We can do better: it is sufficient that $$h(u) \leq d’(u,t)$$, where $$d’(u,t)$$ is the length of the shortest path from $$u$$ to the end that does not use any already expanded state. Note that this restriction is looser than the original one, since $$d’(u,t)\geq d(u,t)$$ trivially holds.

Proof
Let $$x$$ be an already expanded state, and let $$u$$ be an unexpanded state where we are evaluating $$h$$.

The shortest path through $$x$$ will have length $$l = d(s, x) + d(x, t)$$, where $$d(s,x)$$ is already known since $$x$$ was expanded.

If the global shortest path goes through $$x$$, its length is $$l$$, and we cannot do better by going via $$u$$: replacing $$d(s,x)$$ by $$d(s,u) + d(u,x)$$ can not decrease the distance (by the triangle inequality, or by definition of $$x$$ already being expanded).

Thus, in an unexpanded state $$u$$, taking a path through an already expanded state will never lead to a global minimum. (It may give the shortest distance from $$s$$ to $$t$$ via $$u$$, but that is not what we are looking for.)

Conclusion: In order for a path through $$u$$ to be a candidate for the global minimum, it has to avoid all already expanded states. The heuristic $$h$$ we use can reflect this, and is allowed to satisfy $$h(u) \leq d’(u,t)$$.

## References

Poole, David L. and Mackworth, Alan K. (2017). Artificial Intelligence, Cambridge University Press.