基于IAPS的扩展规则局部搜索算法

发布时间：2021-01-18 20:14

　　ERACC （Extension Rule Based on Accurate Configuration Checking）算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT（Satisfiability）问题求解上的性能,本文在搜索由极大项组成的空间时,首先利用IMOM（Improved Maximum Occurrences on Clauses of Maximum Size）思想生成初始极大项,接着设计了适用于扩展规则推理的CCA_ER（Configuration Checking with Aspiration for Extension Rule-Based Reasoning）启发式策略,为极大项中格局信息未发生变化的变量对应文字提供一定的翻转机会.同时,为进一步提高扩展规则推理算法在k-SAT问题求解上的性能,设计了适用于扩展规则推理的PAWS_ER（Pure Additive Weighting Scheme for Extension Rule-Based Reasonin... 

【文章来源】：电子学报. 2020,48(05)北大核心

【文章页数】：7 页

【文章目录】：
1 引言
2 基础知识
    2.1 扩展规则
    2.2 ERACC算法
IAPS算法">3 ERACC_IAPS算法
    3.1 初始化极大项
ER启发式">    3.2 CCA_ER启发式
    3.3 子句权重更新策略
    3.4 子句的次贡献值
IAPS算法">4 CERACC_IAPS算法
5 实验结果与分析
IAPS算法的测试结果与分析">    5.1 ERACC_IAPS算法的测试结果与分析
IAPS算法的测试结果与分析">    5.2 CERACC_IAPS算法的测试结果与分析
    5.3 与其他局部搜索算法进行比较
6 结论与展望


【参考文献】：
期刊论文
[1]基于扩展规则的启发式#SAT求解算法[J]. 王强,刘磊,吕帅.  软件学报. 2018(11)
[2]一种新的基于局部搜索的扩展规则推理方法[J]. 杨洋,刘磊,李广力,张桐搏,吕帅.  计算机学报. 2018(04)
[3]基于MCN和MO启发式策略的扩展规则知识编译方法[J]. 谷文祥,王金艳,殷明浩.  计算机研究与发展. 2011(11)
[4]基于半扩展规则的定理证明方法[J]. 张立明,欧阳丹彤,白洪涛.  计算机研究与发展. 2010(09)
[5]基于IMOM和IBOHM启发式策略的扩展规则算法[J]. 李莹,孙吉贵,吴瑕,朱兴军.  软件学报. 2009(06)
[6]一种新的基于扩展规则的定理证明算法[J]. 孙吉贵,李莹,朱兴军,吕帅.  计算机研究与发展. 2009(01)



本文编号：2985593