Module 5 (Search Issues)

Assignment 5

- Which of the following methods will find a path from
*mi*to*cp*without loop detection or multiple-path pruning: depth-first search, A* search, breadth-first search, best-first search. - For A* search, how much saving (in the number of nodes expanded) is obtained by using loop detection and using Multiple-path pruning? (Give the number of nodes selected from the frontier with and without each of the two pruning methods).
- Is a backward search more efficient than a forward search for breadth-first search or A*? Explain why.
- How could a bi-directional search help? Explain. What forward and backward searches would be useful?
- Give the distance table created by dynamic programming to find a
path from
*mi*to*cp*.

Suppose *mod(Mod,Prereqs,Teaches)* is true if module *Mod* covers the elements
of the list *Teaches* and requires that the students have already
covered the elements of the list *Prereqs*.

Suppose we decide to represent the problem of designing custom courses as a search problem wheremod(m1,[],[intro]). mod(m2,[intro],[semantics,symbols]). mod(m3,[symbols,semantics],[proofs]). mod(m4,[intro],[search]). mod(m5,[search,symbols],[advanced_search]). mod(m6,[search,semantics],[csp]). mod(m7,[symbols,semantics],[kr]). mod(m8,[proofs],[metainterpreters]). mod(m9,[semantics],[actions]). mod(m10,[actions,metainterpreters,search],[planning]). mod(m11,[search,metainterpreters],[dtlearning]). mod(m12,[csp],[nnlearning]).

- the nodes are lists of topics that have been covered and
- the arcs are labelled with modules. Suppose
*L*is a node, and*M*is a module such that*mod(M,P,T)*, where*P*is a subset of*L*(every element of*P*is in*L*), and*T*is not a subset of*L*, then*L U T*is a neighbour of*L*, with the arc labelled with*M*.

For example, suppose an instructor wants to cover *nnlearning*, and
*proofs*, then any node that contains both *nnlearning* and *proofs*
is a goal node. Then a solution is the path that starts with *[]*, then has arc
labelled with *m1* to node *[intro]*, then has arc *m4* to
node^{1}
*[intro*, *search]*, then has arc *m2* to node
*[intro*, *search*, *semantics*, *symbols]*, then has arc *m6* to node
*[csp*, *intro*, *search*, *semantics*, *symbols]*, then has arc *m12* to
*[csp*, *intro*, *nnlearning*, *search*, *semantics*, *symbols]*, then has arc *m3*
to node *[csp*, *intro*, *nnlearning*, *proofs*, *search*, *semantics*, *symbols]*,
which is a goal node.

- Draw the search graph to depth four. This should include all paths from the start node that contain three or fewer arcs.
- Is loop checking useful? Explain.
- Is multiple path pruning useful? Explain.
- Is backward search better than forward search for this problem? Explain.
- 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.^{*}

**(1)**- Note that here we are representing sets of nodes as lists sorted alphabetically.

David Poole