$29.99
VE492Homework5
Question 1: Campus Layout
You are asked to determine the layout of a new, small college. The campus will havefour structures: an administration structure (A), a bus stop (B), a classroom(C), andadormitory (D). Each structure (including the bus stop) must be placed somewhere onthe grid shown below. The layout must satisfy the following constraints:
i. The bus stop (B) must be adjacent to the road. ii. The administration structure (A) and the classroom (C) must both be adjacent
to the bus stop (B). iii. The classroom (C) must be adjacent to the dormitory (D). iv. The administration structure (A) must not be adjacent to the dormitory (D). v. The administration structure (A) must not be on a hill. vi. The dormitory (D) must be on a hill or adjacent to the road. vii. All structures must be in different grid squares. Here, adjacent means that the structures must share a grid edge, not just a corner. We recommend you work out the solutions to the following questions on a sheet of
scratch paper, and then enter your results below. Part 1: Unary Constraints
(a) Which of the constraints above are unary constraints?
A. i
B. ii
C. iii
D. iv
E. v
F. vi
G. vii
H. None of the above
Sample Answer:
ABCD
(b) Write the domains of all variables after unary constraints have been applied. Sample Answer:
A(1,1)(1,2)B(1,1)C(1,1)(1,2)D(1,1)(1,2)
Part 2: Arc Consistency
Let's start from the table above (the answer to Part 1) and enforce arc consistency. Initially, the queue contains all arcs (in alphabetical order). Let's examine what happens when enforcing A→B. After enforcing unary constraints, the domains of A and B are:
(c) Which of the following contains the correct domains after enforcing A→B? Payattention to which variable's domain changes and which side of the arc it's on.
A. i
B. ii
C. iii
D. iv
(d) Starting from the answer to Part 1 (in which unary constraints are enforced), writethe domains of all variables after A→B is enforced. Sample Answer:
A(1,1)(1,2)B(1,1)C(1,1)(1,2)D(1,1)(1,2)
(e) You should verify that enforcing consistency for A→C, A→D, B→A, B→C, B→D, and C→A do not change the domains of any variables. After enforcing thesearcs, the next is C→B. Continuing from the previous parts, write the domains of all variables after C→Bisenforced. Sample Answer:
A(1,1)(1,2)B(1,1)C(1,1)(1,2)D(1,1)(1,2)
(f) What arcs got added to the queue while enforcing C→B? Remember that thequeue contained C→D, D→A, D→B, and D→C prior to enforcing C→B. A. A→B
B. A→C
C. A→D
D. B→A
E. B→C
F. B→D
G. C→A
H. C→B
I. C→D
J. D→A
K. D→B
L. D→C
M. None
(g) Continuing from the previous parts, select the domains of all variables after
enforcing arc consistency until the queue is empty. Remember that the queuecurrently contains C→D, D→A, D→B, D→C, and any arcs that were added whileenforcing C→B. Sample Answer:
A(1,1)(1,2)B(1,1)C(1,1)(1,2)D(1,1)(1,2)
Part 3: Search with Arc Consistency
(h) If arc consistency had resulted in all domains having a single value left, we wouldhave already found a solution. Similarly, if it had found that any domain hadnovalues left, we would have already found that no solution exists. Unfortunately, this isnot the case in our example (as you should have found in the previous part). To solvethe problem, we need to start searching. Use the MRV (minimum remaining values)
heuristic to choose which variable gets assigned next (breaking any tiesalphabetically). Which variable gets assigned next?
A. A
B. B
C. C
D. D
(i) The variable you selected should have two values left in its domain. We will usethe least-constraining value (LCV) heuristic to decide which value to assign beforecontinuing with the search. To choose which value is the least-constraining value, enforce arc consistency for each
value (on a scratch piece of paper). For each value, count the total number of valuesremaining over all variables. Which value has the largest number of values remaining (and therefore is the least
constraining value)?
A. (1,1)
B. (1,2)
C. (1,3)
D. (2,1)
E. (2,2)
F. (2,3)
(j) After assigning a variable, backtracking search with arc consistency enforces arcconsistency before proceeding to the next variable. Write the domains of all variables after assignment of the least-constraining value tothe variable you selected and enforcing arc consistency. Note that you already didthiscomputation to determine which value was the LCV. Sample Answer:
A(1,1)(1,2)B(1,1)C(1,1)(1,2)D(1,1)(1,2)
(k) Is the answer to the previous part a solution to the CSP? Write Yes or No.
Question 2: CSP Properties
(a) Write all of the following statements about CSPs that are true. A. Even when using arc consistency, backtracking might be needed to solveaCSP. B. Even when using forward checking, backtracking might be needed to solveaCSP. C. None of the above
(b) Select all of the following statements about CSPs that are true. A. When using backtracking search with the same rules to select unassignedvariables and to order value assignments (in our case, usually MinimumRemaining Values and Least-Constraining Value, with alphabetical
tiebreaking), arc consistency will always give the same solution as forwardchecking, if the CSP has a solution. B. For a CSP with binary constraints that has no solution, some initial valuesmay still pass arc consistency before any variable is assigned. C. None of the above
Question 3: 4-Queens
The min-conflicts algorithm attempts to solve CSPs iteratively. It starts by assigningsome value to each of the variables, ignoring the constraints when doing so. Then, while at least one constraint is violated, it repeats the following:
(1) randomly choose a variable that is currently violating a constraint, (2) assign to it the value in its domain such that after the assignment the total number
of constraints violated is minimized (among all possible selections of values initsdomain). In this question, you are asked to execute the min-conflicts algorithmon a simpleproblem: the 4-queens problem in the figure shown below. Each queen is dedicatedtoits own column (i.e. we have variables
,
,
, and the domain for eachoneof them is {A, B, C, D}). In the configuration shown below, we have th th th . Two queens are in conflict if they share the same row, diagonal, or column (though in this setting, they can never share the same column).
You will execute min-conflicts for this problem three times, starting with the stateshown in the figure above. When selecting a variable to reassign, min-conflictschooses a conflicted variable at random. For this problem, assume that yourrandom number generator always chooses the leftmost conflicted queen. Whenmoving a queen, move it to the square in its column that leads to the fewest conflictswith other queens. If there are ties, choose the topmost square among them. We recommend you work out the solutions to the following questions on a sheet of
scratch paper, and then enter your results below. Part 1
Starting with the queens in the configuration shown in the above figure, which queenwill be moved, and where will it be moved to? Write your answer in a formof tuple(Queen,Position).
Sample Answer:
(2,A)
Part 2
Continuing off of Part 1, which queen will be moved, and where will it be movedto?Write your answer in a form of tuple (Queen,Position). Sample Answer:
(2,A)
Part 3
Continuing off of Part 2, which queen will be moved, and where will it be movedto?Write your answer in a form of tuple (Queen,Position). Sample Answer:
(2,A)
Question 4: Tree-Structured CSPs
There exist efficient solvers for tree-structured CSPs. We can use such solvers intheinner loop of a CSP solver for near-tree-structured CSPs as follows: First find a cutset
(i.e. a set of variables such that if removed, the remaining constraint graph forms atree), then loop over all instantiations of the cutset variables, and for each instantiationcall the tree-structured CSP solver to verify if for that instantiation a solution exists;
the algorithm terminates when a solution is found or when it has looped over all
possible instantiations and no solution was found (and hence the CSP has nosolution).
Consider the graph above. Write down the variables that are in the smallest cutset of
this graph. Note: in general, this is a computationally difficult problem. We have not seenanalgorithm to compute the minimum cutset in lecture, but for a small graph you shouldbe able to do it by hand (with some effort). Sample Answer:
AB
Question 5: Solving Tree-StructuredCSPsConsider the following tree-structured CSP that encodes a coloring problemin whichneighboring nodes cannot have the same color. The domains of each node are shown. The algorithm for solving tree-structured CSPs starts by picking a root variable. Wecan pick any variable for this. For this exercise, we will pick . There are several
linearizations consistent with as the root; we will use the one shown below.
Step 1: Remove Backward
In this step we start with the right-most node ( ), enforce arc-consistency for itsparent (), then do the same for the second-to-right-most node () and its parent (), and so on. Execute this process, and then write the remaining values for all thevariables. Sample Answer:
A(red)B(red,green)C(red,green,blue)D(red)E(red,green)
Step 2: Assign Forward
Now that all domains have been pruned, we can find the solution in a single forwardpass (i.e. no need for backtracking). This is done by starting at the left-most node (), picking any value remaining in its domain, then going to the next variable ( ), picking any value in its domain that is consistent with its parent, and continue left toright, always picking a value consistent with its parent’s assignment. If at any given node there are multiple colors left that are consistent with its parent’svalue, break ties by picking red over green, and then green over blue. What is the solution found by running the algorithm?
Sample Answer:
A(red)B(green)C(red)D(red)E(green)
Question 6: Arc Consistency
Consider the problem of arranging the schedule for an event. There are three timeslots: 1, 2, and 3. There are three presenters: , , and . The variables for the CSPwill then be , , and , each with domain {1, 2, 3}. The following constraints needto be satisfied:
1. , , and all need to take on different values
2.
(a) Enforce consistency for the arc A→C, and then write down which values remainfor each variable. Sample Answer:
A(1)B(1,2)C(1,2,3)
(b) Starting from the result of the previous step, enforce consistency for the arc B→A, and then write down which values remain for each variable. Sample Answer:
A(1)B(1,2)C(1,2,3)
(c) Starting from the result of the previous step, enforce consistency for the arc C→A, and then write down which values remain for each variable. Sample Answer:
A(1)B(1,2)C(1,2,3)
Question 7: Arc Consistency PropertiesAssume you are given a CSP and you enforce arc consistency. Which of the followingare true?
A. If the CSP has no solution, it is guaranteed that enforcement of arc consistencyresulted in at least one domain being empty. B. If the CSP has a solution, then after enforcing arc consistency, you can directlyread off the solution from resulting domains. C. In general, to determine whether the CSP has a solution, enforcingarcconsistency alone is not sufficient; backtracking may be required. D. None of the above.
Question 8: Backtracking Arc ConsistencyWe are given a CSP with only binary constraints. Assume we run backtracking searchwith arc consistency as follows. Initially, when presented with the CSP, one roundof
arc consistency is enforced. This first round of arc consistency will typically result invariables having pruned domains. Then we start a backtracking search usingthepruned domains. In this backtracking search we use filtering through enforcingarcconsistency after every assignment in the search. Which of the following are trueabout this algorithm?
Part 1
Which of the following are true about this algorithm?
A. If after a run of arc consistency during the backtracking search we end upwiththe filtered domains of all of the not yet assigned variables being empty, thismeans the CSP has no solution. B. If after a run of arc consistency during the backtracking search we end upwiththe filtered domain of one of the not yet assigned variables being empty, thismeans the CSP has no solution. C. None of the above. Part 2
Which of the following are true about this algorithm?
A. If after a run of arc consistency during the backtracking search we end upwiththe filtered domains of all of the not yet assigned variables being empty, thismeans the search should backtrack because this particular branch in the searchtree has no solution. B. If after a run of arc consistency during the backtracking search we end upwiththe filtered domain of one of the not yet assigned variables being empty, thismeans the search should backtrack because this particular branch in the searchtree has no solution. C. None of the above. Part 3
Which of the following are true about this algorithm?
A. If after a run of arc consistency during the backtracking search we end upwiththe filtered domains of all of the not yet assigned variables each having exactlyone value left, this means we have found a solution. B. If after a run of arc consistency during the backtracking search we end upwiththe filtered domains of all of the not yet assigned variables each having more thanone value left, this means we have found a whole space of solutions and we canjust pick any combination of values still left in the domains and that will bea
solution. C. If after a run of arc consistency during the backtracking search we end upwiththe filtered domains of all of the not yet assigned variables each having more thanone value left, this means we can’t know yet whether there is a solutionsomewhere further down this branch of the tree, and search has to continue downthis branch to determine this.