Prev Up Next
Go backward to Question 1
Go up to Top
Go forward to Footnotes

Question 2

Publish-on demand for textbooks and online courses is becoming more commonplace. We want to be able to deliver custom versions of cs322 for use at other places who may only want to use a subset of the modules, perhaps in different orders. Here we consider the problem of delivering a course to suit the goals of an instructor as a search problem.

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.

mod(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]).
Suppose we decide to represent the problem of designing custom courses as a search problem where The start node is labelled with the empty list []. A goal node is a node that includes all of the topics the instructor wants to cover.

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 node1 [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.

  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.
  3. Is multiple path pruning useful? Explain.
  4. Is backward search better than forward search for this problem? Explain.
  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.
  • Solution

  • David Poole

    Prev Up Next