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}。

Updated: