0
$\begingroup$

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? enter image description here

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thank you. I have a clearer understanding now. $\endgroup$ – HarryMoore Dec 9 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.