Assignment 3

Due Tuesday, January 26th in class.

  1. Rewrite the GeneralSearch algorithm to use recursion, rather than iteration. Then compare the running time and memory used between your recursive and the original iterative version for 2 missionaries, 2 cannibals and 3 missionaries, 3 cannibals, using breadth-first search.

    The Common Lisp macro time makes it easy to learn the time and memory used by your functions:
    (time (solve prob-2M2C #'BREADTH-FIRST-RECURSIVE))

  2. AIMA 3.16
  3. AIMA 4.7
  4. AIMA 4.12

CS 350 Only

  1. The pseudocode for IDA* (Figure 4.10) works fine for searching trees, but can be made more efficient for search graphs. Write a more efficient version in Lisp, and use it to solve the 4 missionaries, 4 cannibals problem.
  2. We have the use of heuristic functions can dramatically improve resources needed for searching, when compared to uninformed search techniques. Of course the huerisitcs themselves must be computed, and it possible that informing our search will result in a more resource-intensive search. Using information well of course, will mean that the penalty for the use of the information is small compared to the performance benefit of using the information.

    Consider an extreme case: Is it possible to solve a problem with an exponential number of instances without any searching, if only a linear amount of knowledge is available? If it is not possible, show that it is not. If it is possible, describe the structural properties of the classe of problems for which it is possible, and give an example applying this approach to a search problem we have discussed in class.