In class, we studied a Scheme implementation of the Flashlight puzzle. In particular,
we defined a state space that captured a state (positions of the people and flashlight),
a GET-MOVES function to generate legal moves and their associated costs (in minutes), and a simple
heuristic estimate of remaining cost (in minutes) for a given state (see flashlight.scm). Given this implementation, Algorithm A
(atree.scm), was able to find the minimum cost (in elapsed
minutes) solution to the puzzle.
The heuristic used in this implementation is rather simplistic: it merely counts the number of people out of their
goal position. A better heuristic would take into account the actual time required for the people to get into their
goal positions. For this problem, you will consider a "more informed" heuristic and compare Algorithm A's
performance using this new heuristic.
- Similar to exercises in HW2, use the time function to time a solution to the
Flashlight puzzle using Algorithm A
(the a-tree function from atree.scm). Recall that the initial state is
when all four people are on the left side with the flashlight, and the goal state is when all four are on the right
> (a-tree '((1 2 5 10) left ()) '(() right (1 2 5 10)))
How many milliseconds does it take to solve the problem?
- Now add an additional person to the puzzle, whose walking time to cross the bridge is 15 minutes. How many
milliseconds does it take to solve the puzzle with this additional person?
- Does the speed of the additional walker affect the performance of Algorithm A in solving the puzzle? For
example, if the additional walker required 100 minutes instead of 15, would that affect the running time of the
algorithm? Explain your reasoning and provide timings to back up your claim.
- Now consider the following heuristic cost estimate function, which determines which people on each side are
out of place, pairs them up, and adds the longer times from each pair.
(define(H state goalState)
(define (sum-odd-indices numlist)
(cond ((null? numlist) 0)
((null? (cdr numlist)) (car numlist))
(else (+ (car numlist) (sum-odd-indices (cddr numlist))))))
(+ (sum-odd-indices (reverse (remove-all (car goalState) (car state))))
(sum-odd-indices (reverse (remove-all (caddr goalState) (caddr state))))))
> (H '((1 2 5 10) left ()) '(() right (1 2 5 10)))
> (H '((1 2 10) left (5)) '(() right (1 2 5 10)))
Is this new heuristic admissible? Justify your answer.
- Is this new heuristic "better informed" than the old one? That is, for any state, is this heuristic guaranteed
to return a cost estimate that is at least as large as the original one? Justify your answer.
- Compare the performance of Algorithm using this new heuristic. That is, replace the current H function
with this one, and time how long it takes to solve both the original problem and the extended problem (with
additional walker). In general, would you always expect a "better informed" heuristic to lead to a faster search?
> (H '(0 0) '(2 0)) > (H '(4 1) '(2 0))