Assigned: Jan. 24
Due: Jan. 31
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.
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.)