(吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (dengzy19941019@163.com)
出版日期: 2018-04-01基金资助:国家自然科学基金项目(61672261, 61502199, 61402196, 61373052)；浙江省自然科学基金项目(LY16F020004)Computing the Minimal Hitting Sets with Dynamic Maximum Element Coverage Value
Deng Zhaoyong, Ouyang Dantong, Geng Xuena, Liu Jie(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)
Online: 2018-04-01摘要/Abstract
摘要： 在基于模型诊断(model-based diagnosis, MBD)中，因为所有极小冲突集的极小碰集就是待诊断系统的诊断结果，所以利用所有极小冲突集构造极小冲突集合簇，并基于极小冲突集合簇计算极小碰集是诊断的关键步骤.提出一种基于动态极大元素覆盖值求解极小碰集的新算法.该算法按照元素的元素覆盖值从大到小的顺序依次处理元素，并在求解碰集的过程中加入启发式策略和剪枝策略，使得搜索空间极大减少；利用邻接链表存储输入的极小冲突集合簇，邻接链表相对于用矩阵作为存储结构有较好的空间开销且通过邻接指向能快速地找到元素可以覆盖的集合簇中的元素；每得到一个碰集便使用极小碰集判定规则进行筛选，因此算法结束时可以产生而且仅产生所有的极小碰集.实验结果表明该算法有较高的计算效率.
参考文献
相关文章 13
| [1] | 欧阳丹彤, 高菡, 徐旖旎, 张立明. 结合故障逻辑关系的极小冲突集求解方法[J]. 计算机研究与发展, 2020, 57(7): 1472-1480. |
| [2] | 田乃予,欧阳丹彤,刘梦,张立明. 基于子集一致性检测的诊断解极小性判定方法[J]. 计算机研究与发展, 2019, 56(7): 1396-1407. |
| [3] | 曹斌,洪峰,王凯,徐锦婷,赵立为,范菁. Uroad:一种高效的大规模多对多拼车匹配算法[J]. 计算机研究与发展, 2019, 56(4): 866-883. |
| [4] | 欧阳丹彤,陈晓艳,叶靖,邓召勇,张立明. 基于极小碰集求解算法的测试向量集约简[J]. 计算机研究与发展, 2019, 56(11): 2448-2457. |
| [5] | 王荣全,欧阳丹彤,王艺源,刘思光,张立明. 结合DOEC极小化策略的SAT求解极小碰集方法[J]. 计算机研究与发展, 2018, 55(6): 1273-1281. |
| [6] | 欧阳丹彤,智华云,刘伯文,张立明,张永刚. 基于伪故障度生成枚举树的极小诊断求解方法[J]. 计算机研究与发展, 2018, 55(4): 782-790. |
| [7] | 徐旖旎,欧阳丹彤,刘梦,张立明,张永刚. 结合故障输出结构特征的极小冲突求解算法[J]. 计算机研究与发展, 2018, 55(11): 2386-2394. |
| [8] | 刘思光,欧阳丹彤,王艺源,贾凤雨,张立明. 结合SE-Tree结构特征的极小碰集求解算法[J]. 计算机研究与发展, 2016, 53(11): 2556-2566. |
| [9] | 王艺源,欧阳丹彤,张立明,张永刚. 利用CSP求解极小碰集的方法[J]. 计算机研究与发展, 2015, 52(3): 588-595. |
| [10] | 刘显敏,李建中. 一种扩展条件函数依赖的发现算法[J]. 计算机研究与发展, 2015, 52(1): 130-140. |
| [11] | 赵小欢,夏靖波,付凯,李明辉. 高速网络流频繁项挖掘算法[J]. 计算机研究与发展, 2014, 51(11): 2458-2469. |
| [12] | 张立明 欧阳丹彤 曾海林. 基于动态极大度的极小碰集求解方法[J]. , 2011, 48(2): 209-215. |
| [13] | 谷文祥, 王金艳, 殷明浩,. 基于MCN和MO启发式策略的扩展规则知识编译方法[J]. , 2011, 48(11): 2064-2073. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3671
