Up
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

Up