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