# Problem understanding Nilsson's general graph search and A* algorithm

I'm reading several books that present A* algorithm. More precisely, I'm Nilsson's "Artificial Intelligence a New Synthesis" and a textbook on problems of artificial intelligence which is written in spanish.

The following description of A* algorithm is from Nilsson:

I'm having some trouble with step 6. It says:

Expand node n, generating the set M of its successors that are not already ancestors of n in G

To put you I context, G is the search graph while Tr would denote the search tree.

So, my question is: is this description of the algorithm right? In my opinion it should be instead:

Expand node n, generating the set M of its successors that are not already ancestors of n in Tr

To help you understand my concern I show you one step of the algorithm as done in the other book:

In this picture the node that is going to be expanded is D. The dashed line shows that F is an ancestor of D in G. The black line to I says that I is an ancestor of D in the search tree Tr and of course in the search graph.

In this picture we see that when expand D we take into consideration F that was and ancestor of D in G (which contradicts Nilsson's step).

I hope I explained myself clearly. If you need any other details please just comment.

• It seems from the snippet you reproduce from Nilsson's book that "been in $G$" is interpreted as not been on OPEN or CLOSED (see point 7). However, it seems to me that in the example provided F is already in CLOSED as there are dashed lines from it to B. As point 7 explains pointers are re-forwarded in case a cheapest path has been found. Not really sure if I'm interpreting the figure correctly, but it seems there is a path of length 8 from F to I going through D which is cheaper than going through B (which takes 10 units). Do this answer the question? If not let me know ... – Carlos Linares López Sep 1 '16 at 14:24