东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

基于动态极大度的极小碰集求解方法

期刊名称：计算机研究与发展, 2011, 48(2):209- 215. (EI: 2011141389795
时间：0
分类：TP311.1[自动化与计算机技术—计算机软件与理论;自动化与计算机技术—计算机科学与技术]
作者机构：[1]吉林大学计算机科学与技术学院,长春130012, [2]符号计算与知识工程教育部重点实验室（吉林大学）,长春130012
相关基金：国家自然科学基金项目（60973089 60873148 60773097 61003101）; 吉林省科技发展计划基金项目（20101501 20100185 20090108 20080107）; 浙江省自然科学基金项目（Y1100191）; 欧盟合作项目（155776-EM-1-2009-1-IT-ERAMUNDUS-ECW-L12）; 吉林大学符号计算与知识工程教育部重点实验室开放项目（93K-17-2009-K05）吉林大学“985工程”研究生创新基金项目（20080242 20101026）
相关项目：基于模型的诊断若干关键问题研究及其在配置中的应用

关键词：基于模型的诊断, 极小碰集, SE-Tree, 动态极大度, 向量交集, model-based diagnosis, minimal hitting set, SE-Tree, dynamic maximum degree, intersection of vectors

中文摘要：

在计算集合簇的碰集时,结合SE-Tree（set enumeration tree）形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.

英文摘要：

A lot of theoretical and practical problems can be partly reduced to an instance of the minimal hitting set（MHS） or one of its relatives,such as the minimum set cover problem,model-based diagnosis,and teachers and courses problem.While generating MHS cluster of a collection of sets is known to be NP-hard,which necessitates heuristic approaches to handle large problems.Several exhaustive algorithms have been presented to solve the MHS problem.In this paper,we formalize the computing procedure of hitting sets by introducing SE-Tree which produces all the resolutions gradually first.As the closed nodes are added into the SE-Tree,the non-minimal hitting sets can never be produced,and the true resolutions can not be missed by pruning either.Then the concept of un-extended element degree and node degree are presented,and the node of SE-Tree is extended in accordance with the descending order of un-extended element degree.With this extended order,we not only can generate hitting set early,but also can reduce the number of generated nodes.Moreover,the node degree can be used to determine whether the set of node is a hitting set or not directly,and avoid the computing of hitting set.Results show that the corresponding algorithm is easily implemented,and the efficiency is highly improved.

同期刊论文项目