$24
Name:
How to complete this HW: First copy this file; then insert your answers in the file immediately below each question. Submit your homework via the digital drop box on Blackboard by 11:59 pm on the due date.
Note on Collaboration: You may discuss these problems with other students in the class and/or look into other documents (books, web sites), with the exception of published solutions. However, when you write up your solutions please do so individually. If you have discussed any of the problems with other students, indicate their name(s) here:
………………………………………………………………………………………………
Any intentional transgression of these rules will be considered academic misconduct.
General information: In the following, whenever an explanation is required or implied (“Why?”), there will not be full-credit without an explanation.
(5 points) In this map-coloring problem, each variable has the domain {red, green, blue}.
B
A D
C
We start out by coloring country A red.
What will the domains of B, C, and D be after doing forward checking? After AC3? [It is not necessary to show the full details of either algorithm. It is sufficient that you give a high-level explanation of why a value is removed from a particular variable’s domain.]
Without instantiating any additional variables, what further inconsistent values can you eliminate? Explain why forward checking and AC3 weren’t able to do this.
Formulate a constraint propagation algorithm specific to the map-coloring problem that will correctly detect the kind of inconsistency shown in part 2. Note that this algorithm does not need to duplicate the behavior of forward checking or AC3. Pseudo-code is not necessary, but your formulation should be precise.
II. (5 points) A machine shop has four jobs to complete – j1, j2, j3, j4. Each one takes an hour and no two can be done simultaneously. Moreover, job one must be completed before job four, and job two after job three.
Formulate this scheduling problem as Constraint Satisfaction Problem. [Your answer should start like this: There are 4 variables, say, j1, j2, j3, j4. The domain of j1 is {1, 2, 3, 4} << FILL THE REST .]
Use backtracking search to find a solution. Show the sequence of variable values evaluated and backtracks. [Here, your answer should start like this:
Denoting backtrack points (i.e., dead-ends) by BC, the backtracking search produces this
sequence:
j1 = 1, j2 =1, BC,
j2 = 2, j3 = 1, BC,
FILL THE REST ]
Use local search with min-conflicts heuristic to find a solution. Start with (2,2,2,2) allocation (i.e., j1, j2, j3, j4 = 2) and show all steps. [Instead of picking conflicted variables at random, pick them in their natural order, i.e., j1, j2, j3, j4.]
I now advise you to draw the constraint graph to help you answer the following question, but you don’t have to submit this graph in your answer. Find a solution by interweaving AC3, backtracking and forward checking. Explain concisely what variable values are eliminated or selected at each step.