1 Question One
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.
(a) Give a graph where depth-first search (DFS) is much more efficient (expands fewer nodes) than breadth-first search (BFS).
(b) Give a graph where BFS is much better than DFS.
(c) Give a graph where A* search is more efficient than either DFS or BFS.
(d) Give a graph where DFS and BFS are both more efficient than A* search.
You must draw the graph and show the order of the neighbors (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.
1
2 Question Two
Progress is made in science by observing a phenomenon of interest, making hypotheses and testing the hypothesis either empirically or by proving theorems.
For this question you are to think about the effect of heuristic accuracy on A* search. That is, you are to experiment with, and think about how close h(n) is to the actual distance from node n to a goal affects the efficiency and accuracy of A*. To get full marks you must at least invent one (plausible, nontrivial) conjecture and either prove it and show some empirical evidence for your answer or show that it is false. Your answers need to be precise (e.g., don’t say “it works better”, but say something like “it always works better”, “it sometimes works better” or “it works better in a majority of cases”).
(a) What is the effect of reducing h(n) when h(n) is already an underestimate?
(b) How does A* perform when h(n) is the exact distance from n to a goal?
(c) What happens if h(n) is not an underestimate? You can give an example to justify your answer.
One way to vary h(n) is to use the AIspace.org search applet with the automatic node heuristics (under the search options menu) turned on, then turn it off and change heuristic values. There are ways to change all heuristic values.
You can also use other tools (even implement A* algorithms by yourself) to do experiments.
If your conclusion is based on experiments, please give some details about how you conduct the experiment.
