主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘思光,欧阳丹彤,张立明.极小碰集求解中候选解极小性判定方法.软件学报,2018,29(12):3733-3746
极小碰集求解中候选解极小性判定方法
Method of Minimality-Checking of Candidate Solution for Minimal Hitting Set Algorithm
投稿时间:2016-03-17  修订日期:2016-11-06
DOI:10.13328/j.cnki.jos.005311
中文关键词:  基于模型诊断  极小碰集  碰集极小性判定  预剪枝  增量方法
英文关键词:model-based diagnosis  minimal hitting set  minimality-checking of hitting set  pre-pruning  incremental method
基金项目:国家自然科学基金(61133011,61402196,61272208,61003101,61170092);中国博士后科学基金(2013M541302);吉林省科技发展计划基金(20140520067JH);浙江师范大学计算机软件与理论省级重中之重学科开放基金(ZSDZZZZXK12)
作者单位E-mail
刘思光 吉林大学 计算机科学与技术学院, 吉林 长春 130012
符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 
 
欧阳丹彤 吉林大学 计算机科学与技术学院, 吉林 长春 130012
符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 
 
张立明 吉林大学 计算机科学与技术学院, 吉林 长春 130012
符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 130012 
limingzhang@jlu.edu.cn 
摘要点击次数: 902
全文下载次数: 523
中文摘要:
      极小碰集问题是人工智能中的重要问题,应用广泛.碰集极小性判定,作为极小碰集求解过程中的关键步骤,效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题,提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法,剥离了碰集极小性判定耗时与极小碰集簇大小的相关性;通过深入分析增量求解过程中非极小碰集的产生原因,给出了ICC方法的增量判定形式ⅡCC方法,使其可以尽早发现并丢弃非极小候选解,为使用其增量极小碰集求解算法带来额外的剪枝效果,进一步提升算法的效率.实验结果表明:该方法易于实现,可扩展性强,对于当前效率较高的Boolean算法,使用ⅡCC方法后,算法可求解问题的规模和整体效率均有明显提升,效率提升最高达4个数量级以上.
英文摘要:
      Minimal hitting set (MHS) problem is an important problem with widely applications in artificial intelligence. During computing all minimal hitting set, how to check the minimality of hitting sets is a key issue. Most of exhaustive MHS algorithms ensure the minimality of results by using subset checking method where its effectiveness is mainly relevant to the scale of minimal hitting sets, i.e., the larger the scale of the MHSs is, the lower the effectiveness of this method has. Consequently, when coming to solve the massive cases, the effectiveness of these algorithms is not high. To overcome this problem, this paper proposes independent coverage checking (ICC) and then develops it into an incremental method named ⅡCC. The effectiveness of this method is irrelevant to the scale of minimal hitting sets. Moreover, when computing all MHS by the incremental MHS algorithm with ⅡCC, it can incrementally test the minimality of candidate solutions, resulting in cutting down many unnecessary non-minimal hitting sets. ⅡCC is used to optimize the Boolean algorithm which is an incremental MHS algorithm using subset checking. The results show that ⅡCC method significantly outperforms the subset checking methods in terms of running time.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利