Hi, I have a question about the A* algorithm: I have a very simple diagram, it has 3 nodes, node 0 is the starting node, node 2 is the finishing node. The cost of going from node 0 to node 2 is 50, and from node 0 to 1 and 1 to 2 is 10. As seen, all of the are connected to each other. What I have understood, and following the algorithm, what I should do is this: - Put the starting node (node 0) in the open list - Take the node with the minimum F in the list, in this case, node 0, the only one and put it in the close list - Add node 2 to the open list. Since this is the finishing node, I should stop the algorithm because the end has been found. - The path is n0 - n2 But the problem here is that I have found a path that is not the cheapest one (its cost is 50, and path n0 - n1 - n2 is only 20). Would I solve this problem by examining all nodes in open list until the F cost of every of them is higher than the path found? Thanks in advance

Quote: Original post by evans87
- Put the starting node (node 0) in the open list
- Take the node with the minimum F in the list, in this case, node 0, the only one and put it in the close list
- Add node 2 to the open list. Since this is the finishing node, I should stop the algorithm because the end has been found.
- The path is n0 - n2

You're missing a vital step, which is to add the children of the node popped from OPEN into the OPEN list. In other words, you're not actually searching anything. Take a look at this pseudo-code...

Add 'start' to OPENwhile (not(empty(OPEN)))   pop 'best' from OPEN   if ('best' == 'goal') return reverse_path('goal','start')   push 'best' to CLOSED   for_each (child_of('best'))      compute f('child')      if CLOSED contains 'child' AND f('child') < f(CLOSED(child))         replace CLOSED(child) with 'child'      else if OPEN contains 'child' AND f('child') < f(OPEN(child))         replace OPEN(child) with 'child'      else         push 'child' to OPENreturn FAIL

This function returns under two conditions: 1, the goal is found and the path is returned (correctly reversed by traversing from goal back to start recording the sequence of nodes); or 2, no path is found to goal and all nodes are exhausted from OPEN, in which case the function returns a FAIL condition.

The testing of whether the current 'child' node already exists in CLOSED or OPEN is necessary to ensure you keep only the lowest cost path through each node.

I hope this helps.

Regards,

Timkin

[Edited by - Timkin on April 15, 2008 7:36:59 PM]

To put it another way, you shouldn't be testing what you add to the Open list to see if it's the goal. You should be testing what you take off the Open list to see if it's the goal. In your example, by the time you come to take the 2nd node off the Open list, it will consist of Node 1 and Node 2, and Node 1 will be picked because it has a lower F score. You'll then end up overwriting the instance of Node 2 with a revised, lower cost, pulling that off the Open list, and finishing.

Thanks a lot, it's clear now. My misunderstanding was caused by a bad traslation of an A* explanation in a site.