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

芦磊; 王晓峰; 牛鹏飞; 刘子琳

首页> 中文期刊> 《计算机应用研究》 >求解多文字可满足SAT问题的置信传播算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机应用研究》 |2021年第9期|2710-2715|共6页
作者
芦磊; 王晓峰; 牛鹏飞; 刘子琳;
展开▼
作者单位

北方民族大学计算机科学与工程学院银川750021;

北方民族大学计算机科学与工程学院银川750021;

北方民族大学图像图形智能处理国家民委重点实验室银川750021;

北方民族大学计算机科学与工程学院银川750021;

北方民族大学计算机科学与工程学院银川750021;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
多文字可满足; 置信传播算法; WalkSAT算法; 可满足问题;

相似文献

中文文献
外文文献
专利

1. 基于关键文字的求解SAT问题的启发式算法 [J] . 秦永彬 ,张秋菊 . 计算机与数字工程 . 2010,第010期
2. 基于寻找可满足2-SAT子问题的SAT算法 [J] . 傅阳春 ,周育人 . 计算机应用研究 . 2010,第002期
3. 基于子句的动态检查强制文字的SAT求解器 [J] . 常文静 ,徐扬 . 计算机工程与科学 . 2019,第002期
4. 一种求解0-1背包问题的置信传播算法 [J] . 张丹丹 ,王晓峰 ,冯琬晶 . 郑州大学学报（理学版） . 2021,第001期
5. 取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界 [J] . 王永平 ,许道云 . 软件学报 . 2021,第009期
6. PSA_SAT:求解SAT问题的退火算法并行研究 [C] . 王鹤 ,卢凯 . 2010年全国软件与应用学术会议(NASAC2010) . 2010
7. SAT问题的可满足性判定及其全解研究 [A] . 任小芹 . 2019

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

摘要

著录项

相似文献

相关主题

期刊订阅