Introduction to Artificial Intelligence: Problem Set 2

Assigned: Jan. 24
Due: Jan. 31

Problem 1

The MAP-COLORING problem is defined as follows: Given a map of countries, and a fixed set of colors, assign a color to each region in the map in such a way that no two adjacent regions have the same color. For example, the map of New England + New York can be colored from the set {Red, White, Blue} by the assignment: Maine is Red, New Hampshire is Blue, Vermont is Red, Massachussetts is White, Rhode Island is Blue, Connecticut is Red, New York is Blue. (The adjacency relations in this map are as shown below.)
                  VT--NH---ME
                  |\  |   /
                  | \ |  /
                  |  \| /
                  NY--MA
                   \  | \
                    \ |  \
                     \|   \
                      CT---RI

A. Write a non-deterministic algorithm to solve the MAP-COLORING problem given a map and a coloring. You can assume that the map is given in the form of a collection of statements ``Region R borders on Region Q.''

Answer

MAP-COLORING(in M : map; CS : set of colors; out CC : coloring)
begin CC := empty coloring;
      for R in M do
        choose a color C in CS such that
            there is no region R1 in M such that 
                R1 borders R in M and R1 is assigned color C in CC;
        add the assignment R -> C to CC
      endfor
      return CC
end.

B. Give bounds on the branching factor, the depth of the search space, and the size of the search space as functions of the number of regions and the number of colors.

Answer: The branching factor is at most the number of colors, |CS|. The depth of the search space is the number of regions |M|. The search space therefore has size at most |CS| ** |M|.

Problem 2

An alternative approach to the MAP-COLORING problem is to use a hill-climbing strategy. For example, one could take a state to be an assignment of colors to all the regions; the cost function to be the number of pairs of regions that are adjacent and are the same color; the operator to be to change the color of one region; and and then try to minimize the cost function using hill-climbing.

Answer the following questions for the particular map shown above and the particular case of using three colors:

A. What is the size of the state space? What is the branching factor? What is the diameter of the state space (i.e. the maximum distance from one state to another.)

Answer: Size of the state space: 37 = 2187. Branching factor: 14 (there are always 7 regions whose color can be changed to either of 2 alternative values). Diameter: 7. (To turn state S into state T, change one region at a time from its value in S to its value in T.)

B. Consider a starting state S in which all countries are labelled "White"? What is the minimum cost neighbor of this state? What is the cost of these two states?

Answer: The minimum cost neighbor has Massachussetts labelled "Red" or "Blue". The cost of the all white map is 10. The cost of the second map is 5.

C. Find a state S that is a local minimum of the cost function but is not a solution; that is, does not have cost 0. ("Local minimum" in the non-strict sense; the cost of S is less than or equal to the cost of any of its neighbors.)

Answer:

MA: Red
ME: White
NH: Blue
VT: White
NY: White
CT: Blue
RI: White