摘要: 信息传播算法求解可满足性问题时非常有效,警示传播(warning propagation,WP)算法是最为基础的信息传播算法。通过对WP算法的数学原理分析,高概率确定的部分变元与公式的骨干集合后门集有密切关系。针对WP算法收敛性的研究,基于骨干集和后门集定义WP-可解公式,利用在G(n, 3, m)模型和植入指派模型下证明WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产生模型上进行数值实验验证,结果表明:如果一个可满足性公式WP-可解公式,当且仅当WP算法高概率收敛。