Abstract: This paper points out the defect of old algorithm for reduction based on discernibility matrix. Through improving discernibility matrix and the method of measuring attribute significance, a complete heuristic algorithm for optimal reduction based on the absorption law in discernibility matrix is introduced, effectively reducing the space complexity of the algorithms for reduction based on discernibility matrix. Experimental result indicates the reduction got by new algorithm is the same to the approach of discernibility matrix and functions. This conclusion illuminates the new algorithm is valid and complete.

Key words: discernibility matrix, optimal reduction, complete algorithm

摘要： 指出现有差别矩阵属性约简算法的不足，对原有差别矩阵和属性重要性度量方法进行改进，运用差别矩阵元素项的重要性质，提出一种新的启发式约简完备算法，有效地降低差别矩阵约简算法的空间复杂度。仿真实验结果显示，新算法产生的约简与分辨函数思想产生的最优约简一致，表明了新算法的有效性与完备性。

关键词: 差别矩阵, 最优约简, 完备算法

CLC Number: 

• TP311