Go backward to Question 1
Go up to Top
Go forward to Question 3

Question 2

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.

Solution

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 every node, whereas breadth-first search expands three nodes:
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:
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.

David Poole