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

王震 等:优化简单表缩减算法求解因子分解编码实例 3531

combines the advantages of CT and STRbit that makes the memory as little as possible while ensuring the efficiency of solving.
Experimental results show that the proposed algorithm is competitive over a variety of instances with non-trivial intersections.
Key words: constraint programming; arc consistency; table constraint; simple tabular reduction; factor-decomposition encoding

约束程序(constraint programming,简称 CP)是人工智能领域的研究方向之一,主要用于解决组合搜索问题.
随着研究的深入,CP 被成功地应用在很多领域,例如时间规划、调度、配置等.表约束是 CP 中一种被广泛研究
的约束类型,它将约束用元组明确地定义出来.广义弧相容(generalized arc consistency,简称 GAC)是求解表约束
时使用的主要技术,GAC 算法通过识别并删除无效值来加快求解速度.回溯搜索算法是求解表约束的完备算法
之一,在回溯搜索树的每一个结点执行 GAC 算法来判断当前状态是否满足 GAC.当前,维持表约束 GAC 的经典
[2]
[4]
[5]
[6]
[1]
[3]
算法有简单表缩减(simple tabular reduction,简称 STR)算法 :STR2 、STR3 、STRbit 、CT 、STR-N 、
[8]
[9]
[7]
AdaptiveSTR 、STR2* 和多值决策图(multi-valued decision diagrams,简称 MDD)算法:MDDc 、MDD4 [10] 、
Compact-MDD [11] .
在 GAC 被广泛使用的同时,高阶相容性也引起了人们的重视,例如关系相容、最大受限成对相容、成对相
容(pairwise consistency,简称 PWC) [12] 和完全成对相容(full pairwise consistency,简称 fPWC).fPWC 是一种既满
足 GAC 又满足 PWC 的相容性,也就是说:如果一个问题满足 GAC,那么它不一定满足 fPWC.当前,有两种方式
可以用来实现 fPWC.一种方式为原始数据编码,比如 k-交叉编码(k-interleaved encoding) [13] 、因子编码(factor
encoding,简称 FE) [14] 和因子分解编码(factor-decomposition encoding,简称 FDE) [15] 等.FDE 是目前效率最高的编
码方式,通常与 STR 算法一起使用.另一种方式为在传播过程中维持高阶相容性,主要算法包括 maxRPWC [16] 、
maxRPWC+ [17] 、eSTR [18] 、PW-AC [19] 和 PW-CT [20] 等.这些算法在维持 GAC 的基础上进行额外的检查,当前效率
最高的算法是 PW-CT.
通过对维持 GAC 与 fPWC 的主要算法分析,当前效率最高的算法都使用了 bitset 的数据结构,例如 CT,
STRbit,PW-CT 等.FDE 是一种将一个约束网络进行编译,形成一个新的约束网络的编码方法.在这个新的约束
网络上,维持 GAC 等价于在原始约束网络上维持 fPWC.我们发现,当前使用 bitset 的算法在求解这个新的约束
网络时有较高的空间复杂度,可能造成内存溢出问题.这是因为通过 FDE 形成的约束网络的规模要大于原始的
约束网络,甚至是它的好几倍.因此在本文中,我们提出了 STRFDE 算法——一种使用 bitset 结构来求解 FDE 实
例的方法.它结合了 CT 和 STRbit 的优势,在保证求解效率的同时,使占用的内存尽可能小.
在本文中,STRFDE 根据 FDE 的特性将整个约束网络分解为两个部分,并对这两个部分使用不同的算法.我
们说明了针对不同的约束使用不同的算法是合理的.PW-CT,eSTR 和其他 PWC 算法不能直接在主流求解器上
实现,这是因为它们的约束不能独立传播.但是,STRFDE 可以直接在主流求解器上实现.实验结果表明了,
STRFDE 在大多数实例上的效率要比 PW-CT 和 STR2+FDE 高并且在一些实例上要高于 CT.
1 背景知识

约束满足问题(constraint satisfaction problem,简称 CSP)是判断一个约束网络 N 是否有解.约束网络可以表
示为 N=(X,C),其中,X 是由 n 个变量组成的变量集合:X={x 1 ,x 2 ,…,x n },C 是由 e 个约束组成的约束集合:C={c 1 ,
c 2 ,…,c e },D(x)表示变量 x 对应的论域.为了简便,我们称(x,a)为一个值,若满足 x∈X 且 a∈D(x).例如,(x,3)是一个变
量值.
每个约束 c∈C 都包含一个变量集合 scp(c)和一个元组集合 rel(c).scp(c)={x 1 ,x 2 ,…,x r }是变量集合 X 的一个
子集,表示约束所涉及的变量.rel(c)是变量论域笛卡尔积{D(x 1 )×D(x 2 )×…×D(x r )}的子集,表示约束的有效元组.
t=(a 1 ,a 2 ,…,a r )是约束 c 的一个元组,t∈rel(c).对于 x i ∈scp(c),对应的值表示为 t(x i ).元组 t 是有效的当且仅当对于
任意的 x i ∈scp(c),满足 t(x i )∈D(x i );否则 t 是无效的.如果元组 t 是有效的,则称 t 为约束 c 的一个支持.若 t 为约束
c 的一个支持且 t(x i )=a,则称 t 为(x i ,a)的一个支持.若元组集 rel(c i )中的元组 t i 与元组集 rel(c j )中的元组 t j 满足
t i [scp(c i )∩scp(c j )]=t j [scp(c i )∩scp(c j )],且 t i 和 t j 是有效的,那么我们称 t i 是 t j 的 PW 支持.我们称 c i 和 c j 为非平凡相