基于求传递闭包的Warshall算法的改进 被引量：16

1

作者 刘任任 陈建二 陈松乔 《计算机工程》 CAS CSCD 北大核心 2005年第19期38-39,48,共3页

围绕传递闭包分析比较了著名的Warshall算法,给出了一个三角形算法。当关系矩阵是稀疏矩阵时,该算法比Warshall快。

关键词 二元关系 传递闭包 WARSHALL算法

在线阅读 下载PDF 职称材料

CP-nets的完备性及一致性研究 被引量：7

2

作者 刘惊雷 廖士中 张伟 《软件学报》 EI CSCD 北大核心 2012年第6期1531-1541,共11页

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-net... CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-nets上的强占优运算研究CP-nets的完备性和一致性.首先,通过构造CP-nets导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall算法求出可判断任意CP-nets的强占优;其次,通过求取3种不同结构(可分离的、链表结构和树形结构)的CP-nets的偏好个数,给出了CP-nets可表达的偏好的不完备性定理,并给出了可分离的CP-nets中偏好的计数公式;最后,研究CP-nets的一致性,给出了CP-nets的一致性判定定理及其算法.所做工作不仅解决了Boutilier和Goldsmith提出的一些难题,还深化了CP-nets的基础理论研究. 展开更多

关键词 强占优 偏好的完备性 偏好的一致性 翻转关系的传递闭包 可分离的条件偏好网 判定定理及算法

在线阅读 下载PDF 职称材料

在RDBMS上扩充传递闭包功能的方法和算法 被引量：1

3

作者 徐宏炳 陈钢 王能斌 《计算机研究与发展》 EI CSCD 北大核心 1997年第10期795-800,共6页

目前的ＲＤＢＭＳ一般不支持传递闭包计算功能．为扩充此功能，作者提出了在原ＲＤＢＭＳ上增加传递闭包处理层ＳＥＴＣＳ，以及扩充传递闭包定义与查询语句的ＳＱＬ＊．该方案已在ＯＲＡＣＬＥ上实现并投入应用．

关键词 关系数据库 传递闭包 增量自救 RDBMS 数据库

在线阅读 下载PDF 职称材料

传递闭包的增量式更新研究 被引量：2

4

作者 汪小燕 杨思春 +1 位作者 叶红 周建平 《苏州科技学院学报（自然科学版）》 CAS 2015年第1期45-48,共4页

针对二元关系中添加序偶原有传递闭包更新问题,先提出一种新的传递闭包算法,并基于新的传递闭包算法给出传递闭包的增量式更新方法,只需要在原有传递闭包的基础上,根据所添加的不同序偶,进行简单的更新即可,利用该方法可以较快地实现动... 针对二元关系中添加序偶原有传递闭包更新问题,先提出一种新的传递闭包算法,并基于新的传递闭包算法给出传递闭包的增量式更新方法,只需要在原有传递闭包的基础上,根据所添加的不同序偶,进行简单的更新即可,利用该方法可以较快地实现动态变化的二元关系传递闭包的求解。 展开更多

关键词 二元关系 传递闭包 恒等关系 增量 更新

在线阅读 下载PDF 职称材料

稀疏矩阵情况下Warshall算法的改进 被引量：3

5

作者 张世龙 沈玉利 《计算机工程与应用》 CSCD 北大核心 2008年第28期60-61,151,共3页

围绕二元关系的传递闭包分析比较了著名的Warshall算法,给出了一个加列算法。当关系矩阵是稀疏矩阵时,该算法效率比Warshall算法高。

关键词 二元关系 传递闭包 WARSHALL算法 加列算法

在线阅读 下载PDF 职称材料

基于λ-Warshall算法的聚类方法 被引量：1

6

作者 李刚 刘宏兵 冯岩 《计算机工程与设计》 CSCD 北大核心 2008年第8期1903-1904,1909,共3页

根据数据之间的相似性,提出了一种基于改进Warshall算法的数据聚类方法。该方法在传统Warshall算法的基础上,引入聚类因子,构造模糊相似关系的传递闭包。由于相似性的自反性与对称性,该传递闭包就是模糊相似关系的等价闭包,把等价数据... 根据数据之间的相似性,提出了一种基于改进Warshall算法的数据聚类方法。该方法在传统Warshall算法的基础上,引入聚类因子,构造模糊相似关系的传递闭包。由于相似性的自反性与对称性,该传递闭包就是模糊相似关系的等价闭包,把等价数据分到一类形成聚类。实验结果表明,该方法可得到与传统的K-均值聚类算法相同的聚类结果。 展开更多

关键词 模糊关系 模糊关系矩阵 WARSHALL算法 λ-Warshall算法 聚类 传递闭包

在线阅读 下载PDF 职称材料

模糊关系矩阵传递闭包的Warshall算法 被引量：13

7

作者 刘贵龙 《模糊系统与数学》 CSCD 2003年第1期59-61,共3页

通过对照关系的传递闭包和模糊关系的传递闭包,把求关系矩阵的传递闭包的算法完整地推广到模糊关系矩阵上。

关键词 传递闭包 模糊关系矩阵 算法

在线阅读 下载PDF 职称材料

