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

《基于扩展规则的知识编译方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、＾！ｐ基于扩展规则的知识编译方法研究ResearchontheKnowledgeCompilationMethodsBasedontheExtensionRule作者姓名：牛当当专业名称：计算机软件与理论指导教师：刘磊教授学位类别：工学博士论文答辩日期：2018年6月5日授予学位日期：2018年月日论文评阅人：答辩委员会组成：姓名职称工作单位姓名职称工作单位盲审专家正高级武汉大学主席许东教授密苏里大学盲审专家正高级北京大学委员徐鹰教授佐亚治大学盲审专家正高级浙江大学马志强教授东北师范大学梁艳春教授吉林大学欧阳继红

2、教授吉林大学欧阳丹彤教授吉林大学宫雷光教授吉林大学摘要摘要基于扩展规则的知识编译方法研究知识编译能够提高重复性任务的求解效率，并且已经成功被应用到模型检测、逻辑综合、诊断、产品配置、系统设计、自动规划等多个领域。知识编译的主要思想是将问题的求解分为两个基本阶段：离线编译和在线推理。提高知识编译方法的编译效率能够减少离线编译所消耗的时间，而提高知识编译方法的编译质量则能够减少每次在线推理所消耗的时间。在扩展规则的基础上，Lin等人提出了一种基于扩展规则的知识编译方法KCER，可以将子句集编译为EPCCL理论。随后，

3、许多学者针对EPCCL理论的编译展开了深入地研究。本文基于扩展规则和超扩展规则从启发式选择、新型编译框架、并行编译、互补知识编译等方面研究了EPCCL理论的编译方法，旨在进一步提高扩展规则知识编译方法的编译效率和编译质量。本文的主要研究内容和创新成果如下：1、提出了相关性矩阵的概念，并定义了相关集。通过分析相关集的性质，利用扩展规则在相关性矩阵和KCER算法之间建立了联系。基于相关集的基本信息以及相关性矩阵与KCER算法的联系，本文设计了MNE启发式和M2S启发式，用于选择满足“相关集所不能扩展出的极大项集对应E

4、PCCL理论规模较小”的子句。不同于现有启发式策略，MNE启发式和M2S启发式主要考虑不同子句长度实例中的启发式信息。最后，设计并实现了MNE_KCER算法和M2S_KCER算法。实验结果表明：对于随机子句长度的实例，MNE_KCER算法和M2S_KCER算法相比于KCER算法能够大幅度降低编译结果的规模，并且具有更高的编译效率。2、提出了一种新的EPCCL理论编译算法：求交知识编译算法IKCHER，适合难解类SAT问题的知识编译，同时是一种可并行的知识编译算法。基于超扩展规则能够求得任意两个非互补且不相互蕴含的

5、子句所能扩展出极大项集的交集、差集和并集，并将所得结果以EPCCL理论的形式保存。IKCHER算法基于超扩展规则，通过计算所有子句所不能扩展出极大项集的交集得出输入子句集所不能扩展出的极大项集，并将结果保存为EPCCL理论，然后再用相同方法求得上述计算结果所不能扩展出极大项集对应的EPCCL理论，进而得出与输入子句集等价的EPCCL理论。实验结果表明：IKCHER算法具有较高的编译效率和编I吉林大学博士学位论文译质量，是目前为止最优秀的EPCCL理论编译算法之一。3、提出了UKCHER算法和IKCHER算法的并行

6、化策略，并实现了相关并行算法。并行推理是提高推理方法效率的有效策略。基于超扩展规则研究了多个EPCCL理论的并行求并合并和并行求交合并，分别提出了PUAE算法和PIAE算法。结合并行求并编译和并行求交编译以及上述合并策略，提出了P-UKCHER算法和P-IKCHER算法。基于对输入EPCCL理论对应普通子句集的利用，设计了高效的并行求并算法imp-PUAE和并行求交算法imp-PIAE，以及相应的并行编译算法impP-IKCHER和impP-UKCHER。实验结果表明：P-UKCHER算法虽然没有提升UKCHER

7、算法的效率，但能够提升UKCHER算法编译结果的质量，最好情况下可提升4倍；impP-UKCHER算法能够提高UKCHER算法的效率，同时也能够提升编译结果的质量，同样最好情况下可提升4倍；P-IKCHER算法所使用的合并策略并没有起到加速的效果，反而使得编译效率和编译质量有所下降；impP-IKCHER算法提高了IKCHER算法的编译效率，四核并行下最高可提高两倍。4、提出了互补知识编译方法，是一种新的非等价的知识编译方法。提出了互补公式（COMF）的概念，并基于超扩展规则提出了C2C编译算法。C2C能够将任意

8、子句集编译为相应的c-FCCD公式。c-FCCD是一种互补公式，同时也是一种EPCCL理论。通过理论分析，证明了COMF和c-FCCD多项式时间内所能支持的知识编译图谱中的查询操作，以及COMF、c-FCCD和EPCCL理论多项式时间内所能支持的知识编译图谱中的转化操作。其中，c-FCCD能够在多项式时间内支持知识编译图谱中的全部八种查询操作以及两种转化操作。不同于现有知