基于加强概率控制策略的SAT局部搜索算法

• 作者: 张峥华 洪剑珂 许贵平
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: SAT问题 局部搜索 概率控制 子句 布尔变元
• 年，卷（期）: 2017,（14）
• 所属期刊栏目: 理论与研发
• 页码范围: 56-60,110
• 页数: 6页
• 分类号: TP301.6
• 字数: 4439字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1603-0151

摘要

局部搜索算法是目前求解SAT问题比较有效的方法,而Sattime算法是在SAT国际大赛中获得大奖的一种典型局部搜索算法.在Sattime算法的求解过程中,记录变元翻转事件流数据库,通过数据分析与模式挖掘,发现Sattime算法的局部搜索行为中会出现相邻搜索步选择同一个变元的现象,即所谓的回环现象,从而降低了求解效率.为解决此问题,提出两种概率控制策略:加强子句选择策略和加强变元选择策略,并将这两种策略应用到Sattime算法中,形成新的局部搜索算法Sattime-P.实验结果表明,与Sattime算法相比,改进后的Sattime-P算法求解效率有显著的提升.该方法也对其他局部搜索算法的改进具有参考价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许贵平	华中科技大学计算机学院	11	90	5.0	9.0
2	洪剑珂	北京林业大学信息学院	2	8	2.0	2.0
3	张峥华	华中科技大学计算机学院	1	3	1.0	1.0