0
$\begingroup$

I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example:

Take a 2x2 grid, in which you can only move in one of 4 (orthogonal) directions (no diagonal movement). Denote the node at (0, 0) by A, the node at (1, 0) by B, the node at (0, 1) by C, and the node at (1, 1) by D (so that it looks like C D A B The weight going from A to B is 3, the weight going from A to C is 2, the weight from B to D is 1, and the weight from C to D is 3. Let the start node be A and the goal be D. Let our heuristic simply be Euclidean distance (or Manhattan distance, both produce the same result in this instance).

So, if my understanding of A* is correct, we start with an open set containing only A, so we pop A. It's neighbours are B and C, which have g values g(B) = 3, g(C) = 2, and h values h(B) = 1, h(C) = 1. So the f-values are f(B) = 3 + 1 = 4, f(C) = 2 + 1 = 3. Add these to the open set.

Now the open set is {B, C}. Since C has the lowest f-value, we pop it. C's only neighbour is D, which is the goal. So we stop, having found "the best path" from A to D.

This is clearly wrong. The algorithm should output the path A->B->D, which has total weight 4, but instead it stopped prematurely.

Now, if we were to have a larger graph, then after exploring the path A->C->D we would go back to B (which is still in the open set), notice that the path A->B->D to D gives D a lower f-value than A->C->D, so we update D's f-value, giving the correct fastest path. Alternatively, we could simply continue running A* until the open set is empty, rather than ending prematurely as soon as we've found the goal (however, this doesn't agree with Wikipedia's pseudocode implementation of A*).

Are my ideas correct, or am I missing something about how A* is typically implemented?

$\endgroup$
4
$\begingroup$

Your misunderstanding is that A* doesn't return success until it pops a goal node, in your terminology.

So, in your example, when it pops $C$, it puts $D$ in the open list, with quite a high value. It then pops $B$ and puts $D$ in the open list again, with a lower value. So the first time that $D$ is popped will be from the route $A\to B\to D$, as it should be.

$\endgroup$
  • 1
    $\begingroup$ Ohhhh, so you add the goal to the open set, then if the node you popped from the open set is the goal, and only then, you end. Thanks for clarifying! $\endgroup$ – user3002473 Mar 29 '18 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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