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
side:
> (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))))))
For example,
> (H '((1 2 5 10) left ()) '(() right (1 2 5 10)))
12
> (H '((1 2 10) left (5)) '(() right (1 2 5 10)))
11
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?
Explain.
> (H '(0 0) '(2 0)) > (H '(4 1) '(2 0))
1 1.5