基于删除序偶的传递闭包求解算法  

Transitive closure algorithm based on deleted ordered couple

作　　者：张世龙[1] 沈玉利[1] 

机构地区：[1]广东海洋大学信息学院

出　　处：《计算机工程与设计》2009年第8期1907-1909,1913,共4页Computer Engineering and Design

基　　金：粤港重大突破招标基金项目(2006A25007002);国家星火基金项目(2007EA780068)

摘　　要：针对在已有传递闭包的基础上删除序偶后的传递闭包求解问题,提出一种基于传递闭包的传递闭包动态求解算法,给出了其形式化描述形式,并给出了算法的详细证明过程。该算法在已有的传递闭包基础上,通过把新删除序偶及该序偶的所有依赖间接指向序偶从已有传递闭包中删除实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程。Aiming at the problem of transitive closure based on present transitive closure and deleted ordered couple, a dynamic algorithm of transitive closure based on present transitive closure is proposed and designed, and is proven in detail, the formal description of the algorithm is also given. In order to get the new transitive closure, the new deleted ordered couple and all dependency indirection ordered couple are deleted from the present transitive closure, so that the time complexity of the algorithm is reduced to O （n^2）, and isn＇t affected by uncertain factors, such as sparse matrix and the length of ordered couple chain. Finally, an example is given to account for the execution of the algorithm.

关 键 词：二元关系 传递闭包 删除序偶 时间复杂度 动态算法 

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