0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Will Jagy
    May 16, 2010 at 4:32

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I edited my question, I am sorry for the confusion. :) $\endgroup$
    – SebKom
    May 15, 2010 at 21:29

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