families of search algorithms
- breadth-first
- depth-first
- best-first
problem: go from s to e
breadth-first
[breadth-02.fig]
expand in all directions until finding the goal
when e is reached, the path is optimal
lot of nodes explored
depth-first
[breadth-03.fig]
go in one direction as much as possible
when impossible, go back and take other paths
first path to e may not be optimal
others
best-first: expand first the node with a minimal measure
search backwards from the goal