利用Warshall转移闭包思想，快速迭代获得可达矩阵，详细步骤演示

返回首页

传递闭包Warshall方法简要介绍

　　① 在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的n×n二值矩阵，则传递闭包的矩阵B+可如下计算： B+ = B + B2 + B3 + ……+ (B)n

　　 ② 式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，……，所以在运算的每一步我们只需简单地把现有结果乘以B。

　　Warshall在1962年提出了一个求关系的传递闭包的有效算法。

　　其具体过程如下，设在n个元素的有限集上关系R的关系矩阵为M：
　　（1）置新矩阵A=M;
　　（2）置k=1;
　　（3）对所有i如果A[i,k]=1，则对j=1..n执行：
　　　　　A[i,j]←A[i,j]∨A[k,j];
　　（4）k增1;
　　（5）如果k≤n，则转到步骤（3），否则停止。
　　所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵。
　　在《离散数学》中都提及了该算法。

　　Warshall算法映射到有向图中

　　设关系R的关系图为G，设图G的所有顶点为u1,u2,…,un，则t(R)的关系图可用该方法得到：若G中任意两顶点ui和uj之间有一条路径且没有ui到uj的弧，则在图G中增加一条从ui到uj的弧，将这样改造后的图记为G’，则G’即为t(R)的关系图。G’的邻接矩阵A应满足：若图G中存在从ui到uj路径，即ui与uj连通，则A[i,j]=1，否则A[i,j]=0。

　　 这样，求t(R)的问题就变为求图G中每一对顶点间是否连通的问题。

　　相乘矩阵，就为所有节点的关系图，也就是当前条件下的关系矩阵。　

　　对于相乘矩阵，进行迭代，迭代的过程为，行取值，然后计算值中对应的每一行的值取并集，得到当前行的关系集合。

　　取完所有行，得到了一个新的转移矩阵再对转移矩阵进行进行求解。

　　本处获得可达矩阵的流程为：

　　(1) 设置求解矩阵

　　(2)判断求解出的转移矩阵是否跟求解矩阵一致，如果一致，则得到的矩阵为原始矩阵的可达矩阵，如果不一致进行 Warshall迭代求解。

　　假定矩阵为5*5的布尔矩阵，假定第一行A[0,0]=1,A[0,1]=1,A[0,2]=1,A[0,3]=1,A[0,4]=1,

　　Warshall迭代求解过程第一行的值如下：A0=A[0]∨A[1]∨A[2]∨A[3]∨A[4]。

　　其它行同理。

　　快速迭代函数的代码量非常少，同时如果数据结构合理，一次集合运算的运算量非常的小。

　　Warshall的迭代次数比逐次平方法的运行效率要高很多。如果图中的顶点是有序的排列，只要进行一次Warshall快速迭代运算就可以获得可达矩阵。因此要更快的获得可达矩阵，可以先对图进行排序。

　　目前的通过多次快速迭代求可达矩阵，其效率也是非常的差的，它还不是一个线性算法，在已经研究的方法中通过Gabow算法先获得回路列表，根据回路列表进行传递闭包的快速迭代是最快的。具体步骤请看。

显示的是一个随机 12 * 12 的方阵