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

• 作者: 李治国 陈彩云
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 属性约 简集合覆盖 NP-hard问题 粗糙集
• 年，卷（期）: 2004,（2）
• 所属期刊栏目: 学术探讨
• 页码范围: 44-46,84
• 页数: 4页
• 分类号: TP18
• 字数: 5314字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2004.02.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈彩云	南开大学组合数学研究中心	6	122	6.0	6.0
2	李治国	南开大学组合数学研究中心	6	100	5.0	6.0