|
|
|
Problem Set 1 Due
Monday 10/12 at 1:30pm (Hand in printout at start of class)
In all problems below, please think carefully before answering questions – strive for a terse, precise explanation. Points may be taken off for overly long or complex explanations. If it is impossible answer a question with the information given, feel free to make additional assumptions (just state them clearly).
1. R&N AIMA2 –
exercise 2.2
2. R&N AIMA2 –
exercise 2.9
3. R&N AIMA2 – exercise
2.12a
4. R&N AIMA2 –
exercise 3.9a, c.
5. R&N AIMA2 –
exercise 3.19a
6. The traveling salesman
problem (TSP) can be posed with a set of cities C= {c1 … cn} and a distance function d(ci, cj) which returns a positive
integer for each pair of distinct cities. The objective is to find the shortest
path that visits each city exactly once.
a. Specify the TSP as a
search problem
b. A powerful, admissible
heuristic for TSP is based on estimating the remaining cost for completing a
partial tour with the sum of the link costs for the minimum spanning tree
connecting the graph of cities not yet in the tour. (The MST can be computed
relatively quickly, i.e. in O(E lg
E) time, using Kruskal’s algorithm). Show how
this heuristic can be derived from a relaxed version of the TSP.
7. Look at the project page
and learn about Robocode.
a. Get “My First
Robot” working
b. Make some enhancement and
test it in a few battles. Write a paragraph explaining your enhancement and its
success
c. Read Jacob
Eisenstein’s term
paper (and optionally his presentation);
then start thinking about how you might approach the problem of creating a
successful controller.
d. You only need to hand in
part b.
Computer Science & Engineering
Department
University of Washington
PO Box 352350
Seattle, WA 98195-2350
USA
Seattle, WA