Fuzzy关系矩阵传递闭包的截矩阵-Warshall算法 被引量：1

8

作者 刘龙章 杨志辉 《模糊系统与数学》 CSCD 北大核心 2008年第1期50-53,共4页

根据模糊矩阵的截矩阵性质,提出了利用截矩阵求模糊关系矩阵传递闭包的一种新算法。

关键词 截矩阵 传递闭包 模糊关系矩阵 算法

在线阅读 下载PDF 职称材料

基于删除序偶的传递闭包求解算法 被引量：1

9

作者 张世龙 沈玉利 《计算机工程与设计》 CSCD 北大核心 2009年第8期1907-1909,1913,共4页

针对在已有传递闭包的基础上删除序偶后的传递闭包求解问题,提出一种基于传递闭包的传递闭包动态求解算法,给出了其形式化描述形式,并给出了算法的详细证明过程。该算法在已有的传递闭包基础上,通过把新删除序偶及该序偶的所有依赖间接... 针对在已有传递闭包的基础上删除序偶后的传递闭包求解问题,提出一种基于传递闭包的传递闭包动态求解算法,给出了其形式化描述形式,并给出了算法的详细证明过程。该算法在已有的传递闭包基础上,通过把新删除序偶及该序偶的所有依赖间接指向序偶从已有传递闭包中删除实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程。 展开更多

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

在线阅读 下载PDF 职称材料

二元关系传递闭包的求法及与图的可达矩阵的关系 被引量：2

10

作者 郭键 师鸣若 辛向丽 《黔南民族师范学院学报》 2008年第6期45-47,86,共4页

分析了几种求解二元关系传递闭包方法的特点,并利用二元关系传递闭包与有向图的可达性矩阵之间的关系,实现了采用Warshall算法对可达性矩阵的求取,简化了计算可达性矩阵的算法.

关键词 二元关系 传递闭包 可达性矩阵 WARSHALL算法

在线阅读 下载PDF 职称材料

关系传递闭包计算的补充 被引量：2

11

作者 张京良 《曲阜师范大学学报（自然科学版）》 CAS 2002年第3期41-43,共3页

设X是一n元集 ,R是X上的一个二元关系 ,该文给出了R中序偶链及其链长的定义 ,并据此找到了一个准确的k≤n使得t(R) =∪ki=1 Ri。

关键词 二元关系 传递闭包 WARSHALL算法 关系逻辑 序偶链 计算方法 集合

在线阅读 下载PDF 职称材料

Warshall算法在判别传递性与求传递闭包中的应用

12

作者 孙凤芝 李映红 +1 位作者 程霜梅 祁彦平 《长春大学学报》 2007年第6期13-16,共4页

通过对warshall算法的研究,通过其关系矩阵判别关系传递性的方法及求传递闭包的方法,使得对可传递关系的研究变得简洁而又高效。

关键词 二元关系 传递性 传递闭包 WARSHALL算法

在线阅读 下载PDF 职称材料

在Word上轻松实现Warshajj算法

13

作者 吕洪升 《巢湖学院学报》 2014年第6期19-23,共5页

用Matlab处理数学课堂教学中数据,复杂的计算变得轻而易举,再用其中notebook编辑教案,就能在文字处理软件Word平台上直接计算,并能根据需要显示或隐藏计算结果,还能调用Matlab的许多功能而无需掌握该语言设计体系。

关键词 Warshajj算法 二元关系 传递闭包

在线阅读 下载PDF 职称材料

关于传递闭包算法的探讨

14

作者 陈中标 《科技信息》 2009年第7期200-201,共2页

分别用定义、得到的推论、Warshall算法以及关系图来计算各类关系的传递闭包,给传递闭包的计算带来了参考和方便。

关键词 传递闭包 关系矩阵 WARSHALL算法 C语言 关系图

在线阅读 下载PDF 职称材料

模糊关系的不动点及在计算传递闭包中的应用

15

作者 陈贻源 王忠山 刘正林 《华中理工大学学报》 CSCD 北大核心 1994年第8期49-53,共5页

给出了模糊关系的不动点定义，以及找不动点的一些方法，阐述了不动点通路的性质。利用不动点及不动点通路的性质，改进了模糊关系传递闭包的计算方法。

关键词 模糊不动点 模糊关系图 传递闭包

在线阅读 下载PDF 职称材料

Warshall算法之证明及若干应用

16

作者 张豪煜 《中国纺织大学学报》 CSCD 1989年第1期38-43,共6页

本文给出了 Warshall 算法的一个正确性证明,不仅简明,而且极有利于对 Warshall 算法本身的理解。对于自动编译程序构造中的基本问题之一,求非终极符所对应的终极符串的带头符(FIRST)和后继符(FOLLOW)集,本文还介绍了基于 Warshall 算... 本文给出了 Warshall 算法的一个正确性证明,不仅简明,而且极有利于对 Warshall 算法本身的理解。对于自动编译程序构造中的基本问题之一,求非终极符所对应的终极符串的带头符(FIRST)和后继符(FOLLOW)集,本文还介绍了基于 Warshall 算法的计算办法。 展开更多

关键词 WARSHALL算法 编译程序 非终极符

在线阅读 下载PDF 职称材料