This assignment involves solving state space problems and comparing the performance of the different search strategies discussed in class.

MzScheme provides a utility function, time, that can be useful in profiling code. The time function, when given an expression as input, evaluates that expression and reports the number of milliseconds of CPU time taken for the evaluation. It even identifies the amount of CPU time taken by garbage collection, so that number can be subtracted out to determine the amount of time spent doing actual computation. Unfortunately, the time function does not produce meaningful results if the execution is extremely fast, as will be the case in some instances here. Instead, you will want to use the following function:

The first input to the time-reps function is a quoted expression to be evaluated, and the second input is a number of repetitions. For example, the call (time-reps '(reverse '(1 2 3 4 5 6)) 1000) would reverse the list 1000 times and report the total CPU time. Subtracting out the garbage collection time then dividing by 1000 will give a fairly consistent and accurate timing for each reverse.

1. For each of the three state space problems discussed in class:
   • travel.scm: 'Omaha --> 'LosAngeles
   • jugs.scm: '(0 0) --> '(2 0)
   • tiles.scm: '(1 2 3 8 6 space 7 5 4) --> '(1 2 3 8 space 4 7 6 5)

   compare the performances of the search strategies: DFS, DFS-nocycles, BFS, BFS-nocycles, and DFS-deepening. That is, when the strategy produces an answer, report the execution time (not counting garbage collection). Comment on the apparent tradeoffs between the strategies.
   
   

2. Consider the following problem:

   Three missionaries and three cannibals seek to cross a river, say from the left bank to the right bank. A boat that may be navigated by any combination of one or two people is available on their side of the river. If the missionaries on either side of the river are outnumbered at any time by cannibals, the cannibals will indulge in their anthropophagic tendencies and do away with the missionaries. Find a sequence of boat trips that will permit all the missionaries and cannibals to cross the river safely.

   1. Define a state space for this problem. In particular, determine how a state will be represented and define the GET-MOVES function to generate all states reachable from a given state.
      
      
   2. Attempt to solve this problem using the various uninformed search control strategies provided, i.e. DFS, DFS-nocycles, BFS, BFS-nocycles, and DFS-deepening. Discuss the behaviors of each of these approaches. For example, if a strategy fails, explain why this would happen. Similarly, if one strategy outperforms another, explain why.
   
   
3. Consider a generalization of the previous problem where there are five missionaries and five cannibals that need to cross the river. The boat can handle up to three people, but the number of cannibals on the boat must never exceed the number of missionaries. As in the previous question, define a state space for this problem, implement the GET-MOVES function, attempt to solve the problem using each of the uninformed strategies, and explain your results.
   
   

ADDITIONAL QUESTION FOR GRADUATE STUDENTS:

4. The implementation of DFS with iterative deepening that was provided for you has one undesirable feature. As is, this function will never halt with an answer of #f, even with a finite search space. Instead, it will just keep extending the depth bound and repeating the same search. Modify this code so that it is able to recognize when the search space is exhausted and terminate accordingly. Note: your modification should not utilize destructive assignments.