Example algorithm * - this is correct

Question

I have the following graph:

If I use the A * algorithm, I get this permission:

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: what solution will we find using the A * algorithm and heuristic estimates (see graph)

humane:

• 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 the search - because the “cost 5” is less than (3 + 3 = 6) → we are not looking for other solutions? Solution: sbd, cost = 5

Is it correct?

Answer 1

Theoretically, looking at what you wrote is correct. However, there is one very important property of the graphs that you run A * that must be valid so that you know that the algorithm gives the optimal solution: the heuristic function that you use should be optimistic, i.e. Never overestimate the real distance to the target. If I understand correctly, you have a couple of node nodes C and D, and the problem is that the heuristic value of A is not optimistic, in fact, it overestimates (the path from A to the target node C is only 1, which is less than h (A ) = 3). That is why you are not really getting the optimal solution.