计算机工程与科学

作者：王帅, 王晓峰, 梁田, 李志

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

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

基金：国家自然科学基金（62062001，61762019，61862051，61962002）；北方民族大学重大专项（ZDZX201901）；宁夏自然科学基金（2020AAC03214,NZ17111,2019AAC03120,2019AAC03119）；北方民族大学校级科研一般项目（2019XYZJK05）

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

来源：2021年第11期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2021年第11期