检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

EPCCL理论的求交知识编译算法

软件学报 2017年第8期28卷 2096-2112页

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

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集、差集和并集,并将所得结果以EPCCL(each pair of clauses contains complementary literals)理论的形式保存.基于超扩... 详细信息

超扩展规则是对扩展规则的扩充,基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集、差集和并集,并将所得结果以EPCCL(each pair of clauses contains complementary literals)理论的形式保存.基于超扩展规则的性质,提出一种EPCCL理论编译算法:求交知识编译算法IKCHER(intersection approach to knowledge compilation based on hyper extension rule).该算法适合难解类SAT问题的知识编译,也是一种可并行的知识编译算法.研究了如何实现多个EPCCL理论的求交操作,证明了EPCCL理论的求交过程是可并行执行的,并设计了相应的并行求交算法PIAE(parellel intersection of any number of EPCCL).通过对输入EPCCL理论对应普通子句集的利用,设计了一种高效的并行求交算法imp-PIAE(improvement of PIAE).基于上述算法,还设计了两种并行知识编译算法P-IKCHER(IKCHER with PIAE)和imp P-IKCHER(IKCHER with imp-PIAE),分别采用PIAE并行合并算法和imp-PUAE并行合并算法.最后,通过实验验证了,大部分情况下,IKCHER算法的编译质量是目前为止所有EPCCL理论编译器中最优的,P-IKCHER算法所使用的合并策略并没有起到加速的效果,反而使得编译效率和编译质量有所下降;imp P-IKCHER算法提高了IKCHER算法的编译效率,CPU四核环境下最高可提高2倍.

关键词：知识编译扩展规则超扩展规则 EPCCL(each pair of clauses contains complementary literals)理论并行知识编译

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

基于相邻子句规约的求差知识编译算法

哈尔滨工程大学学报 2019年第12期40卷 2044-2049页

作者：牛当当吕帅王金艳西北农林科技大学信息工程学院陕西杨凌712100 西北农林科技大学陕西省农业信息感知与智能服务重点实验室陕西杨陵712100 吉林大学计算机科学与技术学院吉林长春130012 吉林大学符号计算与知识工程教育部重点实验室吉林长春130012 广西师范大学计算机科学与信息工程学院广西桂林541004

利用规约规则可以约简EPCCL理论的规模,从而提高扩展规则知识编译算法的编译质量。为此,设计了约简EPCCL理论相邻子句的算法(reducing adjacent clauses in EPCCL,RACE),用于约简EPCCL理论中满足规约规则的相邻子句,进而降低了基于超扩... 详细信息

利用规约规则可以约简EPCCL理论的规模,从而提高扩展规则知识编译算法的编译质量。为此,设计了约简EPCCL理论相邻子句的算法(reducing adjacent clauses in EPCCL,RACE),用于约简EPCCL理论中满足规约规则的相邻子句,进而降低了基于超扩展规则的求差知识编译算法(computing the difference set for knowledge compilation based on hyper extension rule,DKCHER)的中间结果EPCCL理论和最终结果EPCCL理论的规模。结合RACE算法和DKCHER算法,设计并实现了改进的DKCHER算法(improved DKCHER,imp-DKCHER)。实验结果表明:imp-DKCHER算法能够显著提高DKCHER算法的编译质量,平均可提高17.3%,并在大部分实例上能够提高DKCHER算法的编译效率。

关键词：自动推理知识编译扩展规则超扩展规则子句集 EPCCCL理论规约规则相邻子句规约

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

基于MOVR启发式的求差知识编译算法

电子学报 2019年第11期47卷 2299-2303页

作者：牛当当吕帅王金艳西北农林科技大学信息工程学院陕西杨凌712100 吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 广西师范大学计算机科学与信息工程学院广西桂林541004

DKCHER算法是基于超扩展规则的求差知识编译算法,也是目前为止表现最好的EPCCL理论编译算法.本文通过研究DKCHER算法的执行流程,设计了一种新的启发式策略MOVR(maximum occurrence number of variables in middle result),用于动态地从... 详细信息

DKCHER算法是基于超扩展规则的求差知识编译算法,也是目前为止表现最好的EPCCL理论编译算法.本文通过研究DKCHER算法的执行流程,设计了一种新的启发式策略MOVR(maximum occurrence number of variables in middle result),用于动态地从输入子句集中选择所包含变量在中间结果中出现次数最多的子句.将MOVR启发式策略与DKCHER算法相结合,设计了MOVR_DKCHER算法.实验结果表明,MOVR启发式策略能够显著提高DKCHER算法的编译效率和编译质量,编译效率平均可提升70倍左右,最高可以提高237倍.

关键词：知识编译扩展规则超扩展规则 EPCCL理论启发式策略

在线全文

学校读者我要写书评

暂无评论

基于超扩展规则的高效知识编译方法研究

基于超扩展规则的高效知识编译方法研究

作者：牛当当吉林大学

学位级别：硕士

扩展规则推理方法是2003年提出的一种新型推理方法，得到了国内外学者的认可。基于扩展规则能够实现命题逻辑中的推理问题求解及知识编译算法设计。本文旨在提高基于扩展规则的知识编译算法的编译效率和编译质量，其中编译质量用编译结... 详细信息

