Why do admissible functions allow $A^*$ to retain correct shortest path computations?

Question

I was reading about how to use $A^*$ and was told that:

A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$.

I was wondering why such a condition guarantees that the shortest paths can still be computed.

Its clear to me if the heuristic is defined as with the help of a potential function $\lambda(u)$:

$$ h(u) = \lambda(u) - \lambda(s) $$

and the new weights are defined as (i.e. the potential function is feasible):

$$ w^*(u,v) = w(u,v) + h(u) = w(u,v) + \lambda(u) - \lambda(s) $$

then if we have $w^*(u,v) \geq 0$ with that heuristic then its clear that shortest paths are retained (because of telescoping series).

However, otherwise, I can't see why admissible function would retain shortest paths or what the motivation is to use admissible function with the property $h(u) \leq \delta(u,t)$. Why is that?

Usually heuristics tilt search algorithms to better paths, how do admissible function attain this?

Answer 1

Look at it this way:

The heuristic function lets us avoid exploring subpaths that we know are too long.

Suppose we're trying to get from $u$ to $t$. We're running our search, and the best path from $u$ to $t$ so far has length $UB$. We know it takes at most $UB$ to get to $t$.

Now, we see a vertex $v$. If we've found $v$, then we know the exact shortest path from $u$ to $v$. Call this $k$.

We want to know if we should bother looking at the shortest path from $v$ to $t$. So we ask, can it possibly be better than our best so far? So, we check our heuristic. We know that the distance from $v$ to $t$ is at least $h(v,t)$. So if $k + h(v,t) > UB$, then we don't need to even bother expanding $v$, since there's no way it will be better than existing paths to the goal.

This is only safe if $h$ is admissible. But note also that, the larger $h$ is, the more paths we will be able to eliminate. So we have "Price is Right" rules: our goal is always to get $h$ as close to the actual distance function as we can, but we are never allowed to go over.

Dijkstra's is just A* with the heruistic of $h(x,y) = 0$: we ignore vertices if the distance to them from the start is farther than the best distance to the end so far. But we can do a lot better than this if we have a lower-bound on the distance between two vertices, since we can eliminate even more paths.

A common heuristic in a path-finding graph is to use euclidean distance: the shortest road between two points is never shorter than the distance between those two points. Then, our heuristic lets our algorithm eliminate nodes which are close to the initial node if they take us too far away from the final node.

If you're trying to get from Seattle to New York, Dijkstra's might try to go through Portland, because it's close to Seattle. But A* with a Euclidean heuristic sees that this takes you out of your way too much, and can avoid this path.