摘要
Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。
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.
作者
吴宇翔
王晓峰
丁红胜
于卓
Wu Yuxiang;Wang Xiaofeng;Ding Hongsheng;Yu Zhuo(School of Computer Science&Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Images&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)
出处
《计算机应用研究》
CSCD
北大核心
2022年第8期2290-2294,共5页
Application Research of Computers
基金
国家自然科学基金资助项目(62062001)
宁夏自然科学基金资助项目(2020AAC03214)
北方民族大学研究生创新项目(YCX21086)。
