Abstract: 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 backing calculation,and then up the shortage of the WP algorithm. The result of the experiment on the RB sets shows that the method is effective.

Key words: Message passing,Warning propagation(WP) algorithm,Convergence,DPLL algorithm