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