1、可达矩阵快速算法传递闭包Warshall方法计算可达矩阵简要介绍 在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的nn二值矩阵,则传递闭包的矩阵B+可如下计算: B+ = B + B2 + B3 + + (B)n 式中矩阵运算时所有乘法都用逻辑与代替,所有加法都用逻辑或代替。上式中的操作次序为B,B(B),B(BB),B(BBB),所以在运算的每一步我们只需简单地把现有结果乘以B,完成矩阵的n次乘法即可。 /ism/cal_warshall_get_r_
2、mat_detail.phpWarshall在1962年提出了一个求关系的传递闭包的有效算法。其具体过程如下,设在n个元素的有限集上关系R的关系矩阵为M:(1)置新矩阵A=M;(2)置k=1;(3)对所有i如果Ai,k=1,则对j=1.n执行:Ai,jAi,jAk,j;(4)k增1;(5)如果kn,则转到步骤(3),否则停止。所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。在离散数学中都提及了该算法。Warshall算法映射到有向图中设关系R的关系图为G,设图G的所有顶点为u1,u2,un,则t(R)的关系图可用该方法得到:若G中任意两顶点ui和uj之间有一条路径且没有ui到uj的弧,则在
3、图G中增加一条从ui到uj的弧,将这样改造后的图记为G,则G即为t(R)的关系图。G的邻接矩阵A应满足:若图G中存在从ui到uj路径,即ui与uj连通,则Ai,j=1,否则Ai,j=0。 这样,求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。相乘矩阵,就为所有节点的关系图,也就是当前条件下的关系矩阵。对于相乘矩阵,进行叠代,叠代的过程为,行取值,然后计算值中对应的每一行的值取并集,得到当前行的关系集合。取完所有行,得到了一个新的转移矩阵再对转移矩阵进行进行求解。Warshall的叠代次数比逐次平方法的运行效率要高。如果图中的顶点是有序的排列,只要进行一次Warshall运算就可以获得
4、可达矩阵。您输入原始矩阵 matrix_A 为一个方阵结果如下abcdefga11b11c1d1e1f1g1第 1 次迭代 当前0号要素 a 的可达集合(b,f,a ) 1号要素 b 的可达集合c,e,b 5号要素 f 的可达集合c,f 0号要素 a 的可达集合b,f,a 当前0号要素 a 的可达集合(b,f,a,c,e ) 当前1号要素 b 的可达集合(c,e,b ) 2号要素 c 的可达集合b,c 4号要素 e 的可达集合f,e 1号要素 b 的可达集合c,e,b 当前1号要素 b 的可达集合(c,e,b,f ) 当前2号要素 c 的可达集合(b,c ) 1号要素 b 的可达集合c,e,b
5、,f 2号要素 c 的可达集合b,c 当前2号要素 c 的可达集合(b,c,e,f ) 当前3号要素 d 的可达集合(a,d ) 0号要素 a 的可达集合b,f,a,c,e 3号要素 d 的可达集合a,d 当前3号要素 d 的可达集合(a,d,b,f,c,e ) 当前4号要素 e 的可达集合(f,e ) 5号要素 f 的可达集合c,f 4号要素 e 的可达集合f,e 当前4号要素 e 的可达集合(f,e,c ) 当前5号要素 f 的可达集合(c,f ) 2号要素 c 的可达集合b,c,e,f 5号要素 f 的可达集合c,f 当前5号要素 f 的可达集合(c,f,b,e ) 当前6号要素 g 的
6、可达集合(b,g ) 1号要素 b 的可达集合c,e,b,f 6号要素 g 的可达集合b,g 当前6号要素 g 的可达集合(b,g,c,e,f )第 1 次迭代 得到的转移矩阵如下:abcdefga11111b1111c1111d111111e111f1111g11111第 2 次迭代 当前0号要素 a 的可达集合(b,f,a,c,e ) 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 0号要素 a 的可达集合b,f,a,c,e 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c 当前0号要素 a 的可达集合(b,f,a,c,e ) 当前
7、1号要素 b 的可达集合(c,e,b,f ) 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 当前1号要素 b 的可达集合(c,e,b,f ) 当前2号要素 c 的可达集合(b,c,e,f ) 1号要素 b 的可达集合c,e,b,f 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c 5号要素 f 的可达集合c,f,b,e 当前2号要素 c 的可达集合(b,c,e,f ) 当前3号要素 d 的可达集合(a,d,b,f,c,e ) 0号要素 a 的可达集合b,f,a
8、,c,e 3号要素 d 的可达集合a,d,b,f,c,e 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c 当前3号要素 d 的可达集合(a,d,b,f,c,e ) 当前4号要素 e 的可达集合(f,e,c ) 5号要素 f 的可达集合c,f,b,e 4号要素 e 的可达集合f,e,c 2号要素 c 的可达集合b,c,e,f 当前4号要素 e 的可达集合(f,e,c,b ) 当前5号要素 f 的可达集合(c,f,b,e ) 2号要素 c 的可达集合b,c,e,f 5号要素 f 的可达集合c
9、,f,b,e 1号要素 b 的可达集合c,e,b,f 4号要素 e 的可达集合f,e,c,b 当前5号要素 f 的可达集合(c,f,b,e ) 当前6号要素 g 的可达集合(b,g,c,e,f ) 1号要素 b 的可达集合c,e,b,f 6号要素 g 的可达集合b,g,c,e,f 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 5号要素 f 的可达集合c,f,b,e 当前6号要素 g 的可达集合(b,g,c,e,f )第 2 次迭代 得到的转移矩阵如下:abcdefga11111b1111c1111d111111e1111f1111g11111第 3 次迭代 当
10、前0号要素 a 的可达集合(b,f,a,c,e ) 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 0号要素 a 的可达集合b,f,a,c,e 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 当前0号要素 a 的可达集合(b,f,a,c,e ) 当前1号要素 b 的可达集合(c,e,b,f ) 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 当前1号要素 b 的可达集合(c,e,b,f ) 当前2号要素 c 的可达集合(
11、b,c,e,f ) 1号要素 b 的可达集合c,e,b,f 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 5号要素 f 的可达集合c,f,b,e 当前2号要素 c 的可达集合(b,c,e,f ) 当前3号要素 d 的可达集合(a,d,b,f,c,e ) 0号要素 a 的可达集合b,f,a,c,e 3号要素 d 的可达集合a,d,b,f,c,e 1号要素 b 的可达集合c,e,b,f 5号要素 f 的可达集合c,f,b,e 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 当前3号要素 d 的可达集合(a,d,b,f,c,e ) 当
12、前4号要素 e 的可达集合(f,e,c,b ) 5号要素 f 的可达集合c,f,b,e 4号要素 e 的可达集合f,e,c,b 2号要素 c 的可达集合b,c,e,f 1号要素 b 的可达集合c,e,b,f 当前4号要素 e 的可达集合(f,e,c,b ) 当前5号要素 f 的可达集合(c,f,b,e ) 2号要素 c 的可达集合b,c,e,f 5号要素 f 的可达集合c,f,b,e 1号要素 b 的可达集合c,e,b,f 4号要素 e 的可达集合f,e,c,b 当前5号要素 f 的可达集合(c,f,b,e ) 当前6号要素 g 的可达集合(b,g,c,e,f ) 1号要素 b 的可达集合c,e,b,f 6号要素 g 的可达集合b,g,c,e,f 2号要素 c 的可达集合b,c,e,f 4号要素 e 的可达集合f,e,c,b 5号要素 f 的可达集合c,f,b,e 当前6号要素 g 的可达集合(b,g,c,e,f )第 3 次迭代 得到的转移矩阵如下:abcdefga11111b1111c1111d111111e1111f1111g11111
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2