CSP解的存在性问题是NP完全的。 因此，一些方法已经发展起来，以简化CSP之前或期间的搜索解决方案。 一致性技术是最常用的技术。对于二进制CSP和N元CSP提出了几种实现弧一致性的算法。
引入的特殊约束的算法AC-4进行了改进，研究了单调和泛函二元约束。 在本工作中，我们对n元约束的一个特殊情况：“不同约束”感兴趣，为此我们提出了一个过滤算法。
如果一个约束在变量子集上被一组元组定义，而在同一元组中出现的值都是不同的，则称为“不同约束”。 它们存在于现实生活中的许多问题中。
这些约束可以表示为n元约束，并用广义弧一致性算法GAC4进行分层。 这种过滤会减少域，但它的复杂性可能会很昂贵。 事实上，它取决于所有可容许元组的长度和数目。 让我们考虑p个变量的“不同约束”，p个变量的值取自基数D的集合。 因此，允许元组的数目对应于从d个元素中选择的p个元素不重复的排列数目：d Pp=d！/（d- p）！ .
因此，一些约束解析系统，用一组二进制约束来表示这些n元约束。 在这种情况下，对属于同一“不同约束”的每对变量建立一个不同的的二元约束。
但由于这些约束条件，圆弧一致性的剪枝性能较差。 实际上，对于两个变量i和j之间的二元Alldierent约束，只有当j的定义域减少到一个值时，弧一致性才从i的定义域中移除一个值。
让我们假设我们有一个具有3个变量x1，x2，x3和这些变量之间的一个不同约束的CSP（图1） 变量的定义域为D 1 = {a, b} , D 2 ={a, b} and D 3 ={a, b,c} . GAC4用一个三元约束表示的不同约束消除了x3域中的a和b值，而用不同的二元约束表示的不同约束的弧一致性不删除任何值。
本文给出了一种实现广义弧一致性条件的有效方法，以便从它的剪枝性能上得到更好的结果。 其空间复杂度为O(Pd)，时间复杂度为O(P2d2)。
论文的其余部分组织如下。 第2节对约束满足问题和匹配问题作了一些初步的探讨，并提出了一种仅涉及约束条件的弧一致性约束表示：双弧一致性。 第3节提出了一个新的条件来保证CSPS中的双弧一致性。 在第4节中，我们提出了一个ECIANT实现来实现这个条件，并分析了它的复杂性。 在第五节中，我们用一个例子说明了它的性能和它的兴趣。 第六节给出了结论。
基本定义
变量x i的域中的值a i与给定的n元约束一致，如果约束中的所有其他变量都存在值使得这些值与a i同时满足该约束。 更一般地说，n元CSP的弧一致性或广义弧一致性如下[Mohr和Masini,1988a]
从前面的定义中，我们提出了一个特殊的弧一致性，它只涉及“不同的约束”：
如果X中的每个顶点都是匹配（M）中边的端点，则匹配（M）覆盖集合X。
注意，在二分图G=(X；Y；E）中覆盖X的匹配一定是最大匹配。 （无共同接节点的边集合叫做匹配，那么所有节点一节点对应一个边，一定数量最大，一定四最大匹配）
在下一节中，我们从匹配的定义和值图的定义出发，给出了一个新的必要条件，以保证diff-arc-consistency 在constraints of difference的CSPs上。
下面的定理在constraints of difference的值图中建立了diff-arc-consistency 和匹配概念之间的联系。
证明：
=>让我们考虑一个constraints of difference和它的值图GV©的约束。 从C的每个可容许元组中，可以建立一组对。 对由元组中的变量及其赋值组成。 对集包含每个变量的对。 这个集合对应于一组边，在GV©中用A表示。 由于p是双弧一致的，所以每个元组中的值都是双弧一致的。 因此，A的两条边不可能有一个公共顶点，A是覆盖X C的匹配。 而且，约束中每个变量的每个值都属于至少一个元组。 因此，GV©的每条边都属于覆盖X的匹配
<=
让我们考虑一个变量x i和它的定义域的一个值a。 对于constraints of difference C的每一个约束，对（x i,a）都属于GV©中覆盖x c的匹配。 由于在匹配中没有两条边有一个共同的顶点，所以约束中的所有其他变量都存在值，使得这些值同时满足约束。 所以P是双弧一致的。
这个定理给我们提供了一种在CSP中表示constraints of difference 约束的有效方法。 实际上，一个constraints of difference 约束只能用它的值图来表示，空间复杂度为O(pd)。 它还允许我们给出一个基本的算法（算法1）来过滤一个 在其上被constraints of difference约束的集合的变量域。 该算法通过建立迭代约束的值图，计算一个覆盖Xc的匹配，以删除所有不属于匹配覆盖Xc的边（delete every edge which belongs to no matching covering Xc）匹配不覆盖。 图3给出了这种轻量化的应用程序。
为了简化表示法，我们考虑了一个二分图G=(x，y，e）而不是二分图G=(Xc,D(Xc)，e）和一个在G中覆盖X的匹配M。为了理解我们如何删除所有不属于匹配的边（不匹配），我们提出了一些关于匹配理论的定义。 欲了解更多信息，读者可以咨询[Berge，1970]或[Lovasz and Plummer，1986]
一个属于每个最大匹配的边是至关重要的。
图3给出了一个在二分图中覆盖x的匹配示例。 粗边是匹配的边。 顶点7是自由的。 路径（7,x6,6,x5,5）是从自由顶点开始的交替路径。 循环（1,x3,3,x2,2,x1,1）是一个交替循环。 边缘(x4,4)是至关重要的。
每个matching序列当中个都有元素（x4,4）因此是vital
根据这个性质，我们可以得到一个覆盖X的任意匹配M，每条不属于匹配覆盖X的边（delete every edge which belongs to no matching covering Xc）。有一些边既不属于M（不属于重要），也不属于从自由顶点开始的偶数交替路径，也不属于偶数交替循环。
证明
1）如果我们忽略等价，很明显这个命题是真的。 在第一种情况下，由于G是二部的，所以它没有任何奇圈。
2）在第二种情况下，我们必须证明G O的每一条从自由顶点开始的有向简单路径对应于G的一条从自由顶点开始的偶数交替路径。 M是覆盖X的匹配，所以X中没有自由顶点。由于G是二部的，并且由于每条路径都从一个自由顶点开始，所以在Y中，每条奇数有向简单路径都以X中的一个顶点结束。从这个顶点出发，我们总是可以在Y中找到一个不属于该路径的顶点，因为X中的每一个顶点都有一个后继，而Y中的一个顶点都有一个前驱。 因此，从一个奇数有向简单路径，我们总是可以建立一个偶数有向简单路径。
这个问题可以表示为一个包含25个变量的约束网络，每个变量对应5个颜色、饮料、国籍、香烟和宠物：
每个变量具有域值{1，2， 3， 4，5}，每个数字对应一个房子位置（例如将值2赋给可变马意味着马主人住在第二个房子里）[Dechter，1990]。 断言2到15被转换为一元和二元约束。 此外，有三种表示第一个断言的方法，这意味着同一集群中（颜色、饮料、国籍、香烟和宠物）的变量必须采用不同值：
第一种表示法通常被用来解决这个问题[Dechter，1990；Bessiere和Cordier，1993]。 从这三种表示形式出发，我们可以研究弧相合的一些结果。 它们在图4和5中给出。 对应于断言2到15的约束在扩展中表示。 为了清楚起见，省略了各聚类变量之间的不确定性约束。
本文给出了CSPS中的一种离散约束的过滤算法。 该算法可以看作是实现一类特殊约束&离散约束的广义弧一致性条件的一种有效方法。 它使我们能够以较低的复杂度从前面条件的剪枝性能中获得提高。 实际上，对于一个约束条件，其空间复杂度为O(Pd)，时间复杂度为O(P2，d2)。 它已经被证明对斑马问题非常有效。 并成功地用于复杂有机合成方案的计算机辅助设计系统Resyn[Vismara et al.，1992]中的子图同构问题的求解。
