| 基于新增序偶的传递闭包求解算法 |
| |
| 引用本文： | 张世龙,唐雅娜,邹阿金.基于新增序偶的传递闭包求解算法[J].仲恺农业工程学院学报,2014,27(2):23-26. |
| |
| 作者姓名： | 张世龙 唐雅娜 邹阿金 |
| |
| 作者单位： | 1仲恺农业工程学院信息科学与技术学院2广东海洋大学信息学院 |
| |
| 基金项目： | 广东省自然科学基金(S2012010009976);广东省科技计划(2011B040200074);湛江市科技攻关计划(2011C3105001)资助项目 |
| |
| 摘 要： | 针对在已有传递闭包的基础上新增序偶后的传递闭包求解问题,提出了一种基于新增序偶的传递闭包求解算法,并给出了详细证明过程.该算法在已有的传递闭包基础上,通过把新增序偶及该序偶的所有派生间接指向序偶添加到已有的传递闭包中实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程.
|
| 关 键 词： | 传递闭包 新增序偶 二元关系 时间复杂度 |
A transitive closure solution algorithm based on new ordered couples |
| |
| ZHANG Shilong;TANG Yana;ZOU Ajin.A transitive closure solution algorithm based on new ordered couples[J].Journal of Zhongkai University of Agriculture and Technology,2014,27(2):23-26. |
| |
| Authors: | ZHANG Shilong;TANG Yana;ZOU Ajin |
| |
| Institution: | ZHANG Shilong;TANG Yana;ZOU Ajin;College of Information Science and Technology,Zhongkai University of Agriculture and Engineering;Information College,Guangdong Ocean University; |
| |
| Abstract: | A transitive closure solution algorithm based on new ordered couples was proposed , which aimed to solve transitive closure problems after adding new ordered couples to current transitive closure . The demonstration process was provided as well .In order to solve the problem , the new ordered couples and all the derivatives indirectly pointed to the ordered couples were added to the existing transitive clo -sure.Thus, the time complexity of the algorithm can be reduced to O （n^2）, while the algorithm will not be affected by sparse matrix or chain length of ordered couple chain .Finally, an example was given to il-lustrate the execution of the algorithm . |
| |
| Keywords: | transitive closure new ordered couples binary relation time complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《仲恺农业工程学院学报》浏览原始摘要信息 |
| 点击此处可从《仲恺农业工程学院学报》下载免费的PDF全文 |
