基于矩阵计算极小碰集的启发式算法

吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 106-110.

基于矩阵计算极小碰集的启发式算法

欧阳丹彤^1,2, 耿雪娜^1,2, 郭劲松^1,2, 王晓宇^1,2

1. 吉林大学符号计算与知识工程教育部重点实验室, 长春 130012;
2. 吉林大学计算机科学与技术学院长春 130012

收稿日期:2012-03-20 出版日期:2013-01-01 发布日期:2013-01-01
作者简介:欧阳丹彤(1968-),女,教授,博士生导师.研究方向:基于模型诊断,自动推理.E-mail:ouyangdantong@163.com
基金资助:
国家自然科学基金项目(60973089,60873148,60773097,61003101);高等学校博士学科点专项科研基金项目(20100061110031);吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目;浙江省自然科学基金项目(Y1100191).

Heuristic algorithm of computing minimal hitting sets matrix

OUYANG Dan-tong^1,2, GENG Xue-na^1,2, GUO Jin-song^1,2, WANG Xiao-yu^1,2

1. Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130012, China;
2. College of Computer Science and Technology, Jilin University, Changchun 130012, China

Received:2012-03-20 Online:2013-01-01 Published:2013-01-01

摘要/Abstract

摘要： 提出了一种基于矩阵模型计算极小碰集的新方法。通过在矩阵中存储冲突集合簇的相关信息,引入集合簇中元素的频率作为启发信息,完成对极小碰集的计算。该算法的数据结构简单,程序易于实现,同时启发信息的引入减少了节点的生成。该算法可以产生而且仅产生所有的极小碰集。实验结果表明该算法有较高的计算效率。

关键词: 人工智能, 基于模型诊断, 冲突集, 极小碰集, 启发式算法

Abstract: In model-based diagnosis, computing minimal hitting sets is an important part of the representation of candidate diagnostic results. In this paper, a new method is proposed to obtain the minimal hitting sets by matrix. In this method, the related information of the conflict sets is stored in a matrix. The frequencies of elements of the set cluster are taken as the heuristic information to compute the minimal hitting sets. The data structure of the algorithm is simple and the implementation of the algorithm is easy. The introduction of heuristic information reduces the number of the generated nodes. This algorithm can generate and only generate all the minimal hitting sets. Experiment results show that the proposed algorithm has a better computational efficiency than other algorithms.

Key words: artificial intelligence, model-based diagnosis, conflict set, minimal hitting set, heuristic algorithm

中图分类号:

TP18

欧阳丹彤, 耿雪娜, 郭劲松, 王晓宇. 基于矩阵计算极小碰集的启发式算法[J]. 吉林大学学报(工学版), 2013, 43(01): 106-110.

OUYANG Dan-tong, GENG Xue-na, GUO Jin-song, WANG Xiao-yu. Heuristic algorithm of computing minimal hitting sets matrix[J]. 吉林大学学报(工学版), 2013, 43(01): 106-110.

参考文献

[1] Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32 (1): 57-96.

[2] Greiner R, Smith B A, Wilkerson R W. A correction to the algorithm in Reiter's theory of diagnosis[J]. Artificial Intelligence, 1989, 41 (1): 79-88.

[3] Wotawa F. A variant of Reiter's hitting-set algori-thm[J]. Information Processing Letters, 2001,79:45-51.

[4] 姜云飞, 林笠. 用对分HS-树计算最小碰集[J]. 软件学报, 2002,13 (12): 2267-2274. Jiang Yun-fei, Lin Li. Computing the minimal hitting sets with binary HS-TREE[J]. Journal of Software, 2002, 13(12): 2267-2274.

[5] Lin L, Jiang Y F. Computing minimal hitting sets with genetic algorithm//Proceedings of the 13th International Workshop on Principles of Diagnosis, Austria, 2002:77-80.

[6] 姜云飞, 林笠. 用布尔代数方法计算最小碰集[J]. 计算机学报, 2003,26(8):919-924. Jiang Yun-fei, Lin Li. The computation of hitting sets with boolean formulas[J]. Chinese Journal of Computers, 2003,26(8):919-924.

[7] Zhao X F, Ouyang D T. A method of combining SE-tree to compute all minimal hitting sets[J]. Progress in Natural Science,2006(2): 169-174.

[8] 陈晓梅, 孟晓风, 乔仁晓. 基于BNB-HSSE计算全体碰集的方法[J]. 仪器仪表学报, 2010, 31(1): 61-67. Chen Xiao-mei, Meng Xiao-feng, Qiao Ren-xiao. Method of computing all minimal hitting set based on BNB-HSSE[J]. Chinese Journal of Science Instrument, 2010, 31(1): 61-67.

相关文章 15

[1]	董飒, 刘大有, 欧阳若川, 朱允刚, 李丽娜. 引入二阶马尔可夫假设的逻辑回归异质性网络分类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1571-1577.
[2]	顾海军, 田雅倩, 崔莹. 基于行为语言的智能交互代理[J]. 吉林大学学报(工学版), 2018, 48(5): 1578-1585.
[3]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4]	张浩, 占萌苹, 郭刘香, 李誌, 刘元宁, 张春鹤, 常浩武, 王志强. 基于高通量数据的人体外源性植物miRNA跨界调控建模[J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5]	黄岚, 纪林影, 姚刚, 翟睿峰, 白天. 面向误诊提示的疾病-症状语义网构建[J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6]	李雄飞, 冯婷婷, 骆实, 张小利. 基于递归神经网络的自动作曲算法[J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7]	刘杰, 张平, 高万夫. 基于条件相关的特征选择方法[J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8]	焦玉玲, 徐良成, 王占中, 张鹏. 基于有向网络的双U型装配线平衡实验与分析[J]. 吉林大学学报(工学版), 2018, 48(2): 454-459.
[9]	王旭, 欧阳继红, 陈桂芬. 基于多重序列所有公共子序列的启发式算法度量多图的相似度[J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[10]	杨欣, 夏斯军, 刘冬雪, 费树岷, 胡银记. 跟踪-学习-检测框架下改进加速梯度的目标跟踪[J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[11]	刘雪娟, 袁家斌, 许娟, 段博佳. 量子k-means算法[J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[12]	曲慧雁, 赵伟, 秦爱红. 基于优化算子的快速碰撞检测算法[J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[13]	李嘉菲, 孙小玉. 基于谱分解的不确定数据聚类方法[J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[14]	邵克勇, 陈丰, 王婷婷, 王季驰, 周立朋. 无平衡点分数阶混沌系统全状态自适应控制[J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[15]	王生生, 王创峰, 谷方明. OPRA方向关系网络的时空推理[J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed