**Go up to** 4 Generating Graphs Good for Different Search Strategies

## Solution to generating graphs

In all of these graphs, we assume that we are on a plane, with
Euclidean distance (straight-line distance) as the arc cost and as the
heuristic function. We also assume that the neighbours are ordered
from left to right. The start node is *s* and the goal node is *g*.
- Give a graph where depth-first search is much more efficient (expands fewer nodes)
than breadth-first search.
Here depth-first search expands five nodes, whereas breadth-first
search expands every node:

- Give a graph where breadth-first search is much better than
depth-first search.
Here depth-first search expands every node, whereas breadth-first
search expands three nodes:

- Give a graph where A
^{*} search is more efficient than either
depth-first search or breadth-first search.
Here depth-first search and breadth-first
search expand every node, whereas A^{*} search expands 4 nodes.

- Give a graph where depth-first search and breadth-first search
are both more efficient than A
^{*} search.
Here depth-first search expands three nodes, breadth-first search
expands 4, yet A^{*} search expands every nodes.

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