Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

NIU Dang-dang; L; Shuai

doi:10.3969/j.issn.0372-2112.2019.11.009

您当前的位置：

首页 >

文章列表页 >

Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

更新时间：2025-07-16

- Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics
- Acta Electronica Sinica Vol. 47, Issue 11, Pages: 2299-2303(2019)
- 作者机构：
  
  1. 西北农林科技大学信息工程学院, 陕西杨凌,712100
  2. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
  3. 广西师范大学计算机科学与信息工程学院,广西,桂林,541004
  4. 西北农林科技大学信息工程学院陕西杨凌,712100
  5. 吉林大学计算机科学与技术学院,吉林,长春,130012
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2019.11.009
  CLC： TP301TP181
- Published Online：25 November 2019，
  
  Published：2019
- 稿件说明：
移动端阅览
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：

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

Views

175

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics

Parallel Knowledge Compilation Algorithms for EPCCL Theory

CIMHS: A Method of Computing all Minimal Hitting Sets for Minimal Conflict Sets Based on an Optimized Incremental Strategy

An Extension Rule Algorithm Based on Local Search with IAPS Strategies

Related Author

LIU Bin

LV Shuai

WANG Jin-yan

LIU Lei

NIU Dang-dang

HUANG Sen

ZHAO Xiang-fu

WEI Xia

Related Institution

农业农村部农业物联网重点实验室(西北农林科技大学) 陕西杨凌

陕西省农业信息感知与智能服务重点实验室(西北农林科技大学) 陕西杨凌

陕西省农业信息感知与智能服务重点实验室(西北农林科技大学), 陕西杨凌

农业农村部农业物联网重点实验室(西北农林科技大学), 陕西杨凌

Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education

⁰