二元关系传递闭包的Warshall算法及应用

介绍了传递闭包的 Warshall算法 ,从布尔矩阵运算的角度论证该算法的正确性 ,并讨论 Warshall算法在语法分析中的应用技术和用改进 Warshall算法求有向图的距离矩阵     

关于构造关系传递闭包的三个算法

在本文中,阐明了如何由给定结点集上的二元关系来构造其关系传递闭包并给出三个有关的算法。 第一个是改进了的Warshall算法,当用计算机实现时,它可比原Warshall算法节省许多时间和空间。 第二个是排序算法,本文指出:结点的排序对所有使用布尔矩阵的算法的运算效率有严重影响,而此排序算法将给出结点的合理排序,它将进一步提高Warshall算法以及上述算法的效率。 我们还提出了第三个算法,它适用于结点数少于30左右的情况,此算法中使用了一个简单图解方法,它可直接从给定的关系图中得出传递闭包。     

Warshall算法之证明及若干应用

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

Warshall算法的C语言实现

Warshall算法是求二元关系传递闭包的一种高效的算法.通过对二元关系可传递性的研究,给出Warshall算法的一个C语言程序,使对可传递性的研究变得更加直观和有效.     

Warshall算法在传递性判别中的应用

Warshall算法是用于求传递闭包的有效方法,通过对Warshall算法的深入研究,对其进行了引申,给出判别传递性的定理,并对其进行了证明和应用,使得对可传递关系的判别变得非常简洁、高效。     

关于传递闭包算法的探讨

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

有限集上二元关系传递性的矩阵判别法

通过对二元关系的关系矩阵元素特征的观察和对Warshall算法的深入研究,得出了3种判断有限集上的二元关系是否具备传递性的矩阵判别法：逻辑相加判别法、逻辑乘方比较判别法、打圈画叉判别法．     

基于Dijkstra算法和Floyd算法的物流运输最短路径研究

对于物流公司或企业来说,往往会遇到配送物流时需要送至两个甚至更多的地方,在已有的这种客观条件下,如何使得系统的费用最低,服务效果最好,是配送的核心问题。本文通过利用Dijkstra的两种改进算法和Warshall－Floyd算法来对配送的最小路径进行寻优,比较了三种算法的优化效率和可靠性,结果发现改进的DDkstn算法和warshall－Floyd算法具有较好的搜索效率。     

从Warshall算法到求模糊矩阵传递闭包的一个简捷算法

模糊矩阵传递闭包的计算在模糊聚类中起着关键的作用,而模糊矩阵传递闭包与普通集合论中传递闭包是有密切联系的。从普通集合论中求关系闭包的Warshall算法和模糊关系图出发,论述并实现了一种求模糊矩阵传递闭包的有效算法。与经典的求模糊矩阵传递闭包的算法———平方法比较,该算法简捷,运算量小。最后分析了一个利用传递闭包法进行模糊聚类的实例。     

Fuzzy聚类分析法在楼盘分类中的应用

基于传统的Fuzzy等价关系聚类法,由Fuzzy相似矩阵构建Fuzzy等价矩阵,对传递闭包采用Warshall算法求解,并选择不同置信水平下的分类,利用偏差度得到最优聚类.结合北京市朝阳区近3个月新开楼盘的数据,选择可靠性指标,在最佳置信水平的基础上对其进行最优聚类,实验结果与事实吻合.     

一种基于UML活动图的工作流模式描述与验证方式

随着工作流技术应用的越来越广泛,对于工作流技术的要求也越来越高。而工作流模型的好坏对于整个工作流管理系统性能来说意义重大。在这里,引入了UML活动图来对工作流模式进行描述,并提出图论中的邻接矩阵和Warshall算法来进行验证的方法,这为开发健壮的、合理的大型工作流系统提供了很好的描述方法与验证方式。     

关于Warshall的关系R之传递闭包t(R)求法的一点注记

