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?

$\endgroup$
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$
  • $\begingroup$ Thanks. After I posted this, I realized that it might just be a semantics thing. $\endgroup$ – Iamanon Feb 7 at 15:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.