可达矩阵的四种求解方法:自乘,幂乘,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}} &B1 &B2 &B3 &B4 &B5 &B6 &B7 &B8\\ \hline B1 &1 &1 & &1 & & &1 &1\\ \hline B2 &1 &1 & &1 & & &1 &1\\ \hline B3 &1 &1 &1 &1 &1 &1 &1 &1\\ \hline B4 & & & &1 & & & &1\\ \hline B5 &1 &1 & &1 &1 & &1 &1\\ \hline B6 &1 &1 & &1 &1 &1 &1 &1\\ \hline B7 &1 &1 & &1 & & &1 &1\\ \hline B8 & & & & & & & &1\\ \hline \end{array} $$

矩阵的表示形式



   B1B2B3B4B5B6B7B8
B1                   1   
B2 1                     
B3                1      
B4                      1
B5    1                  
B6 1          1         
B7    1    1            
B8                        

矩阵的表示形式



原始矩阵 可达矩阵
   B1B2B3B4B5B6B7B8
B1                   1   
B2 1                     
B3                1      
B4                      1
B5    1                  
B6 1          1         
B7    1    1            
B8                        
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1

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


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
2
   B1B2B3B4B5B6B7B8
B1 1 1    1       1   
B2 1 1             1   
B3 1    1    1 1      
B4          1          1
B5 1 1       1         
B6 1 1       1 1 1   
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1   
B2 1 1             1   
B3 1    1    1 1      
B4          1          1
B5 1 1       1         
B6 1 1       1 1 1   
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1   
B2 1 1    1       1   
B3 1    1    1 1      
B4          1          1
B5 1 1    1 1    1   
B6 1 1    1 1 1 1   
B7 1 1    1       1 1
B8                      1
3
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1   
B3 1 1 1    1 1 1   
B4          1          1
B5 1 1       1    1   
B6 1 1    1 1 1 1   
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1   
B4          1          1
B5 1 1    1 1    1   
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
4
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1   
B4          1          1
B5 1 1    1 1    1   
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
5
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1
6
   B1B2B3B4B5B6B7B8
B1 1 1    1       1 1
B2 1 1    1       1 1
B3 1 1 1 1 1 1 1 1
B4          1          1
B5 1 1    1 1    1 1
B6 1 1    1 1 1 1 1
B7 1 1    1       1 1
B8                      1

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


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


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
B1 B1、B7、
B2 B1、B2、
B3 B3、B6、
B4 B4、B8、
B5 B2、B5、
B6 B1、B5、B6、
B7 B2、B4、B7、
B8 B8、
B1 B1、B7、
B2 B1、B2、
B3 B3、B6、
B4 B4、B8、
B5 B2、B5、
B6 B1、B5、B6、
B7 B2、B4、B7、
B8 B8、
B1 B1、B7、
B2 B1、B2、
B3 B3、B6、
B4 B4、B8、
B5 B2、B5、
B6 B1、B5、B6、
B7 B2、B4、B7、
B8 B8、
2
B1 B1、B2、B4、B7、
B2 B1、B2、B7、
B3 B1、B3、B5、B6、
B4 B4、B8、
B5 B1、B2、B5、
B6 B1、B2、B5、B6、B7、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、
B2 B1、B2、B7、
B3 B1、B3、B5、B6、
B4 B4、B8、
B5 B1、B2、B5、
B6 B1、B2、B5、B6、B7、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、
B2 B1、B2、B4、B7、
B3 B1、B3、B5、B6、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、
B6 B1、B2、B4、B5、B6、B7、
B7 B1、B2、B4、B7、B8、
B8 B8、
3
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、
B3 B1、B2、B3、B5、B6、B7、
B4 B4、B8、
B5 B1、B2、B5、B7、
B6 B1、B2、B4、B5、B6、B7、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
4
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
5
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、
6
B1 B1、B2、B4、B7、B8、
B2 B1、B2、B4、B7、B8、
B3 B1、B2、B3、B4、B5、B6、B7、B8、
B4 B4、B8、
B5 B1、B2、B4、B5、B7、B8、
B6 B1、B2、B4、B5、B6、B7、B8、
B7 B1、B2、B4、B7、B8、
B8 B8、

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



矩阵相乘的次数 相乘矩阵自乘的方法 逐次平方法 快速转移法,Warshall快速转移
1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
   B1B2B3B4B5B6B7B8
B1 1                1   
B2 1 1                  
B3       1       1      
B4          1          1
B5    1       1         
B6 1          1 1      
B7    1    1       1   
B8                      1
2
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     1  
B2 11         1  
B3 1   1   1 1    
B4       1       1
B5 1 1     1      
B6 11     111  
B7 1 1   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     1  
B2 11         1  
B3 1   1   1 1    
B4       1       1
B5 1 1     1      
B6 11     111  
B7 1 1   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     1  
B2 11   1     1  
B3 1   1   1 1    
B4       1       1
B5 1 1   1 1   1  
B6 11   1 111  
B7 1 1   1     11
B8               1
3
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     1  
B3 11 1   111  
B4       1       1
B5 11     1   1  
B6 11   1 111  
B7 11   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11 11 111  
B4       1       1
B5 11   1 1   1  
B6 11   1 1111
B7 11   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11 11 111 1
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1
4
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 1111 111  
B4       1       1
B5 11   1 1   1  
B6 11   11111
B7 11   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11111111
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11111111
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1
5
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11111111
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11111111
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1
6
B1 B2 B3 B4 B5 B6 B7 B8
B1 11   1     11
B2 11   1     11
B3 11111111
B4       1       1
B5 11   11   11
B6 11   11111
B7 11   1     11
B8               1

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