程序代写代做代考 C algorithm follow the forward checking algorithm precisely: only prune values that would be pruned

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ All constraints put on GAC queue.
§ Process C3 first.
X = 1 (X=1, Y=1, Z=1, W=3) X = 2 (X=2, Y=1, Z=1, W=4) X = 3 (X=3, Y=1, Z=1, W=5) X = 4 – Inconsistent. Dom(X) = {1, 2, 3}
similarly Dom(Y) = {1, 2, 3} Dom(Z) = {1, 2, 3}
3
W = 1 – inconsistent
W = 2 – inconsistent
W = 3 – same support as X=1 W = 4 – same support as X = 2 W= 5 – same support as X = 3
Dom(W) = {3, 4, 5}
All domains pruned, but all other constraints already on GAC queue
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
2

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ Process C2 next Currently
Dom(X) = {1, 2, 3} Dom(W) = {3, 4, 5}
X = 1 (X=1, W=3) X = 2 (X=2, W=3) X = 3 (X=3, W=4)
W=3, W=4 found supports already
3 W=5 (X=1, W=5)
No domains pruned. Nothing added
to GAC Queue
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
3

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ Process C1 next
3
Z = 1 – same support as X=2
Z=2– samesupportasX=3 Z = 3 – inconsistent
Updated domains X = {2,3}
Y = {1,2}
Z = {1,2}
Put C2 and C3 back onto GAC queue
At this stage
Dom(X) = Dom(Y) = Dom(Z)
X = 1 – inconsistent
X = 2 – (X=2, Y=1, Z=1) X = 3 – (X=3, Y=1, Z=2)
Y = 1 – same support as X=2
Y = 2 – (X=3, Y=2, Z=1) Y = 3 – inconsistent
= {1, 2, 3}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
4

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ Process C3 next current domains: 3 Dom(X) = {2, 3}
Dom(Y) = {1, 2}
Dom(Z) = {1, 2}
X = 2 – {X=2, W=4, Y=1, Z=1} X = 3 – {X=3, W=5, Y=1, Z=1}
Y = 1 – found support
Y = 2 – {X=2, W=5, Y=2, Z=1}
Z = 1 – found support
Z = 2 – {X=2, W=5, Y=1, Z=2}
Dom(W) = {3,4,5}
W = 3 inconsistent
W = 4 – found support W = 5 – found support
Pruned domains W = {4, 5}
C2 already on GAC queue
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
5

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ Process C2 next current domains: 3 Dom(X) = {2, 3}
Dom(W) = {4,5}
X = 2 – {X=2, W=4} X = 3 – {X=3, W=4}
W = 4 – found support W = 5 – {X=3, W=5}
No Domains pruned. Nothing added to queue
Queue Empty
GAC finished.
GAC domains: X = {2,3}
Z = {1, 2}
Y = {1, 2}
W = {4,5}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
6

follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
GAC Example
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol
DWO).
3. Say we have 4 variables X, Y , Z, and W , with the following domains of values:
(a) Dom[X] = {1,2,3,4} (b) Dom[Y ] = {1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W ] = {1,2,3,4,5} And 3 constraints:
(a) C1(X,Y,Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W ) which is satisfied only when W = X + Z + Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
§ Note GAC enforce does not find a 3 solu8on
To find a solu8on we must use do search while enforcing GAC.
§ Branch on X. X = 2
GAC(C1)èY = 1, Z=1 GAC(C2) è no changes GAC(C3)èW = 4
This is a solu8on.
§ Branch on X = 3 GAC(C1)èno changes GAC(C2)èno changes GAC(C3)èPrune W=4
Prune Y = 2 Prune Z = 2 Current Domains
X={3}, Y={1}, Z={1}, W={5} GAC(C1) è Prune Y={1} DWO
NOTE No solu8on with X=3 but X=3 not pruned by GAC enforce.
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto,
7

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C3(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
§ Dom[V1]…Dom[V5] = {a, b, c}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
8

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C3(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
§ V1=C: no support § V2=C: no support § V3=A: no support
§ V1={a,b} § V2={a,b} § V3={b,c}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
9

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C3(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
§ V1=C: no support § V2=C: no support § V3=A: no support
§ V1={a,b} § V2={a,b} § V3={b,c}
§ V4=A: no support § V5=A: no support § V5=C: no support
§ V4={C,B} § V5={B}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
11

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C2(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
§ V1=C: no support § V2=C: no support § V3=A: no support
§ V1={a,b} § V2={a,b} § V3={b,c}
§ V4=A: no support § V5=A: no support § V5=C: no support
§ V4={C,B} § V5={B}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
12

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C2(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
§ V1=C: no support § V2=C: no support § V3=A: no support
§ V1={a,b} § V2={a,b} § V3={b,c}
§ V4=A: no support § V5=A: no support § V5=C: no support
§ V4={C,B} § V5={B}
§ V2=A: no support § V3=B: no support
§ V2={B} § V3={C}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
13

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C2(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
§ V1=B has no support § V1={A}
§ V4={C,B} § V5={B}
§ V2={B} § V3={C}
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
14

Example
§ C1(V1,V2,V3)
§ C2(V1,V3,V4,V5)
§ C2(V2,V3,V5)
V1
V2
V3
A
B
C
B
A
C
A
A
B
V2
V3
V5
A
A
A
A
B
C
B
C
B
C
A
B
C
B
A
V1
V3
V4
V5
A
A
A
A
A
B
C
B
B
C
B
B
C
A
B
C
C
B
A
B
§ V1=B has no support § V1={A}
§ V4=B has no support § V4={B}
§ V5={B}
§ V3=C has no support
§ V2={B} § V3={C}
§ V3={} DWO
Fahiem Bacchus, CSC384 Introduc8on to Ar8ficial Intelligence, University of Toronto
15

Related Posts