Page 206 - 《软件学报》2021年第11期

3532 Journal of Software 软件学报 Vol.32, No.11, November 2021

交,当且仅当 c i 和 c j 满足|scp(c i )∩scp(c j )|>1.
定义 1. GAC.
• 变量值(x,a)在约束 c 上是 GAC 的当且仅当任意包含 x 的约束中存在对(x,a)有效的支持;
• 变量 x 是 GAC 的当且仅当 D(x)中所有变量值是 GAC 的;
• 约束 c 是 GAC 的当且仅当 scp(c)中所有变量是 GAC 的;
• 约束网络是 GAC 的当且仅当所有约束是 GAC 的.
定义 2. PWC.
• 约束 c i 中的元组 t 是 PWC 的当且仅当任意 c j ∈C 中存在对 t 的 PW 支持;
• 约束 c i 是 PWC 的当且仅当约束 c i 的所有元组是 PWC 的;
• 约束网络是 PWC 的当且仅当所有约束是 PWC 的.
定义 3. fPWC.
若一个约束网络既满足 PWC 又满足 GAC,那么此约束网络是 fPWC 的.
如图 1(a)所示,对偶图的顶点表示约束网络的约束,边表示两个约束之间涉及相同的变量,边的权值表示涉
及的相同变量.Janssen 等人 [12] 和 Dechter [21] 发现,当两个顶点之间存在至少一条长度大于 1 的路径,且这条路径
上的每个顶点都包含这两个顶点相同的变量,那么这两个顶点之间的边是多余的.例如,R 1 和 R 4 之间的边是多余
的,它们存在路径 R 1 R 2 R 4 且 R 2 也包含变量 A.将一个对偶图所有的冗余边删除得到的图,称为最小对偶图,如图
1(b)所示.

Fig.1 Dual graph and its minimal dual graph
图 1 Dual 图和它的最小对偶图

最小对偶图是对偶图的一个简化,一个对偶图可能有多个最小对偶图.最小对偶图和对偶图拥有相同的表
达能力,不会影响算法的正确性.前人的研究工作已经证明,使用最小对偶图比使用对偶图效率更高 [20] .因此在
本文中,我们实现的所有 fPWC 算法都是基于最小对偶图的.

2 STRFDE

在本节中,我们首先描述算法的基本思想并给出伪代码,然后对算法的复杂度进行证明.FDE 是一种将一个
约束网络进行编译形成一个新的约束网络的编码方法,在这个新的约束网络上维持 GAC,等价于在原始约束网
络上维持 fPWC.这个新的约束网络中的约束具有不同的特征,我们根据这些特征将约束分为两部分:附加约束
和原始约束.
ori
针对这两种约束,我们提出了不同的算法模型,因此,STRFDE 包含两种算法:STRFDE add 和 STRFDE .
使用不同的算法来处理不同的约束是合理的.每个约束在搜索过程中是相对独立的,它们拥有私有的属性,
并根据相同的变量连接起来,我们只需要将变量的改变传播给相应的约束,就能判断当前问题是否相容.在解决
一个实例时,根据约束的特征选择合适的算法会提升求解效率.
STRFDE add 和 STRFDE ori 是相对独立的,可以在主流求解器中直接实现.为了更好地介绍它们,我们给出一
些定义.
定义 4(平凡变量). 经 FDE 处理之后,变量论域未改变的变量是平凡变量.