可达矩阵的四种求解方法:自乘,幂乘,Warshall转移闭包法、一次性Warshall法



~
计算方式
优缺点
自乘法

第一步:求出自乘矩阵

第二步:相乘矩阵,乘以相乘矩阵,就是进行布尔积(Boolean Product)⊙运算

第三步:自乘矩阵一直乘下去。

最后:得到的矩阵不再变化时,该矩阵就叫可达矩阵。

优点:数学表达式简单,好理解。通常计算都是用这种方法,大部分教科书也是用的这种方法。

缺点:运算慢。矩阵的布尔积运算次数多!

幂乘法

第一步:求出自乘矩阵

第二步:相乘矩阵,乘以相乘矩阵,就是进行布尔积(Boolean Product)⊙运算

第三步:得到的矩阵称之为幂矩阵,幂矩阵再相乘,一直这样平方下去。

最后:得到的矩阵不再变化时,该矩阵就叫可达矩阵。

优点:数学表达式简单,好理解。

缺点:运算慢。矩阵的布尔积运算次数多!

另外一个由于幂矩阵中的为1的值相对较多。其实际运算速度不一定就比自乘法快,虽然其,矩阵乘法运算次数相对于自乘法要少!
Warshall法

第一步:求出自乘矩阵

第二步:相乘矩阵,得到转移矩阵。

第三步:转移矩阵的相对于自乘矩阵的转移矩阵,一直循环。

最后:得到的矩阵不再变化时,该矩阵就叫可达矩阵。

优点:运算速度中等。

缺点:稍微有点难理解!

改进Warshall法

第一步:求出自乘矩阵

第二步:相乘矩阵,得到转移矩阵。

第三步:转移矩阵的转移矩阵,一直循环。

最后:得到的矩阵不再变化时,该矩阵就叫可达矩阵。

优点:运算速度中等。

缺点:稍微有点难理解!

一次性Warshall法

第一步:根据原始矩阵求出所有的强连通分量

第二步:根据强连通分量得到的是一个良好拓扑排序的矩阵

第三步:从上到下,进行一次Warshall运算就得到了可达矩阵。

优点:运算速度得到数量级的提高。

缺点:难理解!

在矩阵对角线下一个对角线上全部输入1,只要一次Wallshall就可以得出可达矩阵!



可达矩阵如下



$$R=\begin{array} {c|c|c|c|c|c|c|c}{M_{8 \times8}} &E1 &E2 &E3 &E4 &E5 &E6 &E7 &E8\\ \hline E1 &1 & &1 &1 & &1 &1 &1\\ \hline E2 & &1 &1 &1 &1 &1 & &1\\ \hline E3 & & &1 &1 & &1 & &1\\ \hline E4 & & &1 &1 & &1 & &1\\ \hline E5 & &1 &1 &1 &1 &1 & &1\\ \hline E6 & & &1 &1 & &1 & &1\\ \hline E7 & & &1 &1 & &1 &1 &1\\ \hline E8 & & &1 &1 & &1 & &1\\ \hline \end{array} $$

矩阵的表示形式



   E1E2E3E4E5E6E7E8
E1                1 1   
E2             1         
E3                1      
E4       1               
E5    1          1      
E6                      1
E7                1      
E8          1            

矩阵的表示形式



原始矩阵 可达矩阵
   E1E2E3E4E5E6E7E8
E1                1 1   
E2             1         
E3                1      
E4       1               
E5    1          1      
E6                      1
E7                1      
E8          1            
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1

可达矩阵的求解,其中其中快速(迭代)Warshall的转移闭包与逼近的可达矩阵的速度最快


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
2
   E1E2E3E4E5E6E7E8
E1 1             1 1 1
E2    1       1 1      
E3       1       1    1
E4       1 1    1      
E5    1       1 1    1
E6          1    1    1
E7                1 1 1
E8       1 1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1 1
E2    1       1 1      
E3       1       1    1
E4       1 1    1      
E5    1       1 1    1
E6          1    1    1
E7                1 1 1
E8       1 1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1 1
E2    1       1 1      
E3       1       1    1
E4       1 1    1    1
E5    1       1 1    1
E6          1    1    1
E7          1    1 1 1
E8       1 1    1    1
3
   E1E2E3E4E5E6E7E8
E1 1       1    1 1 1
E2    1       1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1    1 1 1    1
E6       1 1    1    1
E7          1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1    1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1    1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
4
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1    1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
5
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1
6
   E1E2E3E4E5E6E7E8
