WP可解公式上警示传播算法收敛的有效条件

来源：计算机应用研究杂志2020年第5期北京时间：

作者：崔立,王晓峰,牛进,

单位：北方民族大学计算机科学与工程学院,银川750021；

摘要：通过对警示传播（warning propagation，WP）算法的数学原理分析，高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究，基于骨干集和后门集定义WP-可解公式，利用在G（n，3，m）模型和植入指派模型下证明WP算法的收敛性，给出算法收敛的充要条件。最后，通过在植入指派的公式产生模型上进行数值实验验证，结果表明：如果一个可满足性公式WP-可解公式，当且仅当WP算法高概率收敛。

关键词：警示传播算法,骨干集,后门集,WP-可解公式,实例产生模型,

基金资助：国家自然科学基金资助项目(61462001,61762019,61762002,11761002,61561002)；北方民族大学重点科研项目(2017KJ24,2017KJ25)；2018宁夏回族自治区重点研发计划项目(2018BEE03019)；宁夏高等学校一流学科建设(电子科学与技术学科)资助项目(NXYLXK2017A07)；北方民族大学创新项目(YCX19060)；北方民族大学校级科研一般项目(2019XYZJK05)；宁夏自然科学基金资助项目(NZ17111,2019AAC03120