**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.
- 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
depth-first search.
- 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.

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
heuristic function.

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