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

• 作者: 李先贤 牛当当 王金艳 胡春
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: 扩展规则 自动推理 局部搜索 格局检测
• 年，卷（期）: 2020,（5）
• 所属期刊栏目: 学术论文
• 页码范围: 899-905
• 页数: 7页
• 分类号: TP181|TP301
• 字数: 6026字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2020.05.009

摘要

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 Reasoning)策略,并且给出变量的Subscore ER(Subscore for Extension Rule-Based Rea-soning),CScore_ER(Comprehensive Score for Extension Rule-Based Reasoning)和HScore_ER(Hybrid Score for Extension Rule-Based Reasoning)属性.在此基础上,提出了ERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER and Subscore_ER)和CERACC_IAPS(ERACC with IMOM,CCA_ER,PAWS_ER,CScore_ER and HScore_ER)算法.实验结果表明:ER-ACC_IAPS和CERACC_IAPS算法的效率明显优于ERACC算法,最高可将其求解效率提高1000多倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡春	广西师范大学计算机科学与信息工程学院	1	0	0.0	0.0