## 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: 3^{7} = 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