The Application Of Improved Belief Propagation Algorithm Insolving The Maximum Constraint Satisfaction Problems

The maximum constraint satisfaction problem is to find a solution which makes the maximum constraint to be satisfied. As one of the most important fundamental problems of artificial intelligence, the maximum constraint satisfaction problem has important research value and status in the field of artificial intelligence research. In the previous work, the domestic and foreign scholars mainly use the complete algorithms and incomplete algorithm to solve the maximum constraint satisfaction problem. In different application areas, they have made many good solutions. The belief propagation algorithm is a classical message propagation algorithm and has an important position in the artificial neural network. It is an incomplete algorithm to obtain an incomplete solution in the factor graph and has solved many NPC problems perfectly.Based on the in-depth study of belief message propagation algorithm and the stylistic features of the maximum constraint satisfaction problem, we establish the factor graph. Then we apply the minimum entropy in belief propagation algorithm for the maximum constraint satisfaction problem of RB model. In order to improve the effect the algorithm, add a penalty value in the belief propagation equation. Last we use the belief propagation algorithm to solve the maximum constraint satisfaction problem. This paper also analyzes the phase transition of RB model in the maximum constraint satisfaction problem.Applying the improved belief propagation algorithm to the maximum constraint satisfaction problem make the solution better and using the method of experimental analysis proved that the improved solution is effect. Using the excellent effect for RB model by the belief propagation algorithm, this paper also analyzes the phase transition of RB model in the maximum constraint satisfaction problem. Using the method of experimental analysis proved the existence of the phase transition point before the use of theoretical research in the maximum constraint satisfaction problem. It makes many contributions to the further research of the RB model in maximum constraint satisfaction problem.