Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

## 3.8 Review

The following are the main points you should have learned from this chapter:

- Many problems can be abstracted as the problem of finding paths in graphs.
- Breadth-first and depth-first searches can find paths in graphs without any extra knowledge beyond the graph.
*A*search can use a heuristic function that estimates the cost from a node to a goal. If this estimate underestimates the actual cost,^{*}*A*is guaranteed to find a least-cost path first.^{*}- Iterative deepening and depth-first branch-and-bound searches can be used to find least-cost paths with less memory than methods such as
*A*, which store multiple paths.^{*} - When graphs are small, dynamic programming can be used to record the actual cost of a least-cost path from each node to the goal, which can be used to find the next arc in an optimal path.