A* algorithm example explained I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a new node. So every time the code with the smallest f(n) from the root is expanded. However, I am confused about the backtracking of the algorithm when it does not find the best solution. I tried to follow the example explained here. Therefore, by only using the f(n) the algorithm should have expanded: S-B-C-G. Firstly B then C and then G. Then declare that find a solution. How, the backtracking works?

The example is as follows:


In the left, there is the graph and in the table is the heuristic cost. What is going to be the a star expand in this graph?
A* doesn't backtrack. It just keeps expanding the node with the least value of&nbsp;$f$ until it finds a solution. The properties of the heuristic used guarantee that the first solution found is optimal.