一种基于决策表约简的集覆盖问题的近似解法

集覆盖问题和决策信息表的约简问题分别是优化领域和信息处理领域重要的研究课题,但目前的研究大都针对这两个问题分别独立展开.通过分析集覆盖问题的解结构和决策信息表的布尔约简结构,将两者联系起来探讨.首先,给出一个集覆盖问题的布尔矩阵表示,并通过添加决策属性,对集覆盖中的集合进行分类,进一步诱导出一个以该布尔矩阵为条件属性值的决策信息表.其次,分析了决策表和集覆盖的辨识集之间的关系,证明了集覆盖问题的一个局部最优解恰好是该决策表的一个属性约简,即,求解集覆盖问题可等价地转化为求解决策表的属性约简问题.然后,利用决策表中的条件熵来度量集覆盖中一个集合在集族中的相对重要度,并构造了基于条件熵的集覆盖问题的近似算法.最后,运用实例验证了该算法的有效性和可行性,并将新算法与几个传统集覆盖算法进行了对比.实验结果表明,新算法在求得满意解上具有一定的优势.