Explain the uniform cost search pseudocode.
On page 84 of Russell & Norvig 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 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?
I think this is a problem with missing brackets in uniform cost search 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.