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

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