计算机应用研究

作者：吴宇翔,王晓峰,丁红胜,于卓,

单位：北方民族大学a.计算机科学与工程学院;b.图像图形智能处理国家民委重点实验室,银川750021；

关键词：可满足性问题,最大可满足性问题,警示传播算法,局部搜索算法,

基金：国家自然科学基金资助项目(62062001)；宁夏自然科学基金资助项目(2020AAC03214)；北方民族大学研究生创新项目(YCX21086)；；

Max-SAT问题是SAT问题的优化版本，目标是在给定的子句集中找到一组变元赋值，使得满足子句数最多，该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展，过去原有的算法已不再适用，设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性，提出了一种基于变元权值计算的警示传播算法，结合随机游走算法，给出一种新型算法WWP+WalkSAT，通过改进求解的局限性，更好地得到一组有效的初始解，从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例，将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明，WWP+WalkSAT算法有较好的性能。

来源：2022年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2022年第8期