可达矩阵快速算法.docx

可达矩阵快速算法.docx

《可达矩阵快速算法.docx》由会员分享，可在线阅读，更多相关《可达矩阵快速算法.docx（7页珍藏版）》请在冰点文库上搜索。

可达矩阵快速算法

传递闭包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，完成矩阵的n次乘法即可。

/ism/cal_warshall_get_r_mat_detail.php

　　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中每一对顶点间是否连通的问题。

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

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

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

　　Warshall的叠代次数比逐次平方法的运行效率要高。

如果图中的顶点是有序的排列，只要进行一次Warshall运算就可以获得可达矩阵。

您输入原始矩阵matrix_A为一个方阵结果如下

a

b

c

d

e

f

g

a

1

1

b

1

1

c

1

d

1

e

1

f

1

g

1

第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，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的可达集合（b，g）

      1号要素b的可达集合c，e，b，f 

      6号要素g的可达集合b，g 

     当前6号要素g的可达集合（b，g，c，e，f）

第1次迭代得到的转移矩阵如下：

a

b

c

d

e

f

g

a

1

1

1

1

1

b

1

1

1

1

c

1

1

1

1

d

1

1

1

1

1

1

e

1

1

1

f

1

1

1

1

g

1

1

1

1

1

第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）

     当前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，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，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次迭代得到的转移矩阵如下：

a

b

c

d

e

f

g

a

1

1

1

1

1

b

1

1

1

1

c

1

1

1

1

d

1

1

1

1

1

1

e

1

1

1

1

f

1

1

1

1

g

1

1

1

1

1

第3次迭代 

     当前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的可达集合（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）

     当前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次迭代得到的转移矩阵如下：

a

b

c

d

e

f

g

a

1

1

1

1

1

b

1

1

1

1

c

1

1

1

1

d

1

1

1

1

1

1

e

1

1

1

1

f

1

1

1

1

g

1

1

1

1

1