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

• •

  Many problems can be abstracted to the problem of searching to find paths in graphs.

• •

  Breadth-first and depth-first searches can find paths in graphs without any extra knowledge beyond the graph.

• •

  $A^{\ast }$ search can use a heuristic function that estimates the cost from a node to a goal. If a graph satisfies some reasonable condition (see Proposition 3.2) and the heuristic is admissible, $A^{\ast }$ is guaranteed to find a lowest-cost path to a goal if one exists.

• •

  Multiple-path pruning and cycle pruning can be used to make search more efficient.

• •

  Iterative deepening and depth-first branch-and-bound searches can be used to find lowest-cost paths with less memory than methods, such as $A^{\ast }$, which store multiple paths.

• •

  When graphs are small enough to store all the nodes, dynamic programming records the actual cost of a lowest-cost path from each node to the goal, which can be used to find the next arc in an optimal path.

• •

  When designing a search problem for the real world, you should ensure that there are no unintended social consequences, such as the ones of Section 3.9.