扩展规则推理方法是2003年提出的一种新型推理方法，得到了国内外学者的认可。基于扩展规则能够实现命题逻辑中的推理问题求解及知识编译算法设计。本文旨在提高基于扩展规则的知识编译算法的编译效率和编译质量，其中编译质量用编译结果的规模来衡量。本文首先提出了一种新的推理规则，超扩展规则(SER)，并证明了超扩展规则与扩展负超归结的关联关系;利用超扩展规则，能将一个SAT问题编译为EPCCL理论，因此重写了殷明浩等人提出的KCER算法;并提出了基于超扩展规则的动态在线推理算法IKCCER，采用离线编译和在线推理过程交互执行的方式，在保持推理效率不改变的同时，极大地降低了空间复杂性。动态在线推理进一步扩展了基于扩展规则的知识编译方法的应用范围。超扩展规则是对扩展规则的扩充，基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集与差集，并将所得结果以EPCCL理论的形式保存。本文首次提出了扩展反驳方法，是一种新型推理方法，并在该推理方法与知识编译之间建立了联系。基于超扩展规则的性质，本文还提出了两种知识编译算法：求并知识编译算法UKCHER和求差知识编译算法DKCHER，是两种新的知识编译算法。算法UKCHER是目前为止唯一一个可并行的EPCCL理论编译算法，算法DKCHER对于相变点附近的难解问题具有较高的编译效率和编译质量。实验结果表明：UKCHER算法的编译效率和编译质量均优于Lin等人提出的KCER算法;当子句数和变量数的比值较大时，DKCHER算法的编译效率和编译质量是最优的，相比于现有EPCCL理论编译算法，该算法具有较强的竞争力。本文提出的三种知识编译算法从不同角度提升了扩展规则知识编译算法的性能。IKCCER算法改善了KCER算法的内存消耗，从而使得原本KCER算法因内存溢出而解决不了的SAT实例得以解决。DKCHER算法和UKCHER算法是基于超扩展规则的两种新型结构的算法。不同于KCER算法的桶删除理论，上述两种算法采用了新的架构，因此与KCER算法具有明显不同的特性。DKCHER算法更适合于相变点附近的SAT实例，而UKCHER算法能够通过动态在线推理提前判断出输入子句集的可满足性。

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

基于MACR和CAL启发式的求差知识编译算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

电子学报 2020年第2期48卷 285-290页

作者：牛当当吕帅王金艳刘斌西北农林科技大学信息工程学院陕西杨凌712100 吉林大学计算机科学与技术学院吉林长春130012 陕西省农业信息感知与智能服务重点实验室(西北农林科技大学) 陕西杨凌712100 农业农村部农业物联网重点实验室(西北农林科技大学) 陕西杨凌712100 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 广西师范大学计算机科学与信息工程学院广西桂林541004

DKCHER算法是基于超扩展规则的求差知识编译算法.本文首先研究了DKCHER算法的执行流程,并定义了互补量的概念,然后设计了启发式策略MACR(maximum complementary amount of clauses with middle result),用于动态选择与中间结果互补量最... 详细信息

DKCHER算法是基于超扩展规则的求差知识编译算法.本文首先研究了DKCHER算法的执行流程,并定义了互补量的概念,然后设计了启发式策略MACR(maximum complementary amount of clauses with middle result),用于动态选择与中间结果互补量最大的子句.针对互补展开过程,设计了动态启发式策略CAL(optimal sequence sorted by complementary amount of literals),将互补展开中的文字按照与输入公式互补量的大小进行排序并展开.将上述两种启发式策略与DKCHER算法相结合,分别设计了MACR_DKCHER算法、CAL_DKCHER算法和MACR_CAL_DKCHER算法.实验结果表明,MACR启发式策略能够提升DKCHER算法的编译效率和编译质量,编译效率最高可提升9倍,编译质量最高可提升1.9倍;CAL启发式策略在子句数和变量数比值较大的实例上,能够提高DKCHER算法的编译效率,但会降低DKCHER算法的编译质量;MACR_CAL启发式最高可将DKCHER算法的编译效率提高12倍,但会导致DKCHER算法的编译质量有所降低.

关键词：知识编译扩展规则超扩展规则 EPCCL理论启发式策略

在线全文

学校读者我要写书评

暂无评论

基于格局检测的模型计数方法

软件学报 2020年第2期31卷 395-405页

作者：贺甫霖刘磊吕帅牛当当王强吉林大学计算机科学与技术学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012 西北农林科技大学信息工程学院陕西杨凌712100

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能... 详细信息

模型计数是指求出给定命题公式的模型数,是SAT问题的泛化.模型计数在人工智能领域取得了广泛应用,很多现实问题都可以规约为模型计数进行求解.目前,常用的模型计数求解器主要有Cachet与sharp SAT,它们均采用完备方法且具有高效的求解能力,但其求解效率对模型数不敏感.有理由猜测:当给定问题的模型较少时,不完备算法可能发挥其效率优势而更适合模型计数.局部搜索是求解SAT问题的高效不完备方法,Cai等人提出了格局检测策略,并将其应用到局部搜索方法中,提出了SWcc算法,具有很高的求解效率.对SWcc算法进行扩充,分别得到了迭代法与优化后的增量法两种效率较高的不完备模型计数方法,给出了两种方法的思路和具体实现.最后给出了大量测试样例的实验结果,以验证当给定合取范式的模型较少时,该迭代法与优化后的增量法的求解效率有所提升.

关键词：模型计数局部搜索格局检测

在线全文

学校读者我要写书评

暂无评论

基于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多倍.

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