Answers.Body: <p>The 2nd and 3rd editions of the Russell and Norvig's book (which you can find on the web) do not have a figure for the pseudocode of A*.</p>
  <p>However, the <a href="https://ai.stackexchange.com/a/9554/2444">graph search</a> version of A* is equal to the pseudocode of uniform-cost search (UCS), which they provide in figure 3.14 (page 94, section 3.4.2.), but, rather than using <span class="math-container">$g$</span> (the cost of the shortest path from the start node to <span class="math-container">$n$</span>), you use <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$h$</span> is an estimate of the shortest path to the goal from <span class="math-container">$n$</span>, which should be <a href="https://ai.stackexchange.com/q/6026/2444">admissible</a> in order for A* to be optimal. See <a href="https://ai.stackexchange.com/q/9182/2444">this answer</a>.</p>
  <p>You can find a screenshot of UCS below.</p>
  <p><a href="https://i.sstatic.net/4axDt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4axDt.png" alt="enter image description here" /></a></p>
  <p>In the pseudocode, <code>PATH-COST</code> is <span class="math-container">$g(n)$</span>. When they pop from the frontier, you should pop according to <span class="math-container">$f(n)$</span> in A*. See also section 3.5 of the 3rd edition of the book.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-21T10:52:37.883Z
Answers.LastActivityDate: 2022-03-21T10:52:37.883Z
Answers.UserDisplayName: nbro
Body: <p>Can anybody point me to a link to Peter Norvig's version of the A* pseudocode. I've googled it interminably but found nothing.</p>
  <p>It's the version that uses the Unexplored/Frontier/Explored data structures. I've looked at other versions (one from CMU), but I can't see how to get from that version to Norvig's version, and it's not in any of the versions of his text!</p>
  <p>He wrote it down longhand in the online (Norvig &amp; Thrun) lectures for his Stanford AI class. Those YouTube videos have since been taken down, and I don't have an old link to find it in the Wayback Machine. If anybody has the links to the whole suite of lectures on the Wayback Machine, that would be ideal.</p>
  <p>But if a typewritten version were ever posted somewhere on the net (pdf, ppt, html, etc.), that would also be perfect.</p>
  
Tags: <reference-request><search><a-star><pseudocode>
Title: Where can I find Norvig's version of the pseudocode for the A* search algorithm?
UserDisplayName: Fred Friendly
ThreadText: # Where can I find Norvig's version of the pseudocode for the A* search algorithm?
  
  (Asked by: username_0 on 2022-03-18)
  
  Can anybody point me to a link to Peter Norvig's version of the A\* pseudocode. I've googled it interminably but found nothing.
  
  It's the version that uses the Unexplored/Frontier/Explored data structures. I've looked at other versions (one from CMU), but I can't see how to get from that version to Norvig's version, and it's not in any of the versions of his text!
  
  He wrote it down longhand in the online (Norvig & Thrun) lectures for his Stanford AI class. Those YouTube videos have since been taken down, and I don't have an old link to find it in the Wayback Machine. If anybody has the links to the whole suite of lectures on the Wayback Machine, that would be ideal.
  
  But if a typewritten version were ever posted somewhere on the net (pdf, ppt, html, etc.), that would also be perfect.
  
  **Tags:** reference-request, search, a-star, pseudocode
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-03-21. Score: 0 | Accepted answer
  
  The 2nd and 3rd editions of the Russell and Norvig's book (which you can find on the web) do not have a figure for the pseudocode of A\*.
  
  However, the [graph search](https://ai.stackexchange.com/a/9554/2444) version of A\* is equal to the pseudocode of uniform-cost search (UCS), which they provide in figure 3.14 (page 94, section 3.4.2.), but, rather than using $g$ (the cost of the shortest path from the start node to $n$), you use $f(n) = g(n) + h(n)$, where $h$ is an estimate of the shortest path to the goal from $n$, which should be [admissible](https://ai.stackexchange.com/q/6026/2444) in order for A\* to be optimal. See [this answer](https://ai.stackexchange.com/q/9182/2444).
  
  You can find a screenshot of UCS below.
  
  [![enter image description here](https://i.sstatic.net/4axDt.png)](https://i.sstatic.net/4axDt.png)
  
  In the pseudocode, `PATH-COST` is $g(n)$. When they pop from the frontier, you should pop according to $f(n)$ in A\*. See also section 3.5 of the 3rd edition of the book.
  
  
  ---
  
  