Please let me know if this is not appropriate question to ask here (I hope not but afraid since this isn't really theoretical question).

In the book "Artificial Intelligence Modern Approach" (Russell, Norvig) 3rd ed., in Figure 3.14 in page 84, is the 2nd last line error (this is not on current errata) ?

else if child.State is in frontier with higher PATH-COST then
  replace that frontier node with child

My guess is:

else if child.State is in frontier with lower PATH-COST then
  replace that frontier node with child

This is pseudocode for Un-informed, breadth search, where the search candidates are in a list called frontier, which is lower ordered by PATH-COST. I wonder the suspected code would update the list with the node with higher cost.

Correct me if I'm wrong. Thank you.

  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Feb 23 '12 at 17:59
  • $\begingroup$ There are a number of Q&A sites linked in the FAQ where your question might be appropriate (but read their FAQ before posting). $\endgroup$ – Kaveh Feb 23 '12 at 18:00

what you mean is uniform cost search. see uniform cost search where the pseudocode matches the book which is not in error. that line's logic replaces the frontier node with a newly discovered path to the same node with less weight. the wikipedia article includes a sample run which unfortunately does not exercise that line (adj that article to do that would be an improvement). wikipedia currently uses the line "if n is in frontier with higher cost replace existing node with n" where the book statement you cite is clearer. "with higher path cost" refers to the higher path cost in the frontier. it seems that both wikipedia & the books pseudocode could be improved and some mention of the logic of that line included to avoid confusion.

| cite | improve this answer | |
  • $\begingroup$ Thanks, that makes clear what the code is describing, and I see it is correct although confusing. Btw, I don't get why it's called uniform-cost search...I'm seeing the cost b/w nodes varies in the example both in the book and Wikipedia. Think this should be asked separately though. $\endgroup$ – IsaacS Feb 23 '12 at 17:38

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