在 Java 中实现 'generalized arc consistency' 算法有些困难
Having some difficulty implementing a 'generalized arc consistency' algorithm in Java
这是我试图在 Java 中实现的算法...
（没有完全正确地格式化，所以在 link 上查看它可能更容易，只需从它带给你的地方向上滚动半页 http://artint.info/html/ArtInt_79.html#AC-3-fig ）
1: procedure GAC(V,dom,C)
2: Inputs
3: V: a set of variables
4: dom: a function such that dom ( X ) is the domain of variable X
5: C: set of constraints to be satisfied
6: Output
7: arc-consistent domains for each variable
8: Local
9: D X is a set of values for each variable X
10: TDA is a set of arcs
11: for each variable X do
12: D X ← dom ( X )
13: TDA ← {? X,c ?| c ∈ C and X ∈ scope ( c )}
14: while TDA ?= {} do
15: select ? X,c ? ∈ TDA;
16: TDA ← TDA \ {(X,c)} ;
17: ND X ← { x | x ∈ D X and some { X = x,Y 1 = y 1 ,...,Y k = y k } ∈ c where y i ∈ D Y i for all i }
18: if ND X ?= D X then
19: TDA ← TDA ∪ {? Z,c ? ?| X ∈ scope ( c ? ) , c ? is not c, Z ∈ scope ( c ? ) \ { X }}
20: D X ← ND X
21: return { D X | X is a variable }
我不明白第 16 和 17 行到底在做什么。通过第 16 行中的 "TDA ← TDA \ {(X,c)} ;"，反斜杠是否意味着我们从 TDA 中删除该弧？
然后，在第 17 行，我们似乎在说 X 的新域是旧域中已经存在的任何内容，并与 does/doesn 不满足约束的所有内容进行 AND 运算。这基本上是正确的吗？
第 16 行是可变集差异：从集 TDA.
中删除 (X,c)
第 17 行是集合生成器表示法：将 ND X（我认为它的意思类似于 "New domain of X"）设置为所有元素 x 的集合，其中 x 在X 的域，并且还存在一组相等的对，它们是集合 c 的一个元素，包括 X=x、Y1=y1 到 Y_k=y_k，其中这些对满足 y_i\in domain(Y_i) 所有 i=1,2,...k。换句话说，这是对集 c.
的花式过滤查询
第 17 行有点模棱两可，因为从未指定 k。在这种情况下，人们通常可以自由地推断它可以取任何值。因此，内部集合可以是 {X=x} 或 {X=x,Y1=y1} 等，具有任意数量的 Y_=y_ 对。
这是我试图在 Java 中实现的算法... （没有完全正确地格式化，所以在 link 上查看它可能更容易，只需从它带给你的地方向上滚动半页 http://artint.info/html/ArtInt_79.html#AC-3-fig ）
1: procedure GAC(V,dom,C)
2: Inputs
3: V: a set of variables
4: dom: a function such that dom ( X ) is the domain of variable X
5: C: set of constraints to be satisfied
6: Output
7: arc-consistent domains for each variable
8: Local
9: D X is a set of values for each variable X
10: TDA is a set of arcs
11: for each variable X do
12: D X ← dom ( X )
13: TDA ← {? X,c ?| c ∈ C and X ∈ scope ( c )}
14: while TDA ?= {} do
15: select ? X,c ? ∈ TDA;
16: TDA ← TDA \ {(X,c)} ;
17: ND X ← { x | x ∈ D X and some { X = x,Y 1 = y 1 ,...,Y k = y k } ∈ c where y i ∈ D Y i for all i }
18: if ND X ?= D X then
19: TDA ← TDA ∪ {? Z,c ? ?| X ∈ scope ( c ? ) , c ? is not c, Z ∈ scope ( c ? ) \ { X }}
20: D X ← ND X
21: return { D X | X is a variable }
我不明白第 16 和 17 行到底在做什么。通过第 16 行中的 "TDA ← TDA \ {(X,c)} ;"，反斜杠是否意味着我们从 TDA 中删除该弧？
然后，在第 17 行，我们似乎在说 X 的新域是旧域中已经存在的任何内容，并与 does/doesn 不满足约束的所有内容进行 AND 运算。这基本上是正确的吗？
第 16 行是可变集差异：从集 TDA.
(X,c)
第 17 行是集合生成器表示法：将 ND X（我认为它的意思类似于 "New domain of X"）设置为所有元素 x 的集合，其中 x 在X 的域，并且还存在一组相等的对，它们是集合 c 的一个元素，包括 X=x、Y1=y1 到 Y_k=y_k，其中这些对满足 y_i\in domain(Y_i) 所有 i=1,2,...k。换句话说，这是对集 c.
第 17 行有点模棱两可，因为从未指定 k。在这种情况下，人们通常可以自由地推断它可以取任何值。因此，内部集合可以是 {X=x} 或 {X=x,Y1=y1} 等，具有任意数量的 Y_=y_ 对。