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

doi:10.3969/j.issn.0372-2112.2019.11.009

电子学报 ›› 2019, Vol. 47 ›› Issue (11): 2299-2303.DOI: 10.3969/j.issn.0372-2112.2019.11.009

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

牛当当¹, 吕帅^2,3, 王金艳⁴

1. 西北农林科技大学信息工程学院, 陕西杨凌 712100;
2. 吉林大学计算机科学与技术学院, 吉林长春 130012;
3. 符号计算与知识工程教育部重点实验室(吉林大学), 吉林长春 130012;
4. 广西师范大学计算机科学与信息工程学院, 广西桂林 541004

收稿日期:2018-11-02 修回日期:2019-03-22 出版日期:2019-11-25
- 通讯作者:
- 牛当当
- 作者简介:
- 吕帅男,1981年7月出生,吉林公主岭人.2010年获得吉林大学博士学位,现为吉林大学计算机科学与技术学院副教授,主要研究方向为人工智能、智能规划与自动推理.E-mail:lus@jlu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61502197,No.61503044,No.61763003,No.61502111); 吉林省科技发展计划资助项目 (No.20180101053JC); 广西省自然科学基金 (No.2016GXNSFAA380192); 西北农林科技大学博士科研启动基金 (No.Z109021813)

Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

NIU Dang-dang¹, Lü Shuai^2,3, WANG Jin-yan⁴

1. College of Information Engineering, Northwest A&F University, Yangling, Shaanxi 712100, China;
2. College of Computer Science and Technology, Jilin University, Changchun, Jilin 130012, China;
3. Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun, Jilin 130012, China;
4. School of Computer Science and Information Engineering, Guangxi Normal University, Guilin, Guangxi 541004, China

Received:2018-11-02 Revised:2019-03-22 Online:2019-11-25 Published:2019-11-25
- Corresponding author:
- NIU Dang-dang
- Supported by:
- National Natural Science Foundation of China (No.61502197, No.61503044, No.61763003, No.61502111); Science and Technology Development Project of Jilin Province (No.20180101053JC); Natural Science Foundation of Guangxi Zhuang Autonomous Region, China (No.2016GXNSFAA380192); Doctoral Research Fund of Northwest A&F University (No.Z109021813)

摘要/Abstract

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

关键词: 知识编译, 扩展规则, 超扩展规则, EPCCL理论, 启发式策略

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.

Key words: knowledge compilation, extension rule, hyper extension rule, EPCCL theory, heuristic strategy

中图分类号:

TP301
TP181

牛当当, 吕帅, 王金艳. 基于MOVR启发式的求差知识编译算法[J]. 电子学报, 2019, 47(11): 2299-2303.

NIU Dang-dang, Lü Shuai, WANG Jin-yan . Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics[J]. Acta Electronica Sinica, 2019, 47(11): 2299-2303.

参考文献

[1] Darwiche A.Decomposable negation normal form[J].Journal of the ACM,2001,48(4):608-647.
[2] Darwiche A,Marquis P.A knowledge compilation map[J].Journal of Artificial Intelligence Research,2002,17:229-264.
[3] Broeck G V,Darwiche A.On the role of canonicity in knowledge compilation[A].Proceedings of 29th AAAI Conference on Artificial Intelligence[C].Austin,Texas,2015.1641-1648.
[4] Lai Y,Liu D Y,Wang S S.Reduced ordered binary decision diagram with implied literals:A new knowledge compilation approach[J].Knowledge and Information Systems,2013,35(3):665-712.
[5] Lai Y,Liu D Y,Yin M H.New canonical representations by augmenting OBDDs with conjunctive decomposition[J].Journal of Artificial Intelligence Research,2017,58:453-521.
[6] Amarilli A,Monet M,Senellart P.Connecting width and structure in knowledge compilation[A].Proceedings of 21st International Conference on Database Theory[C].Vienna,Austria,2018.6:1-6:17.
[7] Lin H,Sun J G,Zhang Y M.Theorem proving based on the extension rule[J].Journal of Automated Reasoning,2003,31(1):11-21.
[8] Lin H,Sun J G.Knowledge compilation using the extension rule[J].Journal of Automated Reasoning,2004,32(2):93-102.
[9] 谷文祥,王金艳,殷明浩.基于MCN和MO启发式策略的扩展规则知识编译方法[J].计算机研究与发展,2011,48(11):2064-2073. GU Wen-Xiang,WANG Jin-Yan,YIN Ming-Hao.Knowledge compilation using extension rule based on MCN and MO heuristic strategies[J].Journal of Computer Research and Development,2011,48(11):2064-2073.(in Chinese)
[10] 刘大有,赖永,林海.C2E:一个高性能的EPCCL理论编译器[J].计算机学报,2013,36(6):1254-1260. LIU Da-You,LAI Yong,LIN Hai.C2E:An EPCCL compiler with good performance[J].Chinese Journal of Computer,2013,36(6):1254-1260.(in Chinese)
[11] 刘磊,牛当当,吕帅.基于超扩展规则的知识编译方法[J].计算机学报,2016,39(8):1681-1696. LIU Lei,NIU Dang-Dang,LÜ Shuai.Knowledge compilation methods based on the hyper extension rule[J].Chinese Journal of Computers,2016,39(8):1681-1696.(in Chinese)
[12] Niu D D,Liu L,Lü S.Knowledge compilation methods based on the clausal relevance and extension rule[J].Chinese Journal of Electronics,2018,27(5):1037-1042.
[13] 柳强,何明,刘锦涛,牛彦杰,黄倩.无人机"蜂群"的蜂拥涌现行为识别与抑制机理[J].电子学报,2019,47(2):374-381. LIU Qiang,HE Ming,LIU Jin-Tao,NIU Yan-Jie,HUANG Qian.A mechanism of for identifying and suppressing the emergent flocking behaviors of UAV swarms[J].Acta Electronica Sinica,2019,47(2):374-381.(in Chinese)
[14] Li H B,Liang Y C,Zhang N,Guo J S,Xu D,Li Z S.Improving degree-based variable ordering heuristics for solving constraint satisfaction problems[J].Journal of Heuristics,2016,22(2):25-145.

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

Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	王金艳, 胡春, 牛当当, 李先贤. 基于IAPS的扩展规则局部搜索算法[J]. 电子学报, 2020, 48(5): 899-905.
[2]	牛当当, 吕帅, 王金艳, 刘斌. 基于MACR和CAL启发式的求差知识编译算法[J]. 电子学报, 2020, 48(2): 285-290.
[3]	牛当当, 刘磊, 吕帅. EPCCL理论的并行知识编译算法[J]. 电子学报, 2018, 46(3): 537-543.