Solution

1. Draw the search graph to depth four. This should include all paths from the start node that contain three or fewer arcs.

   

2. Is loop checking useful? Explain.

   No. There are no cycles in this graph. This is because you can't do a module if you have already covered all of the topics. And you never forget topics.

3. Is multiple path pruning useful? Explain.

   Yes. There are many multiple paths. In particular, reorderings of modules produce the save nodes.

4. Is backward search better than forward search for this problem? Explain.

   No, not with the nodes as defined here. This is because there are too many goal nodes. For example, if the goal were to cover nnlearning and proofs, every set of topics that includes these two would be a goal node (there are 2¹1=2056 of these). This would mean that you have too many start nodes in the forward search.

5. Suppose we want to use A^* search. Give a non-trivial heuristic function that is an underestimate of the actual distance from a node to a goal.

   We assume here that we are trying to minimise the number of topics taught.

   The simplest is h(n) is the number of topics in g that are not in n. This isn't quite right, as one module (module m2) covers two topics. So we should divide this number by two or somehow make sure we don't count both semantics and symbols. This would then be an underestimate of the number of topics that needs to be taught.