None
EN
Pruning for A* heuristics
['Ragnar', 'Groot Koerkamp']
home on CuriousCoding
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. 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.