# Optimality of A* search

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.