检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

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

电子学报 2020年第5期48卷 899-905页

作者：王金艳胡春牛当当李先贤广西多源信息挖掘与安全重点实验室(广西师范大学) 广西桂林541004 广西师范大学计算机科学与信息工程学院广西桂林541004 西北农林科技大学信息工程学院陕西杨凌712100

ERACC(Extension Rule Based on Accurate Configuration Checking)算法由杨洋等人基于扩展规则和格局检测提出,具有较高的推理效率.为进一步提高ERACC算法在大规模SAT(Satisfiability)问题求解上的性能,本文在搜索由极大项组成的空间时... 详细信息

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 Reasoning),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)算法.实验结果表明:ERACC_IAPS和CERACC_IAPS算法的效率明显优于ERACC算法,最高可将其求解效率提高1000多倍.

关键词：扩展规则自动推理局部搜索格局检测

在线全文

学校读者我要写书评

暂无评论

一种新的基于局部搜索的扩展规则推理方法

计算机学报 2018年第4期41卷 825-839页

作者：杨洋刘磊李广力张桐搏吕帅吉林大学计算机科学与技术学院长春130012 吉林大学数学学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

作为与归结推理方法互补的推理方法,扩展规则推理方法得到了国内外广泛认可.目前扩展规则推理方法的研究主要集中于完备推理方法,由于极大项变换方式过于机械,导致该方法处理公式的规模比较局限.该文在深入分析扩展规则推理和局部搜索... 详细信息

作为与归结推理方法互补的推理方法,扩展规则推理方法得到了国内外广泛认可.目前扩展规则推理方法的研究主要集中于完备推理方法,由于极大项变换方式过于机械,导致该方法处理公式的规模比较局限.该文在深入分析扩展规则推理和局部搜索关联性的基础上,利用子句集中的"极大项"概念设计了一种反向求解策略,进而设计并实现一种新的基于局部搜索的扩展规则推理框架.在此基础上,为了使得极大项搜索过程更加适配该框架,提出了一种基于精确格局检测实现和双向半扩展规则策略的两阶段局部搜索算法.实验结果表明,该文提出的基于精确格局检测的新型扩展规则推理算法ERACC突破了传统扩展规则推理对公式规模的局限,求解效率有了极大提高,使得扩展规则推理方法不再受公式规模制约,可以用于知识编译和可能性推理等多方面的应用.

关键词：自动推理扩展规则局部搜索精确格局检测双向半扩展规则反向求解

在线全文

学校读者我要写书评

暂无评论

两种新的基于扩展规则#SAT问题求解算法

东北大学学报（自然科学版） 2019年第5期40卷 630-634,646页

作者：吕帅张桐搏王强刘磊吉林大学计算机科学与技术学院吉林长春130012

提出一种新的基于扩展规则的#SAT求解算法NCER,该算法在#ER的基础上加入启发式策略.该策略每次选择当前子句集的最长子句来减小极大项空间,使得递归调用的次数减少,从而加快求解效率.为解决基于扩展规则的#SAT求解器在互补因子较小的样... 详细信息

提出一种新的基于扩展规则的#SAT求解算法NCER,该算法在#ER的基础上加入启发式策略.该策略每次选择当前子句集的最长子句来减小极大项空间,使得递归调用的次数减少,从而加快求解效率.为解决基于扩展规则的#SAT求解器在互补因子较小的样例上的不良表现,结合NCER和CDP的优点提出混合#SAT求解算法NCDPER.实验结果表明:NCER较先前的#ER在所有85个随机SAT测试用例上有了显著的提高.通过与目前最好的基于扩展规则的#SAT求解器的比较,该求解器具有更好的性能.

关键词：自动推理扩展规则模型计数极大项空间启发式策略

在线全文

学校读者我要写书评

暂无评论

扩展规则方法研究综述

智能系统学报 2014年第1期9卷 1-11页

