You should complete this assignment on your own (not in teams). You may discuss the assignment with other students and on the class discussion list cse473-discuss, but you should do your own writeup, and you should not pass around your written solution.
1. A student project in a class taught by UW CSE professor Oren Etzioni resulted in a system called Hamlet, that advised travellers on the best time to purchase their airline tickets. You can read about the technology they used in this paper:
To Buy or Not to Buy: Mining Airfare Data to Minimize Ticket Purchase Price (2003)
Oren Etzioni, Craig A. Knoblock, et al.
Hamlet is now being turned into a commercial product by a startup company. The exact business model for the commerical system has not yet been announced, but for the purposes of this excercise, we will assume that users will pay a small amount of money up front to get Hamlet's advice each time they use it.
Characterize the problem Hamlet is solving using the categories of environment types used in R&N:
Give brief reasons for your choices.
2. A state-space search algorithm can often be improved by adding a cache called a "closed list" that is used to record visited states, as described in R&N section 3.5. Considering using a closed list with depth-first search for the "improved" 8-queens encoding on page 67.
(a) Will the closed list ever be useful in reducing the amount of search? Why or why not?
(b) Suppose we say that state S matches a state C on the closed list if they are identical or S is the mirror image of C, where the "mirror line" is the horizontal line across the middle of the board. Is Graph Search still guaranteed to find a solution eventually? What percentage of the states are potentially pruned by the closed list?
(c) Suppose that the successor function is no longer restricted to choosing a square in the leftmost empty column, but is allowed to choose a square in any empty column. How then should we define a "match" when comparing a state against the closed list?