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.