求解多文字可满足SAT问题的置信传播算法

来源：计算机应用研究杂志2021年第9期北京时间：

作者：芦磊,王晓峰,牛鹏飞,刘子琳,

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

摘要：可满足（SAT）问题是指：是否存在一组布尔变元赋值，使得合取范式公式中每个子句至少有一个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值，使得CNF公式中每个子句至少有两个文字为真。显然，此问题仍然是一个NP难问题。为了研究解决多文字可满足SAT问题的算法，引入随机实例产生模型，设计求解多文字可满足SAT问题的置信传播算法。最后，用实例模型产生了大量数据进行实验验证，结果表明：该算法求解多文字可满足SAT问题的性能优于其他启发式算法。

关键词：多文字可满足,置信传播算法,WalkSAT算法,可满足问题,

基金资助：国家自然科学基金资助项目(62062001,61762019,61862051,61962002)；北方民族大学重大专项(ZDZX201901)；宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)；；