传递闭包的两种算法实现及比较

2024-07-08 23:23| 来源: 网络整理| 查看: 265

传递闭包的两种算法比较 1. 传递闭包的定义法[^1]1.1. 原理分析1.2. 伪代码1.3. 时间复杂度1.4. Matlab代码 2. 沃舍尔算法2.1. 原理分析2.2. 伪代码2.3. 时间复杂度2.4. 源码 3. 总结4. Reference

假设 R R R是定义在集合 A A A上的二元关系， S S S是 R R R的传递闭包. Input：二元关系 R R R的矩阵形式 M R M_R MROutput: R R R对应的传递闭包 S S S. 1. 传递闭包的定义法1 1.1. 原理分析

由传递闭包的定义可得 R i ⊂ S R^i\subset S Ri⊂S(这里的幂指数 i i i表示 i i i个二元关系的合成), 则有

S = ⋃ i = 1 ∞ R i (1) S=\bigcup_{i=1}^{\infty}R^i\tag{1} S=i=1⋃∞Ri(1)

我们对 ( 1 ) (1) (1)式继续进行分析，优化可得 S = ⋃ i = 1 n R i n是集合A的基数 (2) S=\bigcup_{i=1}^nR^i\qquad\text{n是集合A的基数}\tag{2} S=i=1⋃nRin是集合A的基数(2)

证明：

设 ( x , y ) ∈ S (x,y)\in S (x,y)∈S,则必存在一个最小的正整数 p p p使得 ( x , y ) ∈ R p (x,y)\in R^p (x,y)∈Rp，这就是说存在一个序列 x , a 1 , a 2 , a 3 , ⋯ , a p − 1 , y x,a_1,a_2,a_3,⋯,a_{p−1},y x,a1,a2,a3,⋯,ap−1,y使得 ( x , a 1 ) ∈ R , ( a 1 , a 2 ) ∈ R , ( a 2 , a 3 ) ∈ R , ⋯ ， ( a p − 1 , y ) ∈ R (x,a_1 )\in R,\ (a_1,a_2 )\in R,\ (a_2,a_3 )\in R,\cdots，(a_{p−1},y)\in R (x,a1)∈R, (a1,a2)∈R, (a2,a3)∈R,⋯，(ap−1,y)∈R,那么 a 1 a_1 a1 到 a p − 1 a_{p−1} ap−1必须互不相同且不同于 x x x和 y y y，否则关系复合的链条就会缩短，从而与 p p p的最小性矛盾因此 p p p的最大可能值出现在 x = y x=y x=y,而 p − 1 = n − 1 p−1=n−1 p−1=n−1,故得证 p ≤ n p\le n p≤n,即 S = ⋃ i = 1 n R i S=\bigcup\limits_{i=1}^nR^i S=i=1⋃nRi⁡

( 2 ) (2) (2)式用矩阵的形式表示为

M s = M R ∨ M R [ 2 ] ∨ M R [ 3 ] ⋯ ∨ M R [ n ] (3) M_s=M_R\lor M_R^{[2]}\lor M_R^{[3]}\cdots\lor M_{R}^{[n]}\tag{3} Ms=MR∨MR[2]∨MR[3]⋯∨MR[n](3) 其中, M R [ i ] M_R^{[i]} MR[i]表示 i i i个 0 − 1 0-1 0−1矩阵 M R M_R MR的布尔积

1.2. 伪代码 procedure transitive closure A:=M_R S:=A for i:=2 to n A:=A*M_R;(这里的*表示逻辑积) S:=S V A return S 1.3. 时间复杂度最后一步需要算 n − 1 n-1 n−1个 M R [ i ] M_R^{[i]} MR[i]的并，计算每一个并运算需要使用 n 2 n^2 n2次并运算计算布尔幂 M R [ i ] M_R^{[i]} MR[i]需要求出 n − 1 n-1 n−1个 n × n n\times n n×n矩阵的布尔积。计算每个布尔积需要使用 n 2 ( 2 n − 1 ) n^2(2n-1) n2(2n−1)次位运算。因此此步共需要 n 2 ( 2 n − 1 ) ( n − 1 ) n^2(2n-1)(n-1) n2(2n−1)(n−1)次位运算总共需要 n 2 ( 2 n − 1 ) ( n − 1 ) + ( n − 1 ) n 2 = 2 n 3 ( n − 1 ) n^2(2n-1)(n-1)+(n-1)n^2=2n^3(n-1) n2(2n−1)(n−1)+(n−1)n2=2n3(n−1)，即该算法的时间复杂度为 O ( n 4 ) O(n^4) O(n4) 1.4. Matlab代码

