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

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 ﬁrst 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.

-

closed as no longer relevant by Andrés E. Caicedo, Henry Cohn, Felipe Voloch, quid, Bill JohnsonDec 11 '12 at 1:10

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I don't know that we can do anything for you in preparing for your examination. Your question is very oddly worded, you really need some help in person to clear up some, well, confusion. Meanwhile, I can recommend a book by Judea Pearl called "Heuristics: Intelligent search strategies for computer problem solving." There are also websites that allow one to play with A* on a small grid, say 12 by 12, with Manhattan distance as the ambient distance function. – Will Jagy May 16 '10 at 4:32