约束满足问题(CSP)是人工智能领域的重要的研究问题,它为计算机、数学、实际生产生活等领域的复杂问题的建模与求解提供了足够泛化的通用工具。约束满足性问题是计算机领域研究的经典NP-hard问题,求解约束满足性问题是在庞大解空间中得到一组或多组的求解实例,或者证明其无解。约束网络是求解约束满足性问题的一种重要模型,在约束网络中,顶点表示变量,边代表变量之间存在的约束关系。约束满足问题的求解算法即在约束网络上遵照某种传播策略,对变量进行赋值、维持相容性等操作,使得网络变量关联的所有约束条件都得到满足。不同的传播策略对问题求解效率具有重要影响。传统的传播策略缺陷是当约束网络局部发生改变(变量论域修订)时,导致相容性破坏,再次扩大搜索空间,所以本文给出一种分成两阶段的对偶的传播模式,结果表明相比于现有传播模式,可以有效降低冗余操作,进而提升维持弧相容的效率。相比传统的传播策略,本文提出的双向传播策略能够以较低的开销排除冗余的修订,减少扩展单个节点的平均修订次数,使维持弧相容的代价进一步降低,获得求解速度上的提升。在标准测试数据集中,双向传播策略与传统方法相比,具有最低修订次数。对于连通度较高的约束网络,变量之间的约束关系更加紧密,维持相容性的代价更高,该方法的修订次数的降低比较显著,在部分测试数据集中,该方法相比传统方法平均修订次数减少17%,相应地,整体求解时间减少10%。另外,现有的弧相容算法设计思路均是基于“传播”的思想,即约束网络局部发生改变,继而相容性破坏,引起其关联的其他部分的修改来重新实现相容性,这种思路具有良好的增量运算性质,但也限制了无法实现并行的弧相容维持,为了解决这个问题,本文提出一种方法,将弧相容设计成一种全局迭代的维持过程,利用矩阵操作维持弧相容,牺牲了增量运算的特性,但整个过程实现了完整的并行化。矩阵操作中依赖的算子在现有的广泛采用的框架(如numpy,pytorch,tensorflow)中均有实现,因此借助于这些框架,大大简化了算法设计。由于整个相容性维持过程均被表示成了矩阵操作,因此相容性维持可以完整地在GPU上执行,实验结果表明,在稠密连接的复杂约束网络上,相比现有算法,这种并行维持弧相容方法的效率获得了显著提升。传统串行方法的平均修订次数远大于基于矩阵表示的并行方法的迭代次数,当变量个数达到700时,传统串行方法的修订次数达到18万次,而并行方法迭代次数基本维持在3.5到4.5次之间。相应的,比较扩展一个节点的平均耗时,并行运算方法比传统方法性能提升100倍。