**Go backward to** Solution to part (a): Depth-first search

**Go up to** 3 Comparting Different Search Strategies

**Go forward to** Solution to part (c): Least-cost-first search

## Solution to part (b): Breadth-first search

- What is the final path found?
*s -> a -> b -> g*.
- How many nodes were expanded?
9.
- Explain why it selected
nodes during the search that were not on the shortest path from
*s* to
*g*.
It selects all nodes that are two steps from the start node,
irrespective of where the goal is, before it expands nodes that are
three steps away and finds the goal.
- Explain why it may have been led astray in the final solution.
It finds the path with the fewest arcs, not the shortest path.

Computational
Intelligence online
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999