基于趋势强度的SAT问题学习子句评估算法

摘要：

针对命题逻辑公式求解过程中难以有效评估学习子句是否有利于后续搜索的问题,提出了一种基于学习子句趋势强度的评估算法.该算法首先通过分析学习子句在生存期内参与冲突分析的时间分布特征,将随机、离散的时间分布转换为连续的累积趋势强度;然后在删除周期达到时,通过设定趋势强度阈值删除在后续搜索过程中"不大可能"被使用的子句,保留"可能"被使用的子句;最后采用2015年、2016年SA T问题国际竞赛实例,将该算法与经典的活跃度评估算法和文字块距离(LBD)评估算法进行对比.实验结果表明,趋势强度评估算法在效率上明显优于活跃度评估算法,且求解的实例更多,同时与LBD算法基本持平.

关键词：命题逻辑、趋势强度、学习子句、子句评估、周期性删除

所属期刊栏目：45

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目61673320,11526171,61305074;中央高校基本科研业务费项目2682017ZT12

在线出版日期：2019-01-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：137-141