Where can I find Norvig's version of the pseudocode for the A* search algorithm?

Question

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.

Answer 1

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 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 in order for A* to be optimal. See this answer.

You can find a screenshot of UCS below.

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.