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

来源：软件学报杂志2016年第12期北京时间：

作者：王晓峰,许道云

单位：王晓峰，北方民族大学 计算机科学系, 宁夏 银川 750021;贵州大学 计算机科学系, 贵州 贵阳 55002511,许道云，贵州大学 计算机科学系, 贵州 贵阳 55002502

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

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

基金资助：国家自然科学基金（61462001，61262006，61402017）；宁夏自然科学基金（NZ14108）；北方民族大学基金（2014XYZ03，2014XBZ04）；“计算机应用技术”自治区重点学科项目