可满足性问题全部解的求解算法

doi:10.3778/j.issn.1002-8331.2009.03.009

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (3): 35-37.DOI: 10.3778/j.issn.1002-8331.2009.03.009

可满足性问题全部解的求解算法

毕忠勤¹,陈光喜²,单美静¹

1.华东师范大学上海市高可信计算重点实验室，上海 200062
2.桂林电子科技大学数学与计算科学学院，广西桂林 541004

收稿日期:2008-09-10 修回日期:2008-10-16 出版日期:2009-01-21 发布日期:2009-01-21
通讯作者: 毕忠勤

Algorithm for finding all-solutions of satisfiablity problem

BI Zhong-qin¹,CHEN Guang-xi²,SHAN Mei-jing¹

1.Shanghai Key Laboratory of Trustworthy Computing，East China Normal University，Shanghai 200062，China
2.School of Mathematics & Computational Science，Guilin University of Electronic Technology，Guilin，Guangxi 541004，China

Received:2008-09-10 Revised:2008-10-16 Online:2009-01-21 Published:2009-01-21
Contact: BI Zhong-qin

摘要/Abstract

摘要： SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用，近年来，证明该问题的可满足性取得了巨大的成功，但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换，将可满足性（SAT）问题转化为多项式形式，然后根据命题逻辑的性质以及多项式的性质，得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的。

关键词: 可满足性问题, 局部搜索, 多项式扩展, 自动求解

Abstract: Satisfiability problem has been widely used in many fields such as artificial intelligence，computer theory research and computation theory.Many algorithms about this NP-hard problem have been built，but how to get all of the truth assignments is still difficult.By establishing the correspondence between the primitive operation in polynomial and clause solution in SAT，an efficient algorithm has been built to obtain all solutions which satisfied the problem.Experiment shows that the new algorithm is feasible.

Key words: Sattifiability（SAT） problem, local search, polynomial expanding, automatic solve

毕忠勤¹,陈光喜²,单美静¹. 可满足性问题全部解的求解算法[J]. 计算机工程与应用, 2009, 45(3): 35-37.

BI Zhong-qin¹,CHEN Guang-xi²,SHAN Mei-jing¹. Algorithm for finding all-solutions of satisfiablity problem[J]. Computer Engineering and Applications, 2009, 45(3): 35-37.

[1]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[2]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[3]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[4]	刘春苗，张惠珍. 求解无容量设施选址问题的混合蝙蝠算法[J]. 计算机工程与应用, 2018, 54(22): 28-34.
[5]	董小帅1，2，3，毛政元1，2，3. 基于改进遗传算法的动态路径规划研究[J]. 计算机工程与应用, 2018, 54(19): 49-55.
[6]	常文静1，3，徐扬2，3，吴贯锋1，3. 基于演绎长度的学习子句删除策略[J]. 计算机工程与应用, 2018, 54(16): 30-36.
[7]	吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.
[8]	胡炜1，2，曾斌1，姚路1. 事件驱动下的重点海域监测站部署算法研究[J]. 计算机工程与应用, 2017, 53(7): 136-140.
[9]	宋强. 改进迭代局部搜索算法在MMTVRP中的应用[J]. 计算机工程与应用, 2017, 53(7): 248-255.
[10]	洪剑珂1，张峥华2，许贵平2. 基于加强概率控制策略的SAT局部搜索算法[J]. 计算机工程与应用, 2017, 53(14): 56-60.
[11]	王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.
[12]	伍艳莲1，2，姜海燕1，2，庄嘉祥1，郭小清1，许一骅1. 精英策略个体优势遗传算法研究[J]. 计算机工程与应用, 2016, 52(7): 143-149.
[13]	林耿1，徐梅琴2. 图的最大二等分问题的一种离散填充函数算法[J]. 计算机工程与应用, 2016, 52(5): 27-32.
[14]	鲁宇明1，4，王彦超2，刘嘉瑞3，Wu Liu4. 一种改进的生物地理学优化算法[J]. 计算机工程与应用, 2016, 52(17): 146-151.
[15]	胡博. 基于均匀设计的免疫克隆多峰函数优化[J]. 计算机工程与应用, 2015, 51(2): 57-59.

可满足性问题全部解的求解算法

Algorithm for finding all-solutions of satisfiablity problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics