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

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