Go backward to 3 Comparting Different Search Strategies
Go up to Top
Go forward to 5 Arc Consistency
4 Generating Graphs Good for Different Search Strategies
For each of the following, give a graph that is a tree (there is at
most one arc into any node), contains at most 15
nodes, and has at most two arcs out of any node.
You must draw the graph and show the order of the neighbours (this is
needed for the depth-first search). Either give the arc costs and
heuristic function or state explicitly that you are drawing the graph
to scale and are using Euclidean distance for the arc costs and the
- Give a graph where depth-first search is much more efficient (expands fewer nodes)
than breadth-first search.
- Give a graph where breadth-first search is much better than
- Give a graph where A* search is more efficient than either
depth-first search or breadth-first search.
- Give a graph where depth-first search and breadth-first search
are both more efficient than A* search.
material, ©David Poole, Alan Mackworth and Randy Goebel, 1999