Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I use the A* search algorithm to to search for the shortest path from S to G.
The evaluation function is $f(n) = g(n) + h(n)$.
Since node A and B have the same estimated total cost, I choose to go node A.Then, the $f(n)$ of B is 8, C is 7, G is 10. After expanding C, $f(n)$ of G is 7. Therefore, the path is S-A-C-G with total cost 7.
However, there is a lower cost path S-B-G with $f(n) = 6$.
Is the path S-A-C-G still optimal or I did the search in the wrong way?
The A* algorithm requires that its heuristic function $h(n)$ is admissible for all $n$, meaning that it should never overestimate the (unknown) true cost from a node to the goal. This assumption appears to be violated in your example for nodes $S$, $A$, and $B$. Only for $n = C$ and $n = G$ is the heuristic function $h(n)$ admissible, but it should be for all nodes.
This is why the algorithm seems to be resulting in suboptimal paths for you.
A good example of an admissible heuristic function in 2D environments is often the Euclidean distance (straight-line distance). Unless you start involving strange things such as teleportation, this heuristic is always admissible (you can never get anywhere faster than by following a straight line). Although in your drawing, it seems like this wouldn't work. It doesn't look like your drawing was drawn "correctly". Some short paths seem to have higher costs than longer paths (visually).