本文给出了求二元关系R的传递闭包t(R)的一种方法,它是从另一侧面对Warshall于1962年给出的方法的一个补充和完善。     

关于《离散数学》中两个问题的注

1 传递闭包的Warshall算法的矩阵证明本节只讨论有限集X={x_1,…,x_n}上的二元关系R.M_R=[m_(ij)]_(nxn)表示尺的关系矩阵,用G_R表示R的关系图.[1]指出不易从M_R或G_R判断R是否是传递关系.由[2],我们有如下命题1.1 设R是有限集X={x_1,…,x_n}上的二元关系.R是传递的,当且仅当下述条件之一成立:     

求传递闭包R~+的Warshall法的一种并行计算

Warshall法是求关系R的传递闭包R~+的有效方法,我们用有向森林的方法给出Warshall法的一种并行计算。具体步骤是,先构造一个有向图,用结点表示对于R的行的逻辑加法运算,用有向边表示后一结点在计算过程中所需用到的前一结点的结果,证明了这样构造的有向图是一个有向森林。并行计算是以两个定理的形式给出的。定理1指出在最短的时间内完成求R~+计算所需的计算器台数。定理2指出如果计算器的台数已事先给定,则完成求R~+计算所需的最短时间是多少。整个工作建立在把求R~+的计算归结为对上述有向森林进行计算的基础上。     

用分层关联方法求简单图中所有Hamilton回路的算法

研究简单图中所有的Ham ilton回路,不但可以判断简单图是否Ham ilton图,并且还可以得到简单图的所有的Ham ilton回路。首先在简单图中建立了初级通路的关联关系,并对初级通路的关联关系进行了分层,在此基础上,设计了求简单图中所有Ham ilton回路的算法。该算法利用简单图中长度为x的初级通路及长度为x的初级通路的分层关联关系逐步求长度为x 1的初级通路及长度为x 1的初级通路的分层关联关系的方法,求得简单图的所有Ham ilton回路。通过理论证明,该算法与已有的求简单图的所有Ham ilton回路的算法相比,原有的求简单图的所有Ham ilton回路算法中大量的重复计算被避免,从而提高了算法的效率。     

浅析网络层的路由选择算法

本文就路由选择算法中的默认路由(含静态路由)和两种简单的动态路由算法作一简单分析。     

基于LS算法的MIMO-OFDM频率同步

频率同步是MIMO-OFDM同步技术必须解决的问题之一,但是传统的基于ML算法的频率偏移估计条件要求苛刻,计算复杂,因此对CFO简单算法的探究势在必行。为此提出一种基于LS算法的频率偏移估计,并将其性能与基于ML的频率偏移估计的性能进行比较。仿真结果表明,LS算法性能等同于ML算法性能。基于LS算法的简单性和使用条件的低约束性,可使用LS算法获得和ML算法相同的频偏估计。     

一种分割平面简单多边形的高效算法

简单多边形的分割问题是图形图像处理过程中的一个基本问题,已有的算法复杂度高且实现繁琐.利用链表这种简单的数据结构实现的新算法,其时间复杂度为,空间复杂度是,减少了计算开销,提高了运算速度.通过实际软件应用表明该算法实现简单,且高效、准确,因而有很好的实用性.     

基于FPGA的CORDIC算法研究

CORDIC（TheCoordinateRotationalDigitalComputer）算法是将复杂的数学函数化成简单的加法和移位操作,因此被广泛应用到数字信号处理算法的硬件实现中。基于CORDIC算法的流水线型的正／余弦运算电路具有精度高、误差小、电路结构简单等特点。     

基于MapReduce的Apriori算法并行化

Apriori是挖掘关联规则最经典的算法之一,针对该算法存在的瓶颈问题研究了基于MapReduce编程框架的简单Apriori并行算法;并在简单Apriori并行算法的基础上提出一种采用固定多阶段结合挖掘策略的改进算法——多阶段并行算法。实验结果表明,改进算法能缩短挖掘时间,提高执行的效率。