Note: this post extends the concept of multiple-path pruning presented in Poole and Mackworth (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)\).