一种改进的警示传播算法求解Max-SAT问题

打开文本图片集

摘要：Max-SAT问题是SAT问题的优化版本，目标是在给定的子句集中找到一组变元赋值，使得满足子句数最多，该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展，过去原有的算法已不再适用，设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性，提出了一种基于变元权值计算的警示传播算法，结合随机游走算法，给出一种新型算法WWP+WalkSAT，通过改进求解的局限性，更好地得到一组有效的初始解，从而提高算法的局部搜索能力。（剩余14576字）