陈佳楠,李 哲,李占山1,

1(吉林大学 软件学院,吉林 长春 130012)

2(吉林大学 计算机科学与技术学院,吉林 长春 130012)

3(符号计算与知识工程教育部重点实验室(吉林大学),吉林 长春 130012)

约束程序(constraint programming,简称CP)是一种求解组合优化问题的有效方法,在人工智能、运筹学、图论等诸多领域都有广泛的应用.并行计算是在不改变预期结果的情况下,同时对问题的多个部分进行处理的能力.随着计算机并行处理能力的发展,约束程序与并行计算的结合研究已成为被关注的领域,即并行约束程序.

针对并行约束程序的研究大致可分为以下几类:并行传播、搜索空间分割、组合算法和问题分解等[1].其中,并行传播是指并行执行在约束上的过滤算法,其研究意义在于利用并行计算提高约束传播的效率.但这种并行化操作并不简单,会出现变量论域的同步问题,具有一定的挑战性[2],因此只有少数有关并行传播的研究成果.比如:Rolf 等人[3]提出了维持约束网络并行相容性的两种传播模型,分别是使用共享中间论域的传播模型和使用局部中间论域的传播模型;李哲等人[4]给出了一种适合GPU 运算的并行弧相容算法AC4GPU.

由于缺少相应的表约束并行过滤算法,Rolf 等人提出的传播模型不能直接应用在对表约束的并行传播上.根据我们掌握的资料,目前还没有针对表约束并行传播的研究成果被公布.表约束是约束程序中最常用的约束类型之一,也被称为外延约束,每个约束在包含……