典型文献
一种改进的警示传播算法求解Max-SAT问题
文献摘要：
Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题.随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点.针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+Walk-SAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力.利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验.实验结果表明,WWP+WalkSAT算法有较好的性能.
文献关键词：
可满足性问题;最大可满足性问题;警示传播算法;局部搜索算法
中图分类号：
作者姓名：
吴宇翔;王晓峰;丁红胜;于卓
作者机构：
北方民族大学计算机科学与工程学院,银川750021;北方民族大学图像图形智能处理国家民委重点实验室,银川750021
文献出处：
引用格式：
[1]吴宇翔;王晓峰;丁红胜;于卓-.一种改进的警示传播算法求解Max-SAT问题)[J].计算机应用研究,2022(08):2290-2294
A类：
警示传播,警示传播算法,WWP+Walk,WWP+WalkSAT,最大可满足性问题
B类：
Max,子句,赋值,句数,数最多,NP,hard,深度发展,求解算法,权值,随机游走算法,初始解,搜索能力,国际竞赛,竞赛部,八种,局部搜索算法
AB值：
0.222525
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
