《计算机应用研究》|Application Research of Computers

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

Effective conditions for warning propagation algorithm convergence on WP solvable formula

免费全文下载 (已被下载 次)  
获取PDF全文
作者 崔立,王晓峰,牛进
机构 北方民族大学 计算机科学与工程学院
统计 摘要被查看 次,已被下载
摘要 信息传播算法求解可满足性问题时非常有效,警示传播(warning propagation,WP)算法是最为基础的信息传播算法。通过对WP算法的数学原理分析,高概率确定的部分变元与公式的骨干集合后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n, 3, m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。
关键词 警示传播算法;骨干集;后门集;WP-可解公式;实例产生模型
基金项目 国家自然科学基金资助项目(61462001,61762019,61762002,11761002,61561002)
北方民族大学重点科研项目(2017KJ24,2017KJ25)
2018宁夏回族自治区重点研发计划项目(2018BEE03019)
宁夏高等学校一流学科建设(电子科学与技术学科)资助项目(NXYLXK2017A07)
本文URL http://www.arocmag.com/article/02-2020-05-003.html
收稿日期
修回日期
页码 -
中图分类号 TP
文献标志码