基于可分辨矩阵的快速求核算法  

Quick computing core algorithm based on discernibility matrix

作　　者：葛浩[1,2] 杨传健[3] 李龙澍[2] 

机构地区：[1]滁州学院电子信息工程系,安徽滁州239012 [2]安徽大学计算机学院,安徽合肥230039 [3]滁州学院计算机系,安徽滁州239012

出　　处：《计算机工程与设计》2009年第5期1201-1203,1206,共4页Computer Engineering and Design

基　　金：安徽省自然科学基金项目(O50420204);安徽高校省级自然科学研究基金项目(KJ2008B117)。

摘　　要：目前求核算法存在以下不足:求得的核与基于正区域的核不一致、算法的时间和空间复杂度不理想。针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的。为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(│C││U)。在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(│C││U/C│2,O(C││U)}和O(│C││U/C│2)。最后,实例说明了算法的有效性。At present, the algorithms for computing core have the following shortcomings： the core acquired from these algorithms is not the core based on positive region. The time complexity and space complexity of these algorithms are not good. Aiming at these problems, firstly a definition of simple dicernibility matrix and the method of computing core are provided. It is proved that the core is equivalent to the core based on positive region. In order to improve the efficiency of the algorithm, an efficient algorithm for computing U/C is designed with the idea of radix sorting based on distributing counting. It＇ s time complexity is O（｜ C｜ ｜U｜）. On this condition, a quick computing core algorithm is put forward. Its time complexity and space complexity are cut down max{O（│C││U/C│^2,O（C││U）} and O（│C││U/C│^2） .Finally, an example is used to explained the efficiency of the algorithm.

关 键 词：粗糙集 等价类 正区域 可分辨矩阵 核 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]