Spring 2004

HW2: State Space Search

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.

- Consider the Missionaries and Cannibals puzzle discussed in class. The file www.creighton.edu/~davereed/csc550/Code/mission.scm contains a
state space
definition for this puzzle. It utilizes states of the form
((MissionariesOnLeft CannibalsOnLeft) BoatPosition (MissionariesOnRight CannibalsOnRight)) where the numbers of missionaries and cannibals on each side of the river will be integers ranging from 0 to 3, and the boat position will be either`left`or`right`. For example, the initial state for the puzzle is`((3 3) left (0 0))`, and the goal state is`((0 0) right (3 3))`.Using the

`time`function and the implementations in www.creighton.edu/~davereed/csc550/Code/search.scm, compare the performances of`DFS`,`DFS-nocycles`,`BFS`,`BFS-nocycles`, and`DFS-deepening`on this puzzle. That is, when the strategy produces an answer, report the execution time (not counting garbage collection). Comment on the apparent tradeoffs between the strategies.Note: the shortest time reportable by the

`time`function is 10 ms. If a search succeeds in finding a solution in less than 10 ms, then it will register as no time at all. If this occurs, time multiple calls to the function and divide by the number of repetitions to get a more accurate timing. For example, the following call would time how long it takes for DFS to solve the problem five times.(time (begin (dfs '((3 3) left (0 0)) '((0 0) right (3 3))) (dfs '((3 3) left (0 0)) '((0 0) right (3 3))) (dfs '((3 3) left (0 0)) '((0 0) right (3 3))) (dfs '((3 3) left (0 0)) '((0 0) right (3 3))) (dfs '((3 3) left (0 0)) '((0 0) right (3 3))))) - Consider the problem of traversing a maze, from one opening (identified as the Start) to
another opening
(identified as the Exit). For example, the diagram on the left shows an 8x9 maze, where the
Start is at the
upper-left corner, the Exit is at the lower-right corner, and walls are shown as black
rectangles. To the
right is a Scheme list structure that represents this maze.
S E (define MAZE '("*********" "S *" "* ** * *" "* ** *" "* * *****" "* * *" "* * ** E" "*********")) For maze traversals, a state space can be defined in which a state is defined by the coordinates of the person in the maze. For the above maze, we might identify the Start state as

`(1 0)`, designating the row at index 1 and the column at index 0. Likewise, the goal (Exit) state would be identified as`(6 8)`.Add the above definition of

`MAZE`to a file named`maze.scm`, and define the`GET-MOVES`function for the maze state space using this state representation. For example, the call`(GET-MOVES '(1 1))`should return`'((1 0) (1 2) (2 1))`, or some permutation of these three adjacent spaces in the maze. Note that your`GET-MOVES`function should work correctly even if a different maze is substituted for the above one. In particular, the maze dimensions might change and the Start and Exit positions might vary from maze to maze.Once you have completed this function, compare the performances of the uninformed search strategies on this problem and comment on the apparent tradeoffs.

- The Missionaries and Cannibals state space from
`mission.scm`contains a`HEURISTIC`function, which assigns a value to a state based on how many people are in their goal positions. This heuristic can be used by the hill-climbing and best first search strategies defined in www.creighton.edu/~davereed/csc550/Code/heuristics.scm. Compare the performance of these informed search strategies on the Missionaries and Cannibals problem. Does hill-climbing find a solution? Does best first search outperform the uninformed strategies from problem 1? Explain your answers.

- Similarly, define a
`HEURISTIC`function for your maze state space that can be used by the informed search strategies. Your function should assign a value to a state based on its distance from the goal (Exit) state. In particular, the function should determine the differences in row and column numbers between the current and goal states, and return the negated sum of those differences. Thus,`(HEURISTIC '(5 4) '(6 8))`should evaluate to -5. Compare the performance of the informed search strategies using this heuristic and comment on its behavior.