检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

关键词：知识编译扩展规则超扩展规则 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算法能够通过动态在线推理提前判断出输入子句集的可满足性。

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

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

EPCCL理论的并行知识编译算法

电子学报 2018年第3期46卷 537-543页

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

基于超扩展规则,证明了EPCCL(Each Pair Contains Complementary Literal)理论的合并过程是可并行执行的,并设计了针对多个EPCCL理论的并行合并算法PUAE(Parallel computing Union of Any number of EPCCL).通过对EPCCL理论原始子句集的利用,提出了另一种高效的EPCCL理论并行合并算法imp-PUAE(improvement of PUAE).UKCHER(computing Union sets of maximum terms for Knowledge Compilation based on Hyper Extension Rule)是一种可并行的EPCCL理论编译算法,分别利用PUAE和imp-PUAE设计了两个并行知识编译算法P-UKCHER(UKCHER with PUAE)和imp P-UKCHER(UKCHER with imp-PUAE).实验结果表明:P-UKCHER算法虽然没有提升UKCHER算法的效率,但能够提升UKCHER算法编译结果的质量,最好情况下可提升4倍;而imp P-UKCHER算法能够提高UKCHER算法的效率,同时也能够提升编译结果的质量,同样最好情况下可提升4倍.

关键词：知识编译扩展规则超扩展规则 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理论规约规则相邻子句规约

在线全文

学校读者我要写书评

暂无评论

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)理论并行知识编译

基于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理论启发式策略

在线全文

学校读者我要写书评

暂无评论

基于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理论启发式策略