一种求解命题公式骨干集的警示传播算法

摘要：

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效.通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简.基于这样的特征修改WP算法的迭代方程和变元赋值条件,设计了一种求解命题公式骨干集的信息传播算法.当变元数目超过400时,与经典骨干集求解算法对比,效率提高了40％,与目前常用算法对比也有10％ 的提高.结果表明,所提算法求解命题公式骨干集时非常有效.

关键词：警示传播算法;SAT问题;因子图;骨干集

所属期刊栏目：43

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金;北方民族大学校级科研一般项目

在线出版日期：2021-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2056-2061