软件学报

作者：王晓峰，许道云，杨德仁，姜久雷，李强，刘欣欣

单位：王晓峰，北方民族大学 计算机科学与工程学院, 宁夏 银川 750021;贵州大学计算机科学与技术学院, 贵州 贵阳 55002511,许道云，贵州大学计算机科学与技术学院, 贵州 贵阳 55002502,杨德仁，宁夏医科大学 理学院, 宁夏 银川 75000403,姜久雷，北方民族大学 计算机科学与工程学院, 宁夏 银川 75002104,李强，北方民族大学 计算机科学与工程学院, 宁夏 银川 75002105,刘欣欣，北方民族大学 计算机科学与工程学院, 宁夏 银川 75002106

关键词：信念传播算法;收敛性;可满足性问题;因子图

基金：国家自然科学基金（62062001，61762019，61762002，61862051，61962002）；宁夏自然科学基金（2020AAC03214，NZ17111，2019AAC03120，2019AAC03119，2020AAC03219）；北方民族大学重大专项基金（ZDZX201901）；北方民族大学校级一般科学基金（2019XYZJK05）

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

来源：2021年第5期

《软件学报》期刊编辑部

查看软件学报杂志2021年第5期