If you have a graph of nodes, and in the OPEN list appear a cycle (duplicated node), what of the nodes duplicated can be deleted? example: Priority queue OPEN (ordered by f): C(g=40,h=10,f=50)->E(g=50,h=13,f=63)->D(g=53,h=14,f=67)->C(g=58,h=10,f=68) .... in this case, I have to delete the first C node, or the second?, although the path followed by one of the two will be shortest than the other (independent of f value), but don''t know this when is searching.

I think you''ve implemented the A* algorithm incorrectly. In the case you''ve shown below C->E->D->C, C should already be closed by the time you reach it again, so it shouldn''t even be considered.

It is possible to find loops during any search routine. Whenever you expand a node to create its children, you need to check as to whether the children already exist in your OPEN list AND your CLOSED list.

In the situation where the node already exists, you have two data objects that represent the same node in the search tree. Presumably one has a lower cost than the other. You need to discard the one with the higher cost. If that is the node that is already within the open or closed list, then you need to make sure you correctly graft the new node into the appropriate list. That means setting the parent of the new node to be the parent of the node to be discarded and setting the parent of the children of the node to be discarded as the new node. Make sense?

This will solve your problem.

Cheers,

Timkin

yes, this solve my problem, thanks very much.