求解SAT问题的拟人退火算法

• 作者: 张德富 汪厚祥 黄文奇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: SAT问题 模拟退火算法 拟人
• 年，卷（期）: 2002,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 148-152
• 页数: 5页
• 分类号: TP18
• 字数: 3951字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.02.005

摘要

该文利用一个简单的变换,将可满足性(SAT)问题转换为一个求相应目标函数最小值的优化问题,提出了一种用于跳出局部陷阱的拟人策略.基于模拟退火算法和拟人策略,为SAT问题的高效近似求解得出了拟人退火算法(PA),该方法不仅具有模拟退火算法的全局收敛性质,而且具有一定的并行性、继承性.数值实验表明,对于本文随机产生的测试问题例,采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的WALKSAT算法,因此拟人退火算法是可行的和有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机学院	88	1090	21.0	27.0
2	汪厚祥	华中科技大学计算机学院	3	84	3.0	3.0
3	张德富	华中科技大学计算机学院	2	56	1.0	2.0