A* algorithm example - is it correct

Question

I've following graph:

If I use A* algorithm, I get this sollution:

                      S (0+1=1)
                    /          \
                  /             \
          a(3+3=6)                b(2+3=5)
        /    |    \                /       \
      /      |     \              /         \
  c(4+0=4) b(6+3=9) d(6+0=6)    d(5+0=5)    c(7+0=7)

Question: which solution will we find, using algorithm A* and heuristic estimates(see graph)

Sollution:

• select b(=5):

                    S (0+1=1)
                  /          \
                /             \
        a(3+3=6)               b(2+3=5)
  

• select d(=5):

                   S (0+1=1)
                  /          \
                /             \
        a(3+3=6)                b(2+3=5)
                                 /       \
                                /         \
                              d(5+0=5)    c(7+0=7)
  

• Stop searching - because "cost 5" is less than a(3+3=6) -> we don't search for other solutions ? Solution is: s-b-d, cost = 5

Is it right ?

Solution

Theoretically looking at what you have written it is correct. However, there is one very important property of graphs you run A* on that should be valid so that you know the algorithm produces optimal solution: The heuristic function you use should be optimistic, i.e. never overestimate the real distance to the goal. If I get it correctly you have couple of goal nodes C and D and the problem is that the heuristic value of A is not optimistic, actually it overestimates (the path from A to the goal node C is only 1, which is less than h(A) = 3). This is why you actually do not get optimal solution.

Comments

[OldFox]

Ok, so s-b-d, cost = 5 is solution in this case. Thanks a lot for the explanation.