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

Effective conditions for warning propagation algorithm convergence on WP solvable formula

作　　者：崔立 王晓峰[1] 牛进 Cui Li;Wang Xiaofeng;Niu Jin(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021

出　　处：《计算机应用研究》2020年第5期1406-1410,共5页Application Research of Computers

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

摘　　要：通过对警示传播(warning propagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干集和后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n,3,m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。Through the analysis of the mathematical principle of WP algorithm,it could be found that the partial variables determined by high probability are closely related to the backbone set and backdoor set of the formula.For the study of the convergence of WP-solvable formula and WP algorithm,this paper defined WP-solvable formula based on backbone set and backdoor set,and proved the convergence of the WP algorithm by using the G(n,3,m)model and the planted distribution model,it gave the necessary and sufficient conditions for the convergence of the algorithm.Finally,it carried out the numerical experiments on the model of the planted distribution formula.The results show that if a satisfiability formula WP-solvable formula,if and only if the WP algorithm has a high probability of convergence.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]