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

摘要

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