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

doi:10.3969/j.issn.0372-2112.2019.11.009

PDF(856 KB)

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

学术论文

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

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

作者信息 +

Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

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

Author information +

文章历史 +

摘要

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.

导出引用

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

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. https://doi.org/10.3969/j.issn.0372-2112.2019.11.009

中图分类号： TP301 TP181

参考文献

[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.

基金

国家自然科学基金 (No.61502197,No.61503044,No.61763003,No.61502111); 吉林省科技发展计划资助项目 (No.20180101053JC); 广西省自然科学基金 (No.2016GXNSFAA380192); 西北农林科技大学博士科研启动基金 (No.Z109021813)