关于属性约简和集合覆盖问题的探讨  

A Study of Reduction of Attributes and Set Covering Problem

作　　者：陈彩云[1] 李治国[1] 

机构地区：[1]南开大学组合数学研究中心,天津300071

出　　处：《计算机工程与应用》2004年第2期44-46,84,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助;国家973重点基础研究规划项目(编号:G19980306)资助;教育部;科技部基金资助

摘　　要：论文探讨了粗糙集的属性约简和集合覆盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约简问题与集合覆盖问题联系起来,从而将粗糙集的属性约简问题简化为集合覆盖问题。然后用几个定理及其证明说明了这种联系是存在的。基于这种联系,推断出求最小属性约简问题算法的近似度的上下界为ln(｜U'｜)-lnln(｜U'｜)+O(1)和(1-o(1))ln(｜U'｜)。最后,利用两个范例分别演示了如何具体地构造相关矩阵以及如何将解决集合覆盖问题的思想和方法应用到解决属性约简问题中来,由此推理如果将文献5中的解决集合覆盖问题的启发式方法应用到解决最小属性约简中,属性约简的复杂度为o(r2m3+m2),并且能以78%的“概率”得到最小属性约简。This paper discusses the relationship between the reduction of attributes and set covering by constructing the relation matrix and then gives several theorems to interpret this relationship.The authors deduce the upper bound and the lower bound of approximation is ln(｜U '｜)-lnln(｜U '｜)+O(1)and(1-o(1))ln(｜U '｜)respectively.In the end they give two examples to demonstrate how to construct the relation matrix and how the ideas and methods of set covering can be applied into the problem of reduction of attributes.And at the same time we can infer that complexity and the precision of the reduction of attributes is o(r 2 m 3 +m 2 )and78percent respectively from the heuristic algorithm appearing in reference5.

关 键 词：属性约简 集合覆盖 NP—hard问题 粗糙集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]