Copy the Eliza program from eliza.scm and make the following modifications:
For example, the call (time (bfs '(0 0) '(2 0))) would report how long it took to solve the Jugs Puzzle using breadth-first search. Note, however, that 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 breadth-first search to solve the Jugs Puzzle five times.
Using the time function and the implementations in
search.scm, compare
the performances
of DFS, DFS-nocycles,
BFS, BFS-nocycles, and DFS-deepening on each of these
problems. That is, when
the strategy produces an answer, report the execution time (not
counting
garbage collection). Comment on the apparent tradeoffs between the
strategies.
|
|
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 for this maze would be identified as (6 8).
The file maze.scm contains a Scheme definition of
the state space for this problem. Using this implementation, compare the performances
of the uninformed search
strategies on
this maze and comment on the apparent tradeoffs.
S | E | |||||||||
Using this hueristic function, attempt to solve the mazes from the last two problems using hill-climbing and best-first search (defined in heuristics.scm). If a strategy is unable to solve the problem, explain why. If it is successful, time its execution and compare its efficiency with the uninformed strategies.