2
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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 ... $\endgroup$ – Carlos Linares López Sep 1 '16 at 14:24

Your Answer

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

Browse other questions tagged or ask your own question.