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