| 基于动态极大度的极小碰集求解方法 |
| |
| 引用本文： | 张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法[J].计算机研究与发展,2011,48(2). |
| |
| 作者姓名： | 张立明 欧阳丹彤 曾海林 |
| |
| 作者单位： | 1. 吉林大学计算机科学与技术学院,长春,130012
2. 符号计算与知识工程教育部重点实验室(吉林大学),长春,130012 |
| |
| 基金项目： | 国家自然科学基金项目，吉林省科技发展计划基金项目，浙江省自然科学基金项目，欧盟合作项目，吉林大学符号计算与知识工程教育部重点实验室开放项目，吉林大学"985工程"研究生创新基金项目 |
| |
| 摘 要： | 在计算集合簇的碰集时,结合SE-Tree(set enumeration tree)形式化地表达计算过程,逐步生成所有的极小碰集.并在SE-Tree中添加了终止结点,避免了非极小碰集的产生,并且不会因剪枝而丢失正确的解.提出未扩展元素度的概念和结点度的概念,进而在扩展SE-Tree结点时按照未扩展元素度由大到小的顺序扩展,极早地生成集合簇的碰集,减少枚举树生成的结点个数,并且直接根据结点度得出结点对应的集合是否为集合簇的碰集,避免计算集合是否为集合簇的碰集.实验结果表明,该算法程序容易编制且效率较好.
|
| 关 键 词： | 关于模型的诊断 极小碰集 动态极大度 向量交集 |
Computing the Minimal Hitting Sets Based on Dynamic Maximum Degree |
| |
| Zhang Liming,Ouyang Dantong,Zeng Hailin.Computing the Minimal Hitting Sets Based on Dynamic Maximum Degree[J].Journal of Computer Research and Development,2011,48(2). |
| |
| Authors: | Zhang Liming Ouyang Dantong Zeng Hailin |
| |
| Affiliation: | Zhang Liming,Ouyang Dantong,and Zeng Hailin(School of Computer Science and Technology,Jilin University,Changchun 130012)(Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University),Ministry of Education,Changchun 130012) |
| |
| Abstract: | 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... |
| |
| Keywords: | SE-Tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
