一个基于正区域的快速求核算法  

Quick algorithm for computing core based on the positive region

作　　者：徐章艳[1] 杨炳儒[2] 蔡卫东[2] 崔巍[3] 谷冬元[3] 

机构地区：[1]广西师范大学计算机系,广西桂林541004 [2]北京科技大学信息工程学院,北京100083 [3]北京科技大学管理学院,北京100083

出　　处：《系统工程与电子技术》2006年第12期1902-1905,1931,共5页Systems Engineering and Electronics

基　　金：国家科技成果重点推广计划(2003EC000001)资助课题

摘　　要：现有利用差别矩阵设计的基于正区域的求核算法,其时间复杂度为O(|C‖U|2)。为降低求核算法的时间复杂度,给出了简化差别矩阵的定义和基于简化差别矩阵核的定义,并证明了该核与基于正区域的核是等价的。由于求简化差别矩阵的关键是求划分U/C,故利用基数排序的思想设计了一个快速求划分U/C的算法,其时间复杂度为O(|C‖U|)。在此基础上,利用简化差别矩阵设计了一个基于正区域的快速求核算法,其时间复杂度降为max{O(|C‖U|),O(|C‖U/C‖Up′os)}。实例说明了新算法的有效性。Some scholars provided the discernibility matrix based on the positive region. The time complexity of the algorithm for computing core with this discernibility matrix is O（｜C｜｜U｜^2）. For cuting down the time complexity of the algorithm for computing core, the definition of simplified discernibility matrix based on the positive region and the corresponding definition of the core are provided. At the same time, it is proved that this core is equivalent to the core based on the positive region. Since the partition of U/C is the key process for computing simplified discernibility matrix, a quick algorithm for computing U/C is designed with the idea of radix sorting. Its time complexity is O（[C II uI ）. On this condition, a new algorithm for computing core based on the positive region is designed with the simplified discernibility matrix. Its time complexity is cut down to max{O（｜ C｜｜U｜）,O（｜C｜｜U/C｜｜U′pvs｜）}.

关 键 词：粗糙集 正区域 简化差别矩阵 核 复杂度 

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