基于警示传播与DPLL算法的启发式极性决策算法

Heuristic Polarity Decision Making Algorithm Based on Warning Propagation and DPLL Algorithm

警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RB实例集上的测试实验表明,该方法是有效的。

The warning propagation（WP） algorithm is an important foundation of message propagation algorithm,the essence of the WP algorithm is the iteration process of warning message on the factor gragh.When the algorithm is convergent,it can get a set of stable warning message and get some partial assignment of formula variables by local cavity domain.The analysis of basic principle of the WP algorithm was presented,and the improvement of the algorithm was given.The experiment on the RB sets shows that the improved algorithm has fewer iteration times,less execute time and faster convergence speed than the original WP algorithm.However,in the most of the RB sets,the WP algorithm is not convergent,and then it can not solve the formula effectively.The combination of the WP and DPLL algorithm can reduce the times of the backdating calculation,and then make up the shortage of the WP algorithm.The result of the experiment on the RB sets shows that the method is effective.