一种求解3-SAT问题的新方法

作者：贺毅朝; 王彦祺; 寇应展

来源：计算机工程与应用, 2006, (16): 70-72.

• 3-SAT问题
• 合取范式
• PSO算法
• 局部搜索 3-SAT Problem
• Conjunctive Normal Form
• PSO algorithm
• local search

可满足性问题(SatisfiabilityProblem,SAT)是计算科学的典型问题之一,目前有DP算法、SAT1.3算法和遗传算法等多种求解方法。文章根据Kennedy和Eberhart提出的二进制粒子群优化算法(BinaryParticleSwarmOptimizers),基于局部随机搜索策略,给出了一种求解3-SAT问题的新方法:基于局部随机搜索的改进二进制粒子群优化算法(ModifedBinaryParticleSwarmOptimizersBasedonlocalstochasticsearch,简称MBPSO)。数值实验表明,对于随机产生的3-SAT问题测试实例,该算法是一种高效...

• 单位
  中国人民解放军陆军工程大学; 河北地质大学