作者：王金艳谷文祥覃少华殷明浩广西师范大学计算机科学与信息工程学院广西桂林541004 长春建筑学院基础教学部吉林长春130607 东北师范大学计算机科学与信息技术学院吉林长春130117

归结方法是自动推理的重要方法之一,而扩展规则是与归结对称的方法,近年来引起了研究者的广泛关注。从扩展规则的相关概念、在命题逻辑中的发展以及在一阶逻辑、描述逻辑、模态逻辑、可能性逻辑和多值逻辑中的应用3个方面论述分析了扩... 详细信息

归结方法是自动推理的重要方法之一,而扩展规则是与归结对称的方法,近年来引起了研究者的广泛关注。从扩展规则的相关概念、在命题逻辑中的发展以及在一阶逻辑、描述逻辑、模态逻辑、可能性逻辑和多值逻辑中的应用3个方面论述分析了扩展规则10年来的研究现状,重点阐述扩展规则用于求解SAT、相近SAT和#SAT问题各种算法的优缺点,最后指出相关的研究热点与发展趋势。

关键词：自动推理归结方法扩展规则 SAT #SAT

在线全文

学校读者我要写书评

暂无评论

基于扩展规则的启发式#SAT求解算法

软件学报 2018年第11期29卷 3517-3527页

作者：王强刘磊吕帅吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

#SAT在人工智能领域取得了广泛应用,很多现实问题可以规约成#SAT进行求解,得到命题理论的模型个数.通过对基于扩展规则的#SAT求解器的深入研究,发现选择规约子句的顺序对极大项空间的大小有着较大的影响,因此提出两种加速#SAT求解的启... 详细信息

#SAT在人工智能领域取得了广泛应用,很多现实问题可以规约成#SAT进行求解,得到命题理论的模型个数.通过对基于扩展规则的#SAT求解器的深入研究,发现选择规约子句的顺序对极大项空间的大小有着较大的影响,因此提出两种加速#SAT求解的启发式策略:MW和LC&MW.MW每次选择具有最大权值的子句作为规约子句;LC&MW每次选择最长子句作为规约子句,若最长子句存在多个,则在多个最长子句中选择具有最大权值的子句作为规约子句.利用MW策略设计了算法CER_MW,利用LC&MW策略设计了算法CER_LC&MW.实验结果表明,CER_MW和CER_LC&MW相对于先前的#SAT求解算法在求解效率和求解能力上都有显著的提高.在求解效率方面,CER_MW和CER_LC&MW的求解速度是其他算法的1.4倍~100倍.在求解能力方面,CER_MW和CER_LC&MW在限定时间内可解的测试用例更多.

关键词：扩展规则模型计数启发式算法极大项空间规约子句

在线全文

学校读者我要写书评

暂无评论

基于超扩展规则的知识编译方法

计算机学报 2016年第8期39卷 1681-1696页

作者：刘磊牛当当吕帅吉林大学计算机科学与技术学院长春130012 吉林大学数学学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集,并将所得结果以EPCCL理论的形式保存.该文首次提出了扩展反驳方法,是一种新型推理方法,并在该推理方法与知识编... 详细信息

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集,并将所得结果以EPCCL理论的形式保存.该文首次提出了扩展反驳方法,是一种新型推理方法,并在该推理方法与知识编译之间建立了联系.基于超扩展规则的性质,该文还提出了两种知识编译算法:求并知识编译算法UKCHER和求差知识编译算法DKCHER,是两种新的知识编译算法.算法UKCHER是目前为止唯一一个可并行的EPCCL理论编译算法,算法DKCHER对于相变点附近的难解问题具有较高的编译效率和编译质量.实验结果表明:UKCHER算法的编译效率和编译质量均优于Lin等人提出的KCER算法;当子句数和变量数的比值较大时,DKCHER算法的编译效率和编译质量是最优的,相比于现有EPCCL理论编译算法,该算法具有较强的竞争力.

