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

牛当当; 吕帅; 王金艳

doi:10.3969/j.issn.0372-2112.2019.11.009

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 基于MOVR启发式的求差知识编译算法
- Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics
- 电子学报 2019年47卷第11期页码：2299-2303
- 作者机构：
  
  1. 西北农林科技大学信息工程学院, 陕西杨凌,712100
  2. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
  3. 广西师范大学计算机科学与信息工程学院,广西,桂林,541004
  4. 西北农林科技大学信息工程学院陕西杨凌,712100
  5. 吉林大学计算机科学与技术学院,吉林,长春,130012
- 作者简介：
- 基金信息：
  
  国家自然科学基金 (No.61502197,No.61503044,No.61763003,No.61502111);吉林省科技发展计划资助项目 (No.20180101053JC);广西省自然科学基金 (No.2016GXNSFAA380192);西北农林科技大学博士科研启动基金 (No.Z109021813)
- DOI：10.3969/j.issn.0372-2112.2019.11.009
  中图分类号： TP301TP181
- 网络出版：2019-11-25，
  
  纸质出版：2019
- 稿件说明：
移动端阅览
牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019,47(11):2299-2303.

NIU Dang-dang, L, Shuai. Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics[J]. Acta Electronica Sinica, 2019, 47(11): 2299-2303.
牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019,47(11):2299-2303. DOI： 10.3969/j.issn.0372-2112.2019.11.009.

NIU Dang-dang, L, Shuai. Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics[J]. Acta Electronica Sinica, 2019, 47(11): 2299-2303. DOI： 10.3969/j.issn.0372-2112.2019.11.009.

摘要

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

Abstract

DKCHER is a knowledge compilation algorithm of computing difference based on hyper extension rule

which is the best EPCCL compiler so far. We research the executing process of DKCHER algorithm in this paper

and design MOVR (maximum occurrence number of variables in middle result) heuristics

which is used to dynamically select the clause with maximum occurrence number of variables in middle result. By combining MOVR heuristics with DKCHER

MOVR_DKCHER algorithm is designed. Experimentally

MOVR heuristics can significantly improve the compilation efficiency and compilation quality of DKCHER

in which the compilation efficiency of DKCHER can be averagely improved about 70 times

and the improvement can be up to 237 times at most.

关键词

Keywords

references

浏览量

175

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

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

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

CIMHS：基于优化增量策略求解极小碰集的方法

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