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

摘要：

目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.

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

所属期刊栏目：30

分类号：TP181(自动化基础理论)

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

在线出版日期：2009-04-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：1201-1203,1206