CS121

Introduction to Artificial Intelligence

Winter 2004

 

 

 

Homework #1

(Search Problems)

Out: 1/14/03 — Due: 1/21/03

 

 

How to complete this HW: First copy this file; then insert your answers in the file immediately below each question; finally email the completed file to [email protected] before 1/21 at midnight.

When you e-mail your homework, your subject line should be your leland username and then the homework you are submitting (e.g. "mykel: hw1"). If you must resubmit, make this clear in the subject line (e.g. "mykel: hw1 RESUBMIT").

 

Note on Honor Code: You must NOT look at previously published solutions of any of these problems in preparing your answers. You may discuss these problems with other students in the class (in fact, you are encouraged to do so) and/or look into other documents (books, web sites), with the exception of published solutions, without taking any written or electronic notes. If you have discussed any of the problems with other students, indicate their name(s) here:

………………………………………………………………………………………………

Any intentional transgression of these rules will be considered an honor code violation.

 

General information: In the following, whenever an explanation is required (“Why?”), there will not be full-credit without an explanation. Keep explanations short and to the point. Excessive verbosity will be penalized. If you have any doubt on how to interpret a question, either tell us in advance, so that we can help you understand the question, or tell us how you understand it in your returned solution.

 

Grading:

 

Problem#

Max. grade

Your grade

I

5

 

II

5

 

III

5

 

IV

5

 

V

5

 

VI

5

 

Total

10

 

 

I. (5 points) Express the following problem as a search state problem:

 

“You have to color the various regions of a planar map (for example, the map of the 48 contiguous states of the United States) using only four colors (Red, Blue, Yellow, and Green), in such a way that no two adjacent regions have the same color.”

 

Give the general description of a state, the initial state, the goal test, and the successor function. For the successor function it is not necessary that you write every possible “state ΰ state” combination, but you should make it clear how one would derive the successor states of any given state. Note that we do not ask you to describe a solution of the problem!

 

II. (5 points) We ask you the same question for the following problem:

 

“Three jugs are filled with water. Neither has any measuring marker on it. Each can be fully or partially emptied in a drain or another jug. The jugs respectively measure 15, 7, and 3 gallons. One needs to measure out exactly 2 gallons.”

 

Note that we do not ask you to describe a solution of the problem!

 

III. (5 points) Consider a state space where states are describes by integers. The initial state is 1 and the successor function for state n returns two states 2n and 2n+1.

 

1.      Draw the portion of the state space that contains the initial state and all states that can be reached from the initial state down to depth 3.

2.      Let the goal state be 11. List the order in which nodes are visited by breadth-first search, depth-first search limited to depth 3, and iterative deepening search.

3.      Would backward search be appropriate for this problem? Describe how it would work

 

IV. (5 points) Does a finite state space always lead to a finite search tree? If not, give an example where a finite state space leads to an infinite search tree. How could you avoid an infinite tree?

 

V. (5 points) Consider the n-queens problem using the following formulation:

·         A state is an arrangement of k (0 £ k £ n) queens, one per column, in the leftmost k columns, with no two queens attacking one another.

·         The successor function adds a queen to a square in the leftmost empty column such that it is not attacked by any other queen.

·         The goal state is one with n queens.

 

1.      Show that (n!)1/3 is a lower bound on the size of the state space.

      [Hint: Consider the maximum number of squares in each column that can be attacked by queens from previous columns.]

2.      Consider the case where n = 8. The actual number of states is 2,057. How does this compare to the above lower bound? What are the causes for the difference?

 

VI. (5 points) Construct a search tree of uniform branching factor b and uniform depth d for which it is possible that depth-first search uses more memory than breadth-first search. (The depth of a node in a search tree is the length of the path from the root of the tree to N. In particular, the depth of the root is 0.)

 

Is there any tree and distribution of goal nodes for which depth-first search always requires more memory than breadth-first? Explain briefly. To answer this question, recall that depth-first search assumes no intrinsic ordering of the successors of a node; it may pick any ordering.