关键词：知识编译扩展规则超扩展规则 EPCCL理论扩展反驳

结合互补度的基于扩展规则#SAT问题求解方法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2016年第7期53卷 1596-1604页

作者：欧阳丹彤贾凤雨刘思光张立明吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

#SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一,在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法 CER(counting models using extension rules)深入研究的基础上,提出一种结合互补度的#SAT问题... 详细信息

#SAT问题又称模型计数(model counting)问题是人工智能领域的研究热点之一,在人工智能领域被广泛应用.在对基于扩展规则的#SAT问题求解方法 CER(counting models using extension rules)深入研究的基础上,提出一种结合互补度的#SAT问题求解方法.在计算给定子句集的模型个数时,利用SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成需要计算的子句集合,并在SE-Tree中添加终止结点,避免大部分含互补文字子句集合的生成,且不会因剪枝而导致求解不完备.提出互补度的概念,在扩展SE-Tree结点时按照互补度由大到小的顺序扩展,较早地生成含互补文字且长度较小的子句集合,有效减少枚举树生成的结点个数,进而减少对子句集合判断是否含互补文字的计算次数.实验结果表明:与CER方法相比该方法效率较好,且进一步改进了CER方法在互补因子较低时求解效率低下的不足.

关键词：扩展规则模型计数 CER方法互补度集合枚举树

在线全文

学校读者我要写书评

暂无评论

基于超扩展规则的动态在线推理算法

哈尔滨工程大学学报 2015年第12期36卷 1614-1619页

作者：刘磊牛当当李壮吕帅吉林大学计算机科学与技术学院吉林长春130012

为了提高扩展规则的扩展性能,提出了超扩展规则,并证明了其与扩展负超归结之间的关联关系。KCER算法中使用扩展规则扩展子句,利用超扩展规则替换扩展规则能够更清晰地展示扩展过程,因此提出了基于超扩展规则的动态在线推理算法IKCCER。I... 详细信息

为了提高扩展规则的扩展性能,提出了超扩展规则,并证明了其与扩展负超归结之间的关联关系。KCER算法中使用扩展规则扩展子句,利用超扩展规则替换扩展规则能够更清晰地展示扩展过程,因此提出了基于超扩展规则的动态在线推理算法IKCCER。IKCCER采用离线编译和在线推理过程交互执行的方式,在保持推理效率不变的同时,其空间复杂性为KCCER算法空间复杂性的2/(n+1),其中n为输入子句集的子句数。

关键词：自动推理知识编译扩展规则超扩展规则动态在线推理

在线全文

学校读者我要写书评

暂无评论

半扩展规则下分解的定理证明方法

软件学报 2015年第9期26卷 2250-2261页

作者：张立明欧阳丹彤赵毅吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 吉林大学电子科学与工程学院吉林长春130012

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需... 详细信息

基于扩展规则的定理证明方法在一定意义上是与归结原理对偶的方法,通过子句集能否推导出所有极大项来判定可满足性.IER(improved extension rule)算法是不完备的算法,在判定子句集子空间不可满足时,并不能判定子句集的满足性,算法还需重新调用ER(extension rule)算法,降低了算法的求解效率.通过对子句集的极大项空间的研究,给出了子句集的极大项空间分解后子空间的求解方法.通过对扩展规则的研究,给出了极大项部分空间可满足性判定方法 PSER(partial semi-extension rule).在IER算法判定子空间不可满足时,可以调用PSER算法判定子空间对应的补空间的可满足性,从而得到子句集的可满足性,避免了不能判定极大项子空间可满足性时需重新调用ER算法的缺点,使得IER算法更完备.在此基础上,还提出DPSER(degree partial semi-extension rule)定理证明方法.实验结果表明:所提出的DPSER和IPSER的执行效率较基于归结的有向归结算法DR、IER及NER算法有明显的提高.

关键词：定理证明命题逻辑扩展规则可满足性问题