计算机应用研究2021，Vol.38Issue(9) ：2710-2715.DOI:10.19734/j.issn.1001-3695.2021.01.0012

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

Belief propagation algorithm for solving multi literal satisfiability problem

芦磊 王晓峰 牛鹏飞 刘子琳
计算机应用研究2021，Vol.38Issue(9) ：2710-2715.DOI:10.19734/j.issn.1001-3695.2021.01.0012
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

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

Belief propagation algorithm for solving multi literal satisfiability problem

芦磊 1王晓峰 2牛鹏飞 1刘子琳1
扫码查看

作者信息

  • 1. 北方民族大学 计算机科学与工程学院,银川750021
  • 2. 北方民族大学 计算机科学与工程学院,银川750021;北方民族大学 图像图形智能处理国家民委重点实验室,银川750021
  • 折叠

摘要

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

关键词

多文字可满足/置信传播算法/WalkSAT算法/可满足问题

引用本文复制引用

基金项目

出版年

2021
计算机应用研究
四川省电子计算机应用研究中心

计算机应用研究

CSTPCDCSCD北大核心
影响因子：0.93
ISSN：1001-3695
被引量1
参考文献量2
段落导航相关论文