README COPY OF Quiz 6 (Backtracking Search lectures 1-4)
Due No due date Points 38 Questions 4 Available after Nov 16 at 12am Time Limit None Allowed Attempts Unlimited
Attempt History
Take the Quiz Again
Attempt Time Score
LATEST Attempt 1 14 minutes 0 out of 38 *
* Some questions not yet graded
Submitted Dec 2 at 3:38am
In this quiz we will use the same CSP as was used in Quiz 5: Variables: V1, V2, V3, V4, V5
Variable Domains:
Dom[V1] = Dom[V2] = Dom[V3] = {1,2,3} Dom[V4] = { ‘bob’, ‘fred’, ‘sam’}
Dom[V5] = {¡®a¡¯, ¡®b¡¯, ¡®c¡¯, ¡®d¡¯}
Constraints:
C1(V1, V2), C2(V2, V3) C3(V2, V3, V4, V5), and C4(V2,V5)
C1(V1, V2): V1 and V2 have different parity (i.e., one is ODD and the other is EVEN ) C2(V2, V3): V2 != V3
C3(V2, V3, V4, V5): if V2+ V3 is ODD then V5 is contained in V4
if V2 + V3 is EVEN then V5 is not contained in V4. C4(V2,V5):ifV2 isODDthenV5 =¡¯a¡¯orV5 =¡®b¡¯,ifV2 isEVENthenV5 =¡®c¡¯orV5 =¡®d¡¯
As an example of how C3 works: V2=1, V3=2, V4=’sam’, V5=¡®a¡¯ satisfies the constraint, as does V2=1, V3=1, V4=’sam’, V5=¡®d¡¯, while V2=1, V3=1, V4=’bob’, V5=¡®b¡¯ falsifies it.
Unanswere
e ed
e
d d
Question 1
Not yet graded / 4 pts
1. Show the steps that GAC enforce will execute when we make the CSP (shown above) GAC at the root (i.e., before any variables have been assigned a value).
2. Show the domains of the variables after GAC enforce has completed.
In particular, in a table like that below show each step of the GACEnforce Algorithm. Show the queue of constraints that exists when this step starts. Always select the lowest number constraint from the queue to process next. Show the current domains of the variables that have had values pruned from their domains (do not show the domains of variables that have not been changed at this step). And show the constraints that are newly added to the queue. (In the next step the queue of constraints will reflect all changes made by the prior step).
Format of answer expected:
For example, (using a completely different CSP with constraints C10, C11, C12 and C13
In this example, GACEnforce starts (at step 1) with its queue containing C12 and C13. It selects the lowest numbered constraint on the queue (C12) and makes that constraint GAC. This results in only V20 having some values pruned from its domain, leaving V20 with the domain {1,10,11}. In addition, the constraint C10 is added to the queue for further processing. In the second step the constraint queue consists of C10 and C13 (C12 has been removed in the prior step, and C10 has been added). Again the algorithm selects the lowest valued constraint to process, C10, and that results in pruning domain values from the domain of V14 and V13, leaving them with the domains shown. It also results in adding C11 and C12 to the queue.
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
C12, C13
V20={1, 10, 11}
C10
2.
C10, C13
V14 ={‘z’, ‘x’}, V13 ={1, 2, 3}
C11, C12
Your Answer:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
C1, C2, C3, C4
2.
C2, C3, C4
3.
C3, C4
4.
C4
5
{}
The last line is optional.
Variable domains after GAC.
Dom[V1] = Dom[V2] = Dom[V3] = {1,2,3} Dom[V4] = { ‘bob’, ‘fred’, ‘sam’} Dom[V5] = {¡®a¡¯, ¡®b¡¯, ¡®c¡¯, ¡®d¡¯}
Marks: 1 Marks for showing that C1, C2, C3, C4 is what we start with in the queue when doing GAC at the root.
3 Marks for getting the remaining steps correct and having no variables pruned and no constraints added to the queue
1 Mark for correct final variable domains.
Unanswere
e ed
e
d d
Question 2
Not yet graded / 10 pts
1. Show the steps that GAC enforce will execute after the assignment V1 = 1 is made (i.e., during GAC search this is the first variable assignment made)
2. Show the domains of the variables after GAC enforce has completed. Note that since V1 = 1 is an assignment made Dom[V1] = {1} (assignments implicitly prune all other values of the variable)
Format you answer as in the previous question.
A. Show the queue of constraints that exists when this step starts. Always select the lowest number constraint from the queue to process next.
B. Show the current domains of the variables that have had values pruned from their domains (do not show the domains of variables that have not been changed at this step).
C. Show the constraints that are newly added to the queue. (In the next step the queue of constraints will reflect all changes made by the prior step).
Format of answer expected:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
Your Answer:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
C1
V2 = {2}
C2, C3, C4
2.
C2, C3, C4
V3 = {1, 3}
3.
C3, C4
V5 = {a, b, d}
4.
C4
V5 = {d}
C3
5.
C3
V4 = {fred}
6
{}
(last row optional)
Variable Domains: V1={1}, V2={2}, V3={1,3} V4={fred}, V5={d}
Marks: 1 mark for C1 in “queue at start” at step 1. 8 marks for rest of table correct.
1 mark for correct variable domains.
Part marks: 1 mark rest of row 1 correct (i.e., variable domains and constraints
added correct in row 1)
3 marks for row 1 and row 2 correct. 5 marks for rows 1-3 correct.
Unanswere
e ed
e
d d
Question 3
Not yet graded / 10 pts
1. Show the steps that GAC enforce will execute after the assignment V1 = 2 is made (i.e., during GAC search this is the first variable assignment made)
2. Show the domains of the variables after GAC enforce has completed. Note that since V1 = 2 is an assignment made Dom[V1] = {2} (assignments implicitly prune all other values of the variable)
Format you answer as in the previous question.
A. Show the queue of constraints that exists when this step starts. Always select the lowest number constraint from the queue to process next.
B. Show the current domains of the variables that have had values pruned from their domains (do not show the domains of variables that have not been changed at this step).
C. Show the constraints that are newly added to the queue. (In the next step the queue of constraints will reflect all changes made by the prior step).
Format of answer expected:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
Your Answer:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
C1
V2={1,3}
C2, C3, C4
2.
C2,C3,C4
3.
C3, C4
4.
C4
V5={a, b}
C3
5.
C3
6.
{}
last row optional
Variable domains: V1={2}, V2={1,3}, V3={1,2,3}, V4={bob, fred, sam}, V5 = {a,b}
Marks: 8 marks for table correct.
2 mark for correct variable domains.
Part marks: 1 mark for row 1 correct
3 marks for row 1 and row 2 correct.
5 marks for rows 1-3 correct.
Unanswere
e ed
e
d d
Question 4
Not yet graded / 14 pts
Find the first four (4) solutions to the above CSP using GAC
Use the MRV heuristic to determine the variable ordering. Break ties by choosing the variable with lowest index (e.g., V4 before V5 if both are tied with respect to the MRV heuristic).
Assign each variable the values in its domain in the same order the domain is specified.
In a table formatted as specified below, show each node visited in the order visited by GAC. For each node show
the variable assignment made at that node
list the updated current domain of every variable that has had its current domain pruned by that assignment. Do not show variables that have not had their current domains updated.
Indicate if GAC finds a domain wipe out at that node. In the case of a domain wipe out you do not need to list the updated variable domains.
Finally, specify the four solutions found by GAC.
Hint the answers found above solve some of the steps. Your table should have the format
For example, say that we have a CSP with variables X1, X2, X3, X4, X5, X6, and constraints C1, C2, C3, C4, C5. Then the table entry
would indicate that the 9th node visited by GAC assigned X4 the value 10 and pruned the domains of X1 and X3. After pruning the current domain of X1 is {1,3} and the current domain of X3 is {4,5,6,7}. No other variable has had its current domain updated at this node. There was no domain wipeout.
The table entry
would indicate that the 11th node visited by GAC assigned X5 the value ‘a’ and GAC pruning caused a domain wipe out.
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
9
X4 = 10
X1 = {1,3}, X3 ={4, 5, 6, 7}
N
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
11
X5 = ‘a’
Y
Your Answer:
Node # Variable Assignment Made Updated Variable Domains
DWO [Y/N]
1. V1 = 1 V2={2}, V3={1,3} V4={fred}, V5={d}
N
2. V2 = 2
N
3. V4 = fred
N
4. V5 = d
N
5. V3 = 1
N
6. V3 = 3
N
7. V1 = 2 V2 = {1,3}, V5 = {a,b}
N
8. V2 = 1 V3 = {2, 3}
N
9. V3 = 2 V4 = {bob, sam}
N
10. V4 = bob V5 = {b}
N
11. V5 = b
N
12. V4 = sam V5 = {a}
N
13. V5 = a
Solutions:
1. V1 = 1, V2 = 2, V3 = 1, V4 = fred, V5 = d 2. V1 = 1, V2 = 2, V3 = 3, V5 = fred, V5 = d 3. V1 = 2, V2 = 1, V3 = 2, V4= bob, V5 = b 4. V1 = 2, V2 = 1, V3 = 2, V4 = sam, V5 = a
Marks: Table = 10, solutions = 4
Part marks.
1 marks for correct first row.
4 marks for correct first 6 rows.
1 mark if have a row V1=2 with correct other entries. 4 marks for subsequent 6 rows under V1=2 correct