2
$\begingroup$

On page 84 of Russell & Norvig's book "Artificial Intelligence: A Modern Approach Book" (3rd edition), the pseudocode for uniform cost search is given. I provided a screenshot of it here for your convenience.

I am having trouble understanding the highlighted line if child.STATE is not in explored **or** frontier then

enter image description here

Shouldn't that be if child.STATE is not in explored **and** frontier then

The way it's written, it seems to suggest that if the child node has already been explored, but not currently in the frontier, then we add it to the frontier, but I don't think that's correct. If it's already been explored, then it means we already found the optimal path for this node previously and should not be processing it again. Is my understanding wrong?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I think this is a problem with missing brackets in pseudocode — clearly the state is only added to the frontier if it hasn't been explored already, so it would be:

if not [contains(frontier, state) OR contains(explored, state)] then

which is equivalent to your interpretation of

if not [contains(frontier, state)] AND not [contains(explored, state)] then

(according to De Morgan's Laws)

Being half-way between a programming language and natural language, this is a case where pseudocode is not quite precise enough.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .