READABLE COPY OF Quiz 5 (Backtracking Search Lectures 1-3)
Due No due date Points 34 Questions 4 Available after Nov 2 at 12am Time Limit None Allowed Attempts Unlimited
Attempt History
Take the Quiz Again
Attempt Time Score
LATEST Attempt 1 12 minutes 0 out of 34 *
* Some questions not yet graded
Submitted Dec 2 at 3:37am
We will use the following CSP in the questions below. 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¡¯}
Note that V4 takes on strings as values while V5 takes on characters as values (so the quote symbols ‘ are not part of the value)
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¡¯ or V5 = ¡®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.
Question 1
0 / 4 pts
nanswere
e ed
e
d d
U
Say that we represent each constraint as a table (as on slide 18 of the Backtracking search lecture). What will be the size (i.e., number of rows) of table representing each constraint.
1. C1 2. C2 3. C3 4. C4
Answer 1:
(You left this blank) 9
Answer 2:
(You left this blank) 9
Answer 3:
(You left this blank) 108
Answer 4:
(You left this blank) 12
u Answere
rrect Ans
u Answere
rrect Ans
u Answere
rrect Ans
u Answere
rrect Ans
s
w
s
r r
s
e
s
w
s
r r
s
e
s
w
s
r r
s
e
s
w
s
r r
s
e
e
ed
e
w
we
e
e
d
d
ed
e
w
we
ed
e
w
we
e
ed
e
w
we
e
er
d
d
e
er
d
d
e
er
d
d
e
er
o o
o o
o o
o o
Question 2
Not yet graded / 4 pts
nanswere
e ed
e
d d
Give the table that represents C4
Specify your answer in a table of the following form
Your Answer:
V2
V5
Satisfies C4(V2,V5) [Y/N]
Question 3
Not yet graded / 11 pts
nanswere
e ed
e
d d
Solve the above CSP using BT with the variable ordering that always selects the lowest index unassigned variable next (e.g., V2 before V3) and assigning each variable the values in its domain in the order given (e.g., assign V4=’bob’ before V4=’fred’). In a table formatted as specified below, show each node visited in the order of visited by BT. For each node show the variable assignment made at that node and list all of the constraints that are checked by BT at that node. For nodes where some constraint check failed you can list any one of the constraints that failed followed by an X to indicate that it failed (i.e., you don’t need to worry about constraint checks that succeeded at such nodes).
Finally, specify the solution found by BT.
Your table should have the format
Node #
Variable Assignment Made
Constraints Checked
U
U
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 10th node visited by BT assigned X6 the value ‘foo’ and checked the constraints C1 and C2 (and no others). And the table entry
would indicate that the 20th node visited by BT assigned X4 the value 1 and checked C5 resulting in C5 failing the constraint check. At this node BT might have checked other constraints but since checking C5 failed, we don’t necessarily need to list these other constraints (you can if you wish).
Your Answer:
Node #
Variable Assignment Made
Constraints Checked
10
X6=’foo’
C1, C2
Node #
Variable Assignment Made
Constraints Checked
20
X4=1
C5 X
10 Marks for Table, 1 mark for solution
Node# Variable Assignment
1. V1 = 1
2. V2 = 1
3. V2 = 2
4. V3 = 1
5. V4 = ‘bob’ 6.V5=’a’ 7.V5=’b’ 8.V5=’c’ 9.V5=’d’
10. V4 = ‘fred’ 11.V5=’a’ 12.V5=’b’ 13.V5=’c’ 14.V5=’d’
Constraints checked/failed none (or can leave blank) C1X
C1
C2
none
C3X
C3, C4 X (don’t need to show C3) C3X
C3X none C3X C3X C3X C3, C4
Part marks: first 3 rows correct 2 mark, first 8 rows correct 5 marks
Solution: V1 = 1, V2 = 2, V3 = 1 V4 = ‘fred’, V5 = ‘d’ (1 Mark no part marks)
Question 4
Not yet graded / 15 pts
nanswere
e ed
e
d d
Solve the above CSP using FC and 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).
As before 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
U
order visited by FC. For each node show the variable assignment
order visited by FC. For each node show the variable assignment
made at that node and 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. Finally indicate If FC 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 solution found by FC.
Your table should have the format
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
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
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
9
X4 = 10
X1 = {1,3}, X3 ={4, 5, 6, 7}
N
would indicate that the 9th node visited by FC 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
Node #
Variable Assignment Made
Updated Variable Domains
DWO [Y/N]
11
X5 = ‘a’
Y
would indicate that the 11th node visited by FC assigned X5 the value
‘a’ and FC pruning caused a domain wipe out.
Your Answer:
Table 14 marks, solution 1 mark
Node# Variable assigned
DWO
1. V1=1 N
2. V2=2 N
3. V3=1
N
4. V4 = ‘bob’ Y
5. V4 = ‘fred’ N
6. V5=’d’
N (blank is ok)
Updated Variable
domains V2= {2}
V3= {1, 3}, V5 = {‘c’, ‘d’} none (blank is also ok)
none
V5= {‘d’}
none
Part marks: First two rows correct 6 marks. First 4 rows correct 10 marks.
Solution V1 =1 , V2= 2, V3 = 1, V4 = ‘fred’, V5 = ‘d’ (1 mark no part marks)