How to prove that the A* Algorithm is admissible (by induction)? [closed]

Question

I've been struggling with this question for the past hour but I can't seem to get it.

We begin with the start node S. But what should be the induction hypothesis?

EDIT: My bad, I was referring to the Manhattan Distance heuristic.

I am preparing for an exam in a Robotics course I took at university and we have actually been given what's supposed to be the induction proof of the heuristic's admissibility. It goes like this:

The base case: The base case is the first node to be added to the closed list which is the star t node. Here the G value is 0 which is optimal.

The Inductive Case: For the inductive case we assume that all closed nodes so far have optimal G values. We will then consider the next node to be closed. That is we must consider the node x from the open list with the smallest F value.

We are assuming (for induction) that all closed nodes so far have optimal G values. Consider the node x from the open list with the smallest F value. Let c be the last closed node on the shor test path from the star t node to x and let y be the open node following c in this path.

We know that G(y ) is optimal since its value was updated when c was added to the closed list. If y is x then we are done.

Otherwise y != x . We know that F (x ) ≤ F (y ) by choice of x , and that |H (y ) − H (x )| ≤ d (x , y ) since H is admissible. Combining these two inequalities we have that G(x ) ≤ G(y ) + d (x , y ).

Since y is on the best path to x and G(y ) is optimal, G(x ) ≤ G(y ) + d (x , y ) means that G(x ) is optimal.

Answer 1

Your question is a little confusing: it's the heuristic estimate of distance to the destination that's supposed to be admissable in A*, not the algorithm itself. I assume what you actually mean is: suppose that you have a consistent heuristic, then how do you prove that A* finds the shortest path?

My view of A* is that it is really no different than Dijkstra's algorithm, using different weights. In this view, the new weight of an edge uv is (old weight of uv)-(estimated distance from u to destination)+(estimated distance from v to destination); it's easy to see that changing the weights in this way doesn't change which paths are the shortest. So just like Dijkstra all you need is that the new weights are non-negative (this is basically the definition of a consistent heuristic), and you don't need a separate proof that A* is correct: it's the same mathematical fact as the correctness of Dijkstra. See this blog post for a more detailed explanation.

There are versions of A* that are less like Dijkstra and that work with heuristics that are admissable but not consistent but you'll have to do something else for those.