• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

结合SE-Tree结构特征的极小碰集求解算法

刘思光, 欧阳丹彤, 王艺源, 贾凤雨, 张立明

刘思光, 欧阳丹彤, 王艺源, 贾凤雨, 张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. DOI: 10.7544/issn1000-1239.2016.20150396
引用本文: 刘思光, 欧阳丹彤, 王艺源, 贾凤雨, 张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. DOI: 10.7544/issn1000-1239.2016.20150396
shu
Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, Zhang Liming. Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree[J]. Journal of Computer Research and Development, 2016, 53(11): 2556-2566. DOI: 10.7544/issn1000-1239.2016.20150396
Citation: Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, Zhang Liming. Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree[J]. Journal of Computer Research and Development, 2016, 53(11): 2556-2566. DOI: 10.7544/issn1000-1239.2016.20150396
shu
刘思光, 欧阳丹彤, 王艺源, 贾凤雨, 张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. CSTR: 32373.14.issn1000-1239.2016.20150396
引用本文: 刘思光, 欧阳丹彤, 王艺源, 贾凤雨, 张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. CSTR: 32373.14.issn1000-1239.2016.20150396
shu
Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, Zhang Liming. Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree[J]. Journal of Computer Research and Development, 2016, 53(11): 2556-2566. CSTR: 32373.14.issn1000-1239.2016.20150396
Citation: Liu Siguang, Ouyang Dantong, Wang Yiyuan, Jia Fengyu, Zhang Liming. Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree[J]. Journal of Computer Research and Development, 2016, 53(11): 2556-2566. CSTR: 32373.14.issn1000-1239.2016.20150396
shu

