• Advertisement
Sign in to follow this  

A* confusion

This topic is 3297 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm reading a section in a book dedicate to pathfinding. It shows the following diagrams: http://img369.imageshack.us/img369/5474/61664125rr0.jpg The bottom part of the image is intended to be the first part of the image with 2 more iterations completed. I can't seem to find out why the bottom diagram is at C. My impression was that A* is supposed to find a path based on a heurisitic, not the shortest path. Well, if that were the case, then the next steps that should have happend (as of the above diagram): 1. Select E to process, as it has the smallest estimated total cost so far out of all the open nodes 2. Once E has been processed, select G to process (since it is now in the open nodes list), as it has the smallest estimated total cost so far out of all the open nodes 3. Nothing to process, so finish with G. So why the hell does the bottom diagram show that C is getting processed after process E was processed? That doesn't make any sense since the LOWEST estimated total cost after E is 4.4 (which is associated with G), not 4.8 (which is associated with C). Am I right or have I just gone bonkers? - Kaz

Share this post


Link to post
Share on other sites
Advertisement
It looks like the diagram is wrong to me. The heuristic is overestimating the cost to the goal, and as a result A* doesn't find an optimal path in this case.

Share this post


Link to post
Share on other sites
Is my reasoning correct for WHY it's wrong??

My understanding is that you want to find a path that's okay using the heurisitc, not so much an optimal/minimal/shortest/whatever-you-want-to-call-it path. In this way it is supposed to help reduce the fill of the algorithm? because it considers less nodes out of the entire graph, yet still gives a pretty good result?

Share this post


Link to post
Share on other sites
It depends on the heuristic. If the heuristic always underestimates the cost, A* is guaranteed to find an optimal path. If the heuristic overestimates, then an optimal path is not guaranteed.

For example, if you set the heuristic to always return 0, you will be simulating Dijkstra's algorithm, which will find the optimal path.

Share this post


Link to post
Share on other sites
You mean if it under/over estimates in terms of the real total cost?

Regardless. am I right in my reasonings put in my initial post as to why that diagram is wrong????

Share this post


Link to post
Share on other sites
I think you are correct. The next node to be expanded should be the one with lowest estimated total cost to the goal, and since the goal node has a lower estimated cost it should be expanded before node C.

Share this post


Link to post
Share on other sites
does the book show (or tell) what is the heuristic function doing? I mainly ask this because the heuristics to the start node is 4.2, which to me sounds dead wrong since the f(x) of the start node should be 0 (at least the way I see it).

Share this post


Link to post
Share on other sites
As it turns out:

The diagram isn't so much about the heuristic as it is about showing that a closed node can change if it gets encountered again. I showed the diagram to the author and he confirmed that C shouldn't have been accessed and that it should have gone straight to the goal node.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement