Page 146 - 《软件学报》2021年第9期

2770 Journal of Software 软件学报 Vol.32, No.9, September 2021

Key words: constraint satisfaction problem; parallel propagation; generalized arc consistency; table constraint; simple tabular reduction

约束程序(constraint programming,简称 CP)是一种求解组合优化问题的有效方法,在人工智能、运筹学、图
论等诸多领域都有广泛的应用.并行计算是在不改变预期结果的情况下,同时对问题的多个部分进行处理的能
力.随着计算机并行处理能力的发展,约束程序与并行计算的结合研究已成为被关注的领域,即并行约束程序.
[1]
针对并行约束程序的研究大致可分为以下几类:并行传播、搜索空间分割、组合算法和问题分解等 .其中,
并行传播是指并行执行在约束上的过滤算法,其研究意义在于利用并行计算提高约束传播的效率.但这种并行
[2]
化操作并不简单,会出现变量论域的同步问题,具有一定的挑战性 ,因此只有少数有关并行传播的研究成果.比
[3]
如:Rolf 等人 提出了维持约束网络并行相容性的两种传播模型,分别是使用共享中间论域的传播模型和使用
[4]
局部中间论域的传播模型;李哲等人 给出了一种适合 GPU 运算的并行弧相容算法 AC4 GPU .
由于缺少相应的表约束并行过滤算法,Rolf 等人提出的传播模型不能直接应用在对表约束的并行传播上.
根据我们掌握的资料,目前还没有针对表约束并行传播的研究成果被公布.表约束是约束程序中最常用的约束
类型之一,也被称为外延约束,每个约束在包含的变量集上显式地列举出所有支持或禁止的取值组合.表约束理
论上可以编码任何类型的约束,在许多应用程序领域中,当对组合问题进行建模时,常常需要使用它们.
维持表约束网络广义弧相容(generalized arc consistency,简称 GAC)的串行传播模式由串行传播算法和串
行过滤算法两部分组成,串行传播算法串行执行维持表约束 GAC 的串行过滤算法.过去的十多年中,维持表约
束 GAC 的串行过滤算法研究已经公布了大量的成果,其中具有代表性的系列成果是基于简单表缩减的串行过
滤算法(若无特殊说明,后文的过滤算法均指基于简单表缩减的过滤算法).比如:STR(simple tabular reduction) [5]
[6]
能够动态地维持表约束的有效元组;在 STR 的基础上,STR2 在检查元组的有效性和收集被支持的取值时仅考
[7]
[8]
虑相关的变量子集;STR3 通过使用 dual table 等数据结构,避免了不必要的表遍历;STRbit 采用位向量编码
[9]
dual table,大幅度地提升了过滤效率;CT(compact table) 使用以位向量为基础的 sparse bit-sets,进一步加快了过
滤速度;STR-N [10] 能够直接作用于负表约束,其求解效率具有明显的优势;AdaptiveSTR [11] 通过自适应地检测并
删除无效元组,改进了 STR3,使得算法速度显著提升;STR2* [12] 采用了一种动态维持元组集有效部分的全新方
法,拥有比 STR2 和 STR3 更高的效率.
根据维持表约束网络 GAC 的串行传播模式,我们提出了维持表约束网络临时广义弧相容(temporary
generalized arc consistency,简称 TGAC)的并行传播模式.该模式基于多核 CPU,由并行传播算法和并行过滤算法
两部分组成,并行传播算法利用线程池并行执行维持表约束 TGAC 的并行过滤算法.之后,我们给出了并行传播
模式的可靠性证明,即并行传播模式也维持表约束网络 GAC.接下来,我们分析了并行传播模式的最坏时间复杂
度,并将其与串行传播模式的最坏时间复杂度进行对比;经过分析对比,我们认为,并行传播模式在平均过滤时
间较长的实例上要快于串行传播模式.最终的实验结果也验证了上述结论,而且并行传播模式在多数实例集上
取得了从 1.4~3.4 不等的加速比.
本文第 1 节介绍相关的背景知识.第 2 节回顾维持表约束网络 GAC 的串行传播模式.第 3 节给出维持表约
束网络 TGAC 的并行传播模式.第 4 节展示实验结果.第 5 节做出工作总结和未来展望.
1 背景知识

1.1 约束满足问题
一个约束网络 N 由一个变量集 X 和一个约束集 C 组成,其中:X 包含 n 个变量,C 包含 e 个约束.每个变量 x
有一个初始论域 D(x),D(x)是 x 的初始取值集合;dom(x)表示在回溯搜索中变量 x 的当前论域(若无特殊说明,后
文的论域均指当前论域),(x,a)表示变量 x 在 dom(x)中的取值 a.每个约束 c 都包含一个有序的变量集合 scp(c),
scp(c)被称为 c 的作用域,是变量集 X 的子集.相应地,每个变量 x 有一个约束订阅集 sbp(x)={c|x∈scp(c)}.约束 c
的元数 r 为|scp(c)|,即 c 所包含的变量个数.约束 c 在语义上由一个关系 rel(c)定义,rel(c)包含 c 所允许的元组集
合.(正)表约束 c 通过列出所允许的元组来表示 rel(c).约束网络 N 的解是对所有变量的一组赋值,这组赋值满足