| 基于矩阵计算极小碰集的启发式算法 |
| |
| 引用本文： | 欧阳丹彤,耿雪娜,郭劲松,王晓宇. 基于矩阵计算极小碰集的启发式算法[J]. 吉林大学学报(工学版), 2013, 43(1): 106-110 |
| |
| 作者姓名： | 欧阳丹彤 耿雪娜 郭劲松 王晓宇 |
| |
| 作者单位： | 吉林大学符号计算与知识工程教育部重点实验室,长春130012;吉林大学计算机科学与技术学院长春130012 |
| |
| 基金项目： | 国家自然科学基金项目(60973089,60873148,60773097,61003101);高等学校博士学科点专项科研基金项目(20100061110031);吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05);浙江师范大学计算机软件与理论省级重中之重学科开放基金项目;浙江省自然科学基金项目(Y1100191) |
| |
| 摘 要： | 提出了一种基于矩阵模型计算极小碰集的新方法。通过在矩阵中存储冲突集合簇的相关信息,引入集合簇中元素的频率作为启发信息,完成对极小碰集的计算。该算法的数据结构简单,程序易于实现,同时启发信息的引入减少了节点的生成。该算法可以产生而且仅产生所有的极小碰集。实验结果表明该算法有较高的计算效率。
|
| 关 键 词： | 人工智能 基于模型诊断 冲突集 极小碰集 启发式算法 |
Heuristic algorithm of computing minimal hitting sets matrix |
| |
| OUYANG Dan-tong,GENG Xue-na,GUO Jin-song,WANG Xiao-yu. Heuristic algorithm of computing minimal hitting sets matrix[J]. Journal of Jilin University:Eng and Technol Ed, 2013, 43(1): 106-110 |
| |
| Authors: | OUYANG Dan-tong GENG Xue-na GUO Jin-song WANG Xiao-yu |
| |
| Affiliation: | 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) |
| |
| 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. |
| |
| Keywords: | artificial intelligence model-based diagnosis conflict set minimal hitting set heuristic algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