结合SE-Tree结构特征的极小碰集求解算法

  • (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (lsgmliss@163.com)

基金项目: 国家自然科学基金项目(61133011,61402196,61272208,61003101,61170092)；中国博士后科学基金项目(2013M541302)；吉林省科技发展计划基金项目(20140520067JH)；浙江师范大学计算机软件与理论省级重中之重学科开放基金项目(ZSDZZZZXK12) This work was supported by the National Natural Science Foundation of China (61133011,61402196,61272208,61003101,61170092), the China Postdoctoral Science Foundation (2013M541302), the Science and Technology Development Program of Jilin Province (20140520067JH), and the Provincial Key Disciplines Foundation of Computer Software and Theory of Zhejiang Normal University (ZSDZZZZXK12).
详细信息

  • 中图分类号: TP18

Algorithm of Computing Minimal Hitting Set Based on the Structural Feature of SE-Tree

  • (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)

摘要

    摘要
  • 摘要: 在结合SE-Tree计算集合簇极小碰集的过程中,现有算法会对大量不会产生碰集的冗余节点进行访问.这无疑将影响算法的效率,冗余节点比例越高,影响越大.通过对SE-Tree中叶节点的特殊性质的分析,并结合现有碰集算法有解空间中冗余节点的特征,提出非解冗余节点概念.在对SE-Tree的结构特征进行深入分析基础上,根据非碰集的子集也不是碰集的特点,提出辅助剪枝的概念,通过在剪枝树上设置剪枝判定节点,减少对极小碰集求解过程中无解空间的访问;针对较大规模问题,还提出结合多级辅助剪枝树的极小碰集求解算法,进而较大程度地减少对非解冗余节点的访问;根据多级辅助剪枝树及SE-Tree的结构特征,给出提前终止算法的判定条件,并证明了此算法的正确性.实验结果表明:与效率较高的Boolean算法相比,该算法高效且易于实现,尤其是对规模较大的问题,效率能提升1个数量级.
    Abstract: During the process of computing minimal hitting set (MHS) by SE-Tree, it will generate many redundant nodes that cannot be pruned by current SE-Tree based algorithms, which affects the efficiency of these algorithms, i.e., the higher the ratio of redundant nodes is, the greater likely the impact of algorithms has. In this paper, firstly we introduce the definition of redundant nodes by analyzing the characteristic of leaf-node in SE-Tree and the redundant nodes in solution space in existent algorithms. Secondly, on the basis of analyzing the structural feature of SE-Tree and the theory that the subset of non-hitting set is non-hitting set, we propose the concept of assistant pruning tree. Specially, the decision nodes are added into the assistant pruning tree, which can largely reduce the visit of non-solution space. Furthermore, in order to decrease the visit of non-solution space when computing larger problem as much as possible, the algorithm of computing minimal hitting set combining with multi-level assistant pruning tree is proposed. Finally, we set a reasonable termination condition to make our algorithm stop without losing correct solution as early as possible, and then prove its correctness. Results show that the proposed algorithm is easily implemented and efficient. Moreover, our algorithm significantly outperforms a state-of-the-art minimal hitting set algorithm Boolean, even up to one order of magnitude for some instances.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(27)

  • 期刊类型引用(15)

    1. 吴佳青，任大鹏. 我国人工智能芯片发展探析. 中国工程科学. 2025(01): 133-141 . 百度学术
    2. 仝杰，齐子豪，蒲天骄，宋睿，张鋆，谈元鹏，王晓飞. 电力物联网边缘智能：概念、架构、技术及应用. 中国电机工程学报. 2024(14): 5473-5496 . 百度学术
    3. 万朵，胡谋法，肖山竹，张焱. 面向边缘智能计算的异构并行计算平台综述. 计算机工程与应用. 2023(01): 15-25 . 百度学术
    4. 赵二虎，吴济文，肖思莹，晋振杰，徐勇军. 嵌入式异构智能计算系统并行多流水线设计. 电子学报. 2023(11): 3354-3364 . 百度学术
    5. 李秀敏，陈梓烁，陈雅琪. 我国人工智能芯片产业协同创新网络时空演化特征分析. 科技管理研究. 2023(23): 142-153 . 百度学术
    6. 赵一煊，刘飞阳，高晗，王建生. DNN加速器技术发展及航空计算系统应用展望. 航空计算技术. 2022(03): 130-134 . 百度学术
    7. 谢坤鹏，卢冶，靳宗明，刘义情，龚成，陈新伟，李涛. FAQ-CNN:面向量化卷积神经网络的嵌入式FPGA可扩展加速框架. 计算机研究与发展. 2022(07): 1409-1427 . 本站查看
    8. 蒲明博，李向平，张杨，郑美玲，粟雅娟，曹耀宇，曹暾，徐挺，段宣明，冯帅，孙玲. 芯片制造中的光学微纳加工技术前沿与挑战. 中国科学基金. 2022(03): 460-467 . 百度学术
    9. 高原，杨娇，赵凌，温川飙，张艺凡，罗悦. 运用人工神经网络技术结合穴位敏化理论探索慢性稳定性心绞痛疾病辅助预测模型的构建思路. 世界科学技术-中医药现代化. 2021(02): 628-634 . 百度学术
    10. 渠鹏，陈嘉杰，张悠慧，郑纬民. 实现软硬件解耦合的类脑计算硬件设计方法. 计算机研究与发展. 2021(06): 1146-1154 . 本站查看
    11. 魏东，董博晨，刘亦青. 改进神经网络的图像识别系统设计与硬件实现. 电子与信息学报. 2021(07): 1828-1833 . 百度学术
    12. 张雪怡，曹哲，刘宗宝. 智能芯片技术发展综述及医疗健康领域应用. 中国集成电路. 2021(09): 16-22+36 . 百度学术
    13. 郭经红，梁云，陈川，陈硕，陆阳，黄辉. 电力智能传感技术挑战及应用展望. 电力信息与通信技术. 2020(04): 15-24 . 百度学术
    14. 袁烨，张永，丁汉. 工业人工智能的关键技术及其在预测性维护中的应用现状. 自动化学报. 2020(10): 2013-2030 . 百度学术
    15. 赵晨，周义明. 基于FPGA的模数转换芯片AD7705/AD7706控制电路设计. 北京石油化工学院学报. 2019(04): 54-58 . 百度学术

    其他类型引用(12)

    • 资源附件(0)
计量
  • 文章访问数: 
  • HTML全文浏览量:  0
  • PDF下载量: 
  • 被引次数: 27
出版历程
  • 发布日期:  2016-10-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(27)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计