Due Date: September 20, 2007 at the beginning of class
- Read Chapters 3, 4, 5, and 6 of the textbook.
- Problems: You need to turn in written solutions ONLY
TO THE PROBLEMS MARKED WITH AN ASTERISK "*" BELOW
at the beginning of class on September 20, 2007. Solve the
other problems before the class so that you can ask questions
about them in preparation for Exam 1.
- Chapter 3:
3.6,3.8*, 3.9, 3.12, 3.13*, 3.14, 3.17.
- Chapter 4:
4.1, 4.2*, 4.3*,4.7, 4.11*, 4.16.
- Construct a search space together with an admissible heuristic for
which each of the search methods
listed below produces a different sequence of expanded states (that
is, the states and/or the order in which the states are expanded is
different for each search method).
The search methods you should take into consideration are:
depth-1st, breadth-1st, depth-limited (limit=3), uniform (i.e., branch
and bound), A*, greedy search, hill-climbing, and beam search (w = 2).
- * Describe the general behavior of the search methods listed
below in terms of how they handle a "queue" that keeps track of
which paths are expanded and in what order. Describe this general behavior
by answering the following questions. Note that the answers to questions
1, 2, 3, 4, and 6 should be the same for all search methods, so answer them
just once. The answer to part 5 depends on the particular search method.
- what is a path?
- how is the queue initialized (be precise!)?
- what path in the queue is selected for expansion?
- once that a path is selected for expansion, how is it expanded?
- where are the expansions of the selected path addeded to the queue?
- when does the search terminate and why?
The search methods you should take into consideration are:
depth-1st, breadth-1st, depth-limited, iterative deepening,
uniform (i.e., branch
and bound), A*, greedy search, hill-climbing, and beam search.