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.
