<p>what you mean is <em>uniform cost search</em>. see <a href="http://en.wikipedia.org/wiki/Uniform-cost_search" rel="nofollow">uniform cost search</a> 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 <em>existing node</em> 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 &amp; the books pseudocode could be improved and some mention of the logic of that line included to avoid confusion.</p>

CC BY-SA 3.0
2012-02-23T17:38:53.037Z
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.
IsaacS
CC BY-SA 3.0
2012-02-23T16:50:42.753Z
2012-02-23T17:07:34.650Z
2012-02-23T17:07:34.650Z
vzn
<p>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).</p>

<p>In the book <a href="http://aima.cs.berkeley.edu/" rel="nofollow">"Artificial Intelligence Modern Approach" (Russell, Norvig)</a> 3rd ed., in Figure 3.14 in page 84, is the 2nd last line error (this is not on <a href="http://aima.cs.berkeley.edu/errata.html" rel="nofollow">current errata</a>) ?</p>

<pre><code>else if child.State is in frontier with higher PATH-COST then
  replace that frontier node with child
</code></pre>

<p>My guess is:</p>

<pre><code>else if child.State is in frontier with lower PATH-COST then
  replace that frontier node with child
</code></pre>

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

<p>Correct me if I'm wrong. Thank you.</p>

CC BY-SA 3.0
2012-02-23T17:59:55.287Z
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.
Kaveh
CC BY-SA 3.0
2012-02-23T18:00:54.583Z
There are a number of Q&A sites linked in the [FAQ] where your question might be appropriate (but read their FAQ before posting).
Kaveh
<ai.artificial-intel>
Error in the book Artificial Intellingence Modern Approach (at Un-informed search)?
IsaacS
# Error in the book Artificial Intellingence Modern Approach (at Un-informed search)?

(Asked by: username_0 on 2012-02-23)

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.

**Tags:** ai.artificial-intel

> **Comments:**
> **username_1**: 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.  
> **username_1**: There are a number of Q&A sites linked in the [FAQ] where your question might be appropriate (but read their FAQ before posting).  

---

## 1 answers

### Answer by username_2 on 2012-02-23. Score: 0 | Accepted answer

what you mean is *uniform cost search*. see [uniform cost search](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  

---

