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.''

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.

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.)

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?

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.)