Page 137 - 《软件学报》2021年第5期

王晓峰 等:可满足性问题中信念传播算法的收敛性分析 1361

一个子句 C 是若干个文字的析取(即 C=L 1 ∨L 2 ∨…∨L n ),子句 C 可以视为文字的集合(即 C={L 1 ,L 2 ,…,L n }).一
个合取范式(conjunctive normal form,简称 CNF)公式(以下简称公式)F 是若干个子句的合取(即 F=C 1 ∧C 2 ∧…∧
C m ),公式 F 可以视为子句的集合(即 F={C 1 ,C 2 ,…,C m }).可满足性问题(satisfiability,简称 SAT)是指:给定一个公式
[1]
F,判定是否存在一组指派使得 F 为真 .SAT 问题是计算机科学中最为著名的 NP-完全问题,其理论及其应用研
究是计算机与数理逻辑界众多学者共同关注的一个重大问题.人工智能中的大多数难解问题,通过编码技术都
可转化为 SAT 问题.SAT 问题的 NP-完全性表明:在 P≠NP 条件下,不太可能存在多项式时间算法求解该问题.近
年来,随着人工智能的迅速发展,特别是大数据和物联网的发展,对 SAT 问题原有的求解算法需要重新审视和设
计,这为研究 SAT 问题提供了新的机遇和突破口.
目前,对于 SAT 问题的研究主要集中在两个方面:实例产生模型和求解算法.在实例产生模型研究中,获取
了一些影响实例可满足性的控制参数,如子句数目 m 和变元数目 n 之比值α=m/n.在 G(n,3,m)模型中,随机实例
的可满足与不可满足之间似乎存在一个阈值α d .当α的值小于α d 时,实例高概率满足;反之,高概率不可满足.该
阈值α d 称为满足与不可满足的相变点,当α的值接近α d 时实例往往是难解的 [2,3] .目前,尚无得到α d 的精确值,但
[4]
[5]
α d 的下界为 3.52 ,上界为 4.489 8 .许可等人的研究基于 B 模型和 D 模型,针对经典 CSP 实例产生模型的平
凡无解性问题,提出了具有精确相变点的实例产生模型,分别为 RB 和 RD 模型 [6−8] ,该模型被广泛应用于国际算
法竞赛测试.
基于实例的不可满足性是否能够给出完备性证明,SAT 算法分为完备算法和不完备算法.不完备算法相对
于完备算法而言,能够在短时间内求出问题的解,而完备算法的时间成本较大.因此,不完备算法得到了更为广
泛的应用.DPLL 算法是一种典型的完备求解算法,主要是利用单字句规则和分裂规则对公式进行化简,其执行
[9]
过程是一棵二叉搜索树 ,增加了算法的执行时间.为此,人们提出了各种各样的策略,进而出现了许多其他有效
的算法,如,基于 VSIDS 策略的 ZChaff 算法 [10] 、BerkMin 算法 [11] 、MiniSat 算法 [12] 、SATO 算法 [13] 、GRASP 算
法 [14] 、GSAT 算法 [15] 和 WALKSAT 算法 [16] 等等.
信息传播算法起源于统计物理领域 [17] .该算法是一种高效的边缘概率计算方法,在许多领域得到了广泛应
用 [18−29] .文献[30]中根据不同的随机 SAT 问题分别提出了 3 种基于因子图的信息传播算法,即警示传播(warning
propagation,简称 WP)算法、信念传播(belief propagation,简称 BP)算法和调查传播(survey propagation,简称 SP)
算法.在 3-SAT 随机实例中,该算法被验证非常有效,特别是 SP 算法与局部搜索算法相结合,几乎能够有效求解
难解可满足性实例 [30−33] .信息传播算法这种优秀的性能,引起了众多学者的关注,主要集中在两个方面:(1) 信息
传播算法的收敛性;(2) 信息传播算法的有效性.
所谓收敛性是指:信息传播算法两次信息迭代得到的值不变;有效性是指:信息传播算法能够有效求解问
题.目前,对信息传播算法的性能分析已取得一些重要的研究成果.文献[34−40]分析了信息传播算法的收敛性和
有效性,并给出了算法收敛的充分条件.文献[41,42]基于具体的实例产生模型分析了信息传播算法的收敛性,并
给出了算法收敛的概率条件.文献[43]利用压缩函数的相关性质给出了算法收敛的充分条件,该判定条件由于
受消息取值的限制(消息只能取 0 或 1),导致其应用范围较窄.在此基础上,文献[44]分析了调查传播算法的消息
取值在[0,1]区间上的收敛性,并给出算法收敛的一个充分条件.在高斯图模型中,信息传播算法常被用于计算均
值和方差.文献[45]基于高斯线性模型给出了信息传播算法收敛的充分必要条件,但局限于相邻变量不能共享
同一个因子.文献[46]基于信息矩阵分析了信息传播算法的收敛性,给出了一个充分必要条件,但局限于消息的
信息矩阵为正半定矩阵,并且主要用于判定高斯 BP 算法的收敛性.文献[47]得到了信息传播算法的一个收敛条
件,但该条件的证明需要基于双因素线性高斯模型,而该条件在一般问题上并不适用.文献[48]主要分析了求解
高斯模型中方差的信息传播算法的收敛性,但要求用一个半定规划来检查收敛性,检查效率较低且非常困难.文
献[49]分析了求解均值的信息传播算法的收敛性,要求估计有限尺度矩阵的谱半径,在实际应用中可行性不高.
文献[50]分析了求解线性规划问题的信息传播算法的收敛性,给出算法收敛到线性规划问题最优解的一个标准
框架.文献[51]分析了求解块内插问题(block interpolation problem)的信息传播算法的有效性,当因子图是一个
N×N 的网格图时,算法能够正确收敛.在附加噪音的高斯图模型网络线性系统中,利用 WLS(weighted least