詹婉荣，于 海

(洛阳师范学院 数学科学学院, 河南 洛阳 471934)

粗糙集理论是波兰数学家Pawlak于1982年提出的，它是一种新型的处理模糊和不确定知识的数学工具，其主要思想就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则[1]. 属性约简是粗糙集理论中的核心内容之一.数据库中的属性并不是同等重要的, 甚至其中某些知识是冗余的，通过属性约简, 可以去除数据库中的冗余、无用的成分, 揭示数据中隐含的规律.从粗糙集理论的角度来理解, 在一个信息系统中, 有些属性对于分类来说是多余的, 去掉这些属性后，信息系统的分类能力不会改变, 所以属性约简后仍然反映了一个信息系统的本质信息[2-6].一般来讲，一个信息系统的属性约简不是唯一的，通常人们希望能够找到一个属性个数最小的属性约简，该属性约简称为最小属性约简.对任一给定信息系统，若属性约简算法能确保找到其最小属性约简，则该算法称为最小属性约简的完备算法.

然而，Wong和Zlarko已经证明了寻找一个信息系统的最小约简是NP-hard 问题[7].导致NP-hard 问题的主要原因是属性的组合爆炸问题.传统的属性约简算法大都属于启发式的搜索算法，它们的优点是易于实现，且计算速度快，但求出的不一定是最小属性约简.因此在本文中，我们将最小属性约简问题转化为一个优化问题，进而转化为0-1规划.通过求解该0-1规划，得到了信息系统的最小属性约简……