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.''
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|.
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.)
MA: Red ME: White NH: Blue VT: White NY: White CT: Blue RI: White