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.
