The Max-SAT problem is an optimized version of the SAT problem. The goal is to find a set of variable assignments in a given set of clauses so that the maximum number of clauses is satisfied. This problem is a typical NP-hard problem. With the in-depth development of big data and artificial intelligence, the original algorithms in the past are no longer applicable. Designing a new solution algorithm or optimizing the existing solution algorithm is the current research hotspot. Aiming at the limitations of the information dissemination algorithm for solving the random Max-3-SAT problem, this paper proposed a warning dissemination algorithm based on the calculation of variable weights. Combined with the random walk algorithm, it formed a new algorithm WWP+WalkSAT, which was solved by improvement of the limitation, it was better to get a set of effective initial solutions, thereby improving the local search ability of the algorithm. Using some benchmark examples of the Max-SAT international competition in 2016, it used the WWP+WalkSAT algorithm and 8 local search algorithms for accuracy comparison experiments. The experimental results show that the WWP+WalkSAT algorithm has good performance.

[2022-03-25] Accepted Paper /doc/2022.01.0023/v1

[2022-08-05] Printed Article /doc/2022.01.0023/v2