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
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.
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999