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

NIU Dang-dang; LV Shuai; WANG Jin-yan; LIU Bin

doi:10.3969/j.issn.0372-2112.2020.02.009

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics
- Acta Electronica Sinica Vol. 48, Issue 2, Pages: 285-290(2020)
- 作者机构：
  
  1. 西北农林科技大学信息工程学院, 陕西杨凌,712100
  2. 陕西省农业信息感知与智能服务重点实验室(西北农林科技大学), 陕西杨凌,712100
  3. 农业农村部农业物联网重点实验室(西北农林科技大学), 陕西杨凌,712100
  4. 西北农林科技大学信息工程学院陕西杨凌,712100
  5. 吉林大学计算机科学与技术学院,吉林,长春,130012
  6. 陕西省农业信息感知与智能服务重点实验室(西北农林科技大学) 陕西杨凌,712100
  7. 农业农村部农业物联网重点实验室(西北农林科技大学) 陕西杨凌,712100
  8. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
  9. 广西师范大学计算机科学与信息工程学院,广西,桂林,541004
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2020.02.009
  CLC： TP301TP181
- Published Online：25 February 2020，
  
  Published：2020
- 稿件说明：
移动端阅览
NIU Dang-dang, LV Shuai, WANG Jin-yan, et al. Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics[J]. Acta Electronica Sinica, 2020, 48(2): 285-290.
DOI：

NIU Dang-dang, LV Shuai, WANG Jin-yan, et al. Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics[J]. Acta Electronica Sinica, 2020, 48(2): 285-290. DOI： 10.3969/j.issn.0372-2112.2020.02.009.

摘要

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算法的编译质量有所降低.

Abstract

DKCHER is a knowledge compilation algorithm of computing difference based on hyper extension rule. We study on the executing process of DKCHER algorithm in this paper

and define the concept of complementary amount. We design MACR (maximum complementary amount of clauses with middle result) heuristics based on complementary amount

which is used to dynamically select the clause of maximum complementary amount with middle result. For complementary unfolding in DKCHER

we design dynamic heuristics CAL (optimal sequence sorted by complementary amount of literals)

which sort the literals in complementary unfolding based on their complementary amounts. Combining the above two heuristic methods with DKCHER

MACR_DKCHER algorithm

CAL_DKCHER algorithm and MACR_CAL_DKCHER algorithm are designed. Experimentally

MACR heuristics improves the compilation efficiency and compilation quality of DKCHER. MACR heuristics can improve the efficiency of DKCHER by 9 times in the best case. CAL heuristics can significantly improve the compilation efficiency of DKCHER on the instances with big ratio of clause number with variable number. MACR_CAL heuristics can improve the efficiency of DKCHER by 12 times in the best case. But MACR_CAL heuristics reduces the compilation quality of DKCHER.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Knowledge Compilation Algorithm of Computing Difference Based on MOVR 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

Shuai

NIU Dang-dang

LIU Lei

WEI Xia

ZHAO Xiang-fu

HUANG Sen

WANG Jin-yan

Related Institution

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

College of Computer Science and Technology, Jilin University

Department of Computer， Zhejiang Normal University

⁰