注：Matlab可以进行向量化运算，因此实际运行时间会小于 O ( n 4 ) O(n^4) O(n4)

% main function function Ms=closure(Mr) % get the size of Matrix inputed n=size(Mr); temp=zeros(n); Ms=Mr; % init Mrk=Mr; for k=2:n for i=1:n for j=1:n % vectorize to speed up a little temp(i,j)=log_sum(Mrk(i, : )&Mrk(: ,j)'); end end Mrk=temp; Ms=Ms|Mrk; end end function ls=log_sum(t) nn=length(t); ls=t(1); for i=2:nn ls=ls|t(i); end end 2. 沃舍尔算法

这个算法能够高效地计算某个二元关系的传递闭包

2.1. 原理分析其基础是构造一系列的 0 − 1 0-1 0−1矩阵。这些矩阵是 W 0 , W 1 , W 2 , ⋯ , W n W_0,W_1,W_2,\cdots,W_n W0,W1,W2,⋯,Wn，其中 W 0 = M r W_0=M_r W0=Mr,且 W k = [ w i j ( k ) ] W_k=[w_{ij}^{(k)}] Wk=[wij(k)]（此处类似于迭代）。 A = { v 1 , v 2 , ⋯ , v n } A=\{v_1,v_2,\cdots,v_n\} A={v1,v2,⋯,vn}。如果存在一条从 v i v_i vi到 v j v_j vj的路径使得这条路径的内点在集合 A A A内（就是找到一个点 v k v_k vk使得 w i k = 1 w_{ik}=1 wik=1且 w k j = 1 w_{kj}=1 wkj=1，即存在路径 v i → v k → v j v_i\rightarrow v_k\rightarrow v_j vi→vk→vj,有点类似与Floyd算法），则记 w i j ( k ) = 1 w_{ij}^{(k)}=1 wij(k)=1 W n W_n Wn就是所要求的 S S S以上是大致的思路。补充一个引理：

设 W k = [ w i j ( k ) ] W_k=[w_{ij}^{(k)}] Wk=[wij(k)]是 0 − 1 0-1 0−1矩阵，它在 ( i , j ) (i,j) (i,j)位置处取1当且仅当存在一条从 v i v_{i} vi到 v j v_{j} vj的路径，其内部顶点取值集合 A A A,数学语言描述为

w i j ( k ) = w i j ( k − 1 ) ∨ ( w i k ( k − 1 ) ∧ w k j ( k − 1 ) ) w_{ij}^{(k)}=w_{ij}^{(k-1)}\lor(w_{ik}^{(k-1)}\land w_{kj}^{(k-1)}) wij(k)=wij(k−1)∨(wik(k−1)∧wkj(k−1)) 且有 i , j , k ≤ n i,j,k\le n i,j,k≤n

2.2. 伪代码 procedure Warshall W:=M_R B:=A for k:=1 to n for i:=1 to n for j:=1 to n w_{ij}=w_{ij}|(w_{ik}&w_{kj}) return W 2.3. 时间复杂度求出一项 w i j ( k ) w_{ij}^{(k)} wij(k)需要两次位运算，从 W k − 1 W_{k-1} Wk−1计算 W k W_{k} Wk需要 2 n 2 2n^2 2n2次运算从 W 0 W_0 W0计算出 W 1 , W 2 W_1,W_2 W1,W2一直到 W n W_n Wn需要 n n n次运算则共需 2 n 2 × n = 2 n 3 2n^2\times n=2n^3 2n2×n=2n3次运算，时间的复杂度 O ( n 3 ) O(n^3) O(n3) 2.4. 源码 % main function function W=Warshall(Mr) % get the size of Matrix inputed n=size(Mr); temp=0; W=Mr; % init for k=1:n for i=1:n for j=1:n temp=W(i,j)|(W(i,k)&W(k,j)); W(i,j)=temp; end end end 3. 总结就串行运算的话，第二种算法的时间复杂度比第一种低一个量级，算法高效但是第一种算法可以进行并行处理，会大大提高速度 4. Reference

离散数学及其应用_第七版。ROSEN著.徐六通等译 ↩︎

【本文地址】

传递闭包的两种算法实现及比较

传递闭包的两种算法实现及比较

今日新闻

推荐新闻