README COPY OF Quiz 6 (Backtracking Search lectures 1-4)
Started: Dec 2 at 3:24am
Quiz Instructions
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.
Question 1 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:
Step #
Constraint Queue at start of step
Updated variable domains
Constraints newly added to queue by this step.
1.
For example, (using a completely different CSP with constraints C10, C11, C12 and C13
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
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
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.
View keyboard shortcuts
Edit View Insert Format Tools Table
12pt Paragraph
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor
Fullscreen
Question 2 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.
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 3 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.
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 4 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
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.
View keyboard shortcuts
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
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Saving…
Submit Quiz