高级检索
    谷文祥, 王金艳, 殷明浩. 基于MCN和MO启发式策略的扩展规则知识编译方法[J]. 计算机研究与发展, 2011, 48(11): 2064-2073.
    引用本文: 谷文祥, 王金艳, 殷明浩. 基于MCN和MO启发式策略的扩展规则知识编译方法[J]. 计算机研究与发展, 2011, 48(11): 2064-2073.
    Gu Wenxiang, Wang Jinyan, Yin Minghao. Knowledge Compilation Using Extension Rule Based on MCN and MO Heuristic Strategies[J]. Journal of Computer Research and Development, 2011, 48(11): 2064-2073.
    Citation: Gu Wenxiang, Wang Jinyan, Yin Minghao. Knowledge Compilation Using Extension Rule Based on MCN and MO Heuristic Strategies[J]. Journal of Computer Research and Development, 2011, 48(11): 2064-2073.

    基于MCN和MO启发式策略的扩展规则知识编译方法

    Knowledge Compilation Using Extension Rule Based on MCN and MO Heuristic Strategies

    • 摘要: 在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3~1/39,从而大幅度提高之后的在线推理阶段的效率.

       

      Abstract: The key idea of theorem proving using extension rule is to use the inverse of resolution and the inclusionexclusion principle to circumvent the problem of space complexity. Knowledge compilation using extension rule, called KCER, is a new method for knowledge compilation, in which both the compilation and the querying are based on the extension rule. So KCER can be considered as a counterpart of other existing methods for knowledge compilation. After deep research on the method, two heuristic strategies MCN and MO are proposed. They utilize the information contained in the set of clauses to choose respectively relevant clauses and variables, in order to reduce the times of using extension rule, and further decrease the size of the compiled knowledge base. Furthermore, we apply MCN, MO and both of them to KCER, respectively. The algorithms MCN_KCER, MO_KCER and MCN_MO_KCER, are designed and implemented. Experimental results indicate that the MCN and MO play a great role in minimizing the size of the compiled knowledge base. When MCN and MO are used together, the efficiency becomes better. The sizes gained by MCN_MO_KCER are 1/3—1/39 times larger the sizes gained by knowledge compilation using extension rule without any heuristic strategy. Consequently, the efficiency will be advanced largely in the online reasoning phase.

       

    /

    返回文章
    返回