可满足性问题中信念传播算法的收敛性分析

信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范围为(0,1),将该取值范围扩展到整个实数空间,即(−∞,+∞).利用压缩函数的数学原理,得到了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟,验证了结论的正确性.

警示传播算法收敛的充分条件

信息传播算法求解可满足问题时有惊人的效果,难解区域变窄.然而,因子图带有环的实例,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,对WP算法的收敛性研究是其他信息传播算法收敛性研究的重要基础.在WP算法中,将警示信息的取值从{0,1}松弛为[0,1],利用压缩函数的性质,给出了WP算法收敛的一个充分条件.选取了两组不同规模的随机3-SAT实例进行实验模拟,结果表明:当子句与变元的比值?<1.8时,该判定条件有效.

一种基于图匹配的求解可满足性问题的算法

信息传播算法求解可满足性问题时具有良好的有效性,能使难解区域变窄。在信息传播算法的设计中,是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor),每一个因子依赖于一个变量子集,将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息,这种消息传递有两种方式:变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定,通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时,利用某种规则(如,最小熵、最大积、最大匹配)对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法,根据对算法的收敛性分析,在对问题解的精确性影响不大的前提下,仅需要给出算法合理的迭代步数或者强迫算法终止,使得算法提前结束,有助于求解可满足性问题算法性能的更进一步优化。

调查传播算法收敛的一个充分条件

信息传播算法求解可满足问题时有良好的有效性,使得难解区域变窄.然而,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.调查传播(survey propagation,SP)算法是最为有效的信息传播算法,对SP算法的收敛性研究是设计其他信息传播算法的重要基础,并为信息传播算法的广泛应用提供理论依据.为了分析SP算法的收敛性,通过对消息更新方程取双曲正切,将消息取值从[0,1]扩展为(-∞,∞),利用压缩映射原理给出了SP算法收敛的一个充分条件.基于随机3-SAT实例,给出了SP算法收敛的一个概率条件.最后,选取了随机3-SAT实例进行数值实验模拟,验证了该条件的有效性.