Prev Up Next
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

  1. What is the final path found? s -> a -> b -> g.
  2. How many nodes were expanded? 9.
  3. 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.
  4. 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

Prev Up Next