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.
1. 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:
2. 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:
3. 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.
4. 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