文献类型：期刊文章

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

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

出　　处：《计算机工程与应用》

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

年　　份：2004

卷　　号：40

期　　号：2

起止页码：44-46

语　　种：中文

收录情况：AJ、BDHX、BDHX2000、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

摘　　要：论文探讨了粗糙集的属性约简和集合覆盖问题之间的联系。通过构造信息系统的相关矩阵将粗糙集的属性约简问题与集合覆盖问题联系起来,从而将粗糙集的属性约简问题简化为集合覆盖问题。然后用几个定理及其证明说明了这种联系是存在的。基于这种联系,推断出求最小属性约简问题算法的近似度的上下界为ln(｜U'｜)-lnln(｜U'｜)+O(1)和(1-o(1))ln(｜U'｜)。最后,利用两个范例分别演示了如何具体地构造相关矩阵以及如何将解决集合覆盖问题的思想和方法应用到解决属性约简问题中来,由此推理如果将文献5中的解决集合覆盖问题的启发式方法应用到解决最小属性约简中,属性约简的复杂度为o(r2m3+m2),并且能以78%的“概率”得到最小属性约简。

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

分 类 号：TP18]