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.