E1 1    1 1    1 1 1
E2    1 1 1 1 1    1
E3       1 1    1    1
E4       1 1    1    1
E5    1 1 1 1 1    1
E6       1 1    1    1
E7       1 1    1 1 1
E8       1 1    1    1

逐次平法法进行布尔乘积的次数虽然要少于自乘的方式,但是由于中间矩阵中值为1的个数更多,所以整个获得可达矩阵的时间效率上来说,它不一定快,甚至更慢!,只有改进为集合求解方式,其效率会大大加快


下图为它们的可达集合标记法,链表标识方式


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
E1 E1、E6、E7、
E2 E2、E5、
E3 E3、E6、
E4 E3、E4、
E5 E2、E5、E6、
E6 E6、E8、
E7 E6、E7、
E8 E4、E8、
E1 E1、E6、E7、
E2 E2、E5、
E3 E3、E6、
E4 E3、E4、
E5 E2、E5、E6、
E6 E6、E8、
E7 E6、E7、
E8 E4、E8、
E1 E1、E6、E7、
E2 E2、E5、
E3 E3、E6、
E4 E3、E4、
E5 E2、E5、E6、
E6 E6、E8、
E7 E6、E7、
E8 E4、E8、
2
E1 E1、E6、E7、E8、
E2 E2、E5、E6、
E3 E3、E6、E8、
E4 E3、E4、E6、
E5 E2、E5、E6、E8、
E6 E4、E6、E8、
E7 E6、E7、E8、
E8 E3、E4、E8、
E1 E1、E6、E7、E8、
E2 E2、E5、E6、
E3 E3、E6、E8、
E4 E3、E4、E6、
E5 E2、E5、E6、E8、
E6 E4、E6、E8、
E7 E6、E7、E8、
E8 E3、E4、E8、
E1 E1、E6、E7、E8、
E2 E2、E5、E6、
E3 E3、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E5、E6、E8、
E6 E4、E6、E8、
E7 E4、E6、E7、E8、
E8 E3、E4、E6、E8、
3
E1 E1、E4、E6、E7、E8、
E2 E2、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
4
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
5
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、
6
E1 E1、E3、E4、E6、E7、E8、
E2 E2、E3、E4、E5、E6、E8、
E3 E3、E4、E6、E8、
E4 E3、E4、E6、E8、
E5 E2、E3、E4、E5、E6、E8、
E6 E3、E4、E6、E8、
E7 E3、E4、E6、E7、E8、
E8 E3、E4、E6、E8、

比较求解过程中每一步矩阵值与上一个矩阵的变化



矩阵相乘的次数 相乘矩阵自乘的方法 逐次平方法 快速转移法,Warshall快速转移
1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
   E1E2E3E4E5E6E7E8
E1 1             1 1   
E2    1       1         
E3       1       1      
E4       1 1            
E5    1       1 1      
E6                1    1
E7                1 1   
E8          1          1
2
E1 E2 E3 E4 E5 E6 E7 E8
E1 1         111
E2   1     11    
E3     1     1   1
E4     11   1    
E5   1     11   1
E6       1   1   1
E7           111
E8     1 1       1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1         111
E2   1     11    
E3     1     1   1
E4     11   1    
E5   1     11   1
E6       1   1   1
E7           111
E8     1 1       1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1         111
E2   1     11    
E3     1     1   1
E4     11   1   1
E5   1     11   1
E6       1   1   1
E7       1   111
E8     1 1   1   1
3
E1 E2 E3 E4 E5 E6 E7 E8
E1 1     1   111
E2   1     11   1
E3     11   1   1
E4     11   1   1
E5   1   1 11   1
E6     1 1   1   1
E7       1   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   1 1   111
E2   1   1 11   1
E3     11   1   1
E4     11   1   1
E5   11 1 11   1
E6     1 1   1   1
E7     1 1   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   1 1   111
E2   1   1 11   1
E3     11   1   1
E4     11   1   1
E5   11 1 11   1
E6     1 1   1   1
E7     1 1   111
E8     11   1   1
4
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   1 1   111
E2   1   1 11   1
E3     11   1   1
E4     11   1   1
E5   11 111   1
E6     11   1   1
E7     1 1   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11 111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11 111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1
5
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11 111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1
6
E1 E2 E3 E4 E5 E6 E7 E8
E1 1   11   111
E2   11111   1
E3     11   1   1
E4     11   1   1
E5   11111   1
E6     11   1   1
E7     11   111
E8     11   1   1

化学加平台
解释结构模型
感谢化学加提供单独服务器服务器!请大家多支持化学加平台,可以多介绍人关注化学加!
对解释结构模型在线计算有什么意见与建议请发电子邮件到, hwstu #sohu.com 把#替换成 @