基于链表的不完备决策表属性约简算法  

Attribute Reduction Algorithm Based on Linked Lists under Incomplete Decision Tables

作　　者：陈炼[1] 吴灵芝[1] 

机构地区：[1]南昌大学计算中心,南昌330031

出　　处：《科学技术与工程》2015年第3期250-253,共4页Science Technology and Engineering

基　　金：国家自然科学基金(61262047);江西省科技支撑计划(20112BBE50039);江西省教育厅科学技术研究项目(GJJ14136)资助

摘　　要：差别矩阵作为决策信息系统属性约简的方法是有效的;但空间利用率不高。通过对算法空间利用率及时间效率进行研究,提出基于链表的改进算法;并引入链表的基本运算。该算法通过使用链表的节点存储基于限制容差关系下有效的差别矩阵元素,并在约简过程中通过不断删除不必要的节点以节省时间。通过理论与实例证明其有效性和正确性。Discernibility matrix as a method of attribute reduction in decision information system was efficient,but space efficiency is not high,Through studying on space and time efficiency,an improved algorithm is proposed based on linked list and also given the basic operation of linked list.The algorithm stored useful discernibility matrix elements under limited tolerance relation by linked list nodes,and also constantly deleted unnecessary nodes in the process of reduction to reduced time.Finally,theoretical analysis and a few examples show that this algorithm is effective and practical.

关 键 词：差别矩阵 空间利用率 链表 限制相容关系 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]