Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this 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
add comment

closed as no longer relevant by Andres Caicedo, Henry Cohn, Felipe Voloch, quid, Bill Johnson Dec 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.

1 Answer

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.

share|improve this answer
    
I edited my question, I am sorry for the confusion. :) –  SebKom May 15 '10 at 21:29
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.