GAC 算法实例
GAC 算法
实例
变量及其值域：
Dom[X] = { 1, 2, 3, 4 }
Dom[Y] = { 1, 2, 3, 4 }
Dom[Z] = { 1, 2, 3, 4 }
Dom[W] = { 1, 2, 3, 4, 5 }
约束：
C1: X = Y + Z
C2: W > X
C3: W = X + Y + Z
开始 GAC(0)
取未赋值的变量 X
令 X = 1
X: { 1 }
GACQueue: { C1, C2, C3 }
-
GAC Enforce
-
GACQueue 弹出 C1: X = Y + Z
GACQueue = { C2, C3 }
Scope(C1) = { X, Y, Z }
X: { 1 }
Y: { 1, 2, 3, 4 }
Z: { 1, 2, 3, 4 }
W: { 1, 2, 3, 4, 5 }
-
取 V = X，则 CurDom[V] = { 1 }
-
取 d = 1
找出使得 C1 满足的 A = { Y, Z }。
找不到，CurDom[X] = {}，返回 DWO。
-
-
-
令 X = 2
X: { 2 }
GACQueue: { C1, C2, C3 }
-
GAC Enforce
-
GACQueue 弹出 C1: X = Y + Z
GACQueue = { C2, C3 }
Scope(C1) = { X, Y, Z }
X: { 2 }
Y: { 1, 2, 3, 4 }
Z: { 1, 2, 3, 4 }
W: { 1, 2, 3, 4, 5 }
-
取 V = X，则 CurDom[V] = { 2 }
-
取 d = 2
找出使得 C1 满足的 A = { Y, Z }。
找到 A = { Y = 1, Z = 1 }。
-
-
取 V = Y，则 CurDom[V] = { 1, 2, 3, 4 }
-
取 d = 1
找出使得 C1 满足的 A = { X, Z }。
找到 A = { X = 2, Z = 1 }。
-
取 d = 2
找出使得 C1 满足的 A = { X, Z }。
找不到，CurDom[Y] = { 1, 3, 4 }。
GACQueue = { C2, C3, C1 }。
-
取 d = 3
找出使得 C1 满足的 A = { X, Z }。
找不到，CurDom[Y] = { 1, 4 }。
GACQueue = { C2, C3, C1 }。
-
取 d = 4
找出使得 C1 满足的 A = { X, Z }。
找不到，CurDom[Y] = { 1 }。
GACQueue = { C2, C3, C1 }。
-
-
取 V = Z，则 CurDom[V] = { 1, 2, 3, 4 }
-
取 d = 1
找出使得 C1 满足的 A = { X, Y }。
找到 A = { X = 2, Y = 1 }。
-
取 d = 2
找出使得 C1 满足的 A = { X, Y }。
找不到，CurDom[Z] = { 1, 3, 4 }。
GACQueue = { C2, C3, C1 }。
-
取 d = 3
找出使得 C1 满足的 A = { X, Y }。
找不到，CurDom[Z] = { 1, 4 }。
GACQueue = { C2, C3, C1 }。
-
取 d = 4
找出使得 C1 满足的 A = { X, Y }。
找不到，CurDom[Z] = { 1 }。
GACQueue = { C2, C3, C1 }。
-
-
-
GACQueue 弹出 C2: W > X
GACQueue = { C3, C1 }
Scope(C2) = { X, W }
X: { 2 }
Y: { 1 }
Z: { 1 }
W: { 1, 2, 3, 4, 5 }
-
取 V = X，则 CurDom[V] = { 2 }
-
取 d = 2
找出使得 C2 满足的 A = { W }。
找到 A = { W = 3 }。
-
-
取 V = W，则 CurDom[V] = { 1, 2, 3, 4, 5 }
-
取 d = 1
找出使得 C2 满足的 A = { X }。
找不到，CurDom[W] = { 2, 3, 4, 5 }。
GACQueue = { C3, C1, C2 }。
-
取 d = 2
找出使得 C2 满足的 A = { X }。
找不到，CurDom[W] = { 3, 4, 5 }。
GACQueue = { C3, C1, C2 }。
-
取 d = 3
找出使得 C2 满足的 A = { X }。
找到 A = { X = 2 }。
-
取 d = 4
找出使得 C2 满足的 A = { X }。
找到 A = { X = 2 }。
-
取 d = 5
找出使得 C2 满足的 A = { X }。
找到 A = { X = 2 }。
-
-
-
GACQueue 弹出 C3: W = X + Y + Z
GACQueue = { C1, C2 }
Scope(C3) = { X, Y, Z, W }
X: { 2 }
Y: { 1 }
Z: { 1 }
W: { 3, 4, 5 }
-
取 V = X，则 CurDom[V] = { 2 }
-
取 d = 2
找出使得 C3 满足的 A = { Y, Z, W }。
找到 A = { Y = 1, Z = 1, W = 4 }。
-
-
取 V = Y，则 CurDom[V] = { 1, 2, 3, 4 }
-
取 d = 1
找出使得 C3 满足的 A = { X, Z, W }。
找到 A = { X = 2, Z = 1, W = 4 }。
-
-
取 V = Z，则 CurDom[V] = { 1 }
-
取 d = 1
找出使得 C3 满足的 A = { X, Y, W }。
找到 A = { X = 2, Y = 1, W = 4 }。
-
-
取 V = W，则 CurDom[V] = { 3, 4, 5 }
-
取 d = 3
找出使得 C3 满足的 A = { X, Y, Z }。
找不到，CurDom[W] = { 4, 5 }。
GACQueue = { C1, C2, C3 }。
-
取 d = 4
找出使得 C3 满足的 A = { X, Y, Z }。
找到 A = { X = 2, Y = 1, Z = 1 }。
-
取 d = 5
找出使得 C3 满足的 A = { X, Y, Z }。
找不到，CurDom[W] = { 4 }。
GACQueue = { C1, C2, C3 }。
-
-
-
GACQueue 弹出 C1: X = Y + Z
GACQueue = { C2, C3 }
Scope(C1) = { X, Y, Z }
X: { 2 }
Y: { 1 }
Z: { 1 }
W: { 4 }
都能找到 A。
-
GACQueue 弹出 C2: W > X
GACQueue = { C3 }
Scope(C2) = { X, W }
X: { 2 }
Y: { 1 }
Z: { 1 }
W: { 4 }
都能找到 A。
-
GACQueue 弹出 C3: W = X + Y + Z
GACQueue = {}
Scope(C3) = { X, Y, Z, W }
X: { 2 }
Y: { 1 }
Z: { 1 }
W: { 4 }
都能找到 A。
-
GACQueue 为空，返回 True。
-
GAC Enforce 结果不为 DWO，说明所有约束都满足。
将 X 赋值为 2。
递归调用
调用 GAC(1)、GAC(2)、GAC(3)、GAC(4)，直到所有变量都被赋值，得到一个解 { X = 2, Y = 1, Z = 1, W = 4}。