可达矩阵的四种求解方法:自乘,幂乘,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_{12 \times12}} &子 &丑 &寅 &卯 &辰 &巳 &午 &未 &申 &酉 &戌 &亥\\ \hline 子 &1 & &1 &1 &1 &1 &1 &1 & &1 &1 &1\\ \hline 丑 &1 &1 &1 &1 &1 &1 &1 &1 & &1 &1 &1\\ \hline 寅 &1 & &1 &1 &1 &1 &1 &1 & &1 &1 &1\\ \hline 卯 & & & &1 &1 & &1 &1 & & &1 & \\ \hline 辰 & & & & &1 & & & & & &1 & \\ \hline 巳 & & & & &1 &1 & & & & &1 & \\ \hline 午 & & & & &1 & &1 & & & &1 & \\ \hline 未 & & & & &1 & &1 &1 & & &1 & \\ \hline 申 &1 & &1 &1 &1 &1 &1 &1 &1 &1 &1 &1\\ \hline 酉 &1 & &1 &1 &1 &1 &1 &1 & &1 &1 &1\\ \hline 戌 & & & & &1 & & & & & &1 & \\ \hline 亥 &1 & &1 &1 &1 &1 &1 &1 & &1 &1 &1\\ \hline \end{array} $$

矩阵的表示形式



  
                                 1
                                 1
         1                1      
                     1            
                              1   
                              1   
                              1   
                  1               
1                                 
1             1                  
            1                     
      1                           

矩阵的表示形式



原始矩阵 可达矩阵
  
                                 1
                                 1
         1                1      
                     1            
                              1   
                              1   
                              1   
                  1               
1                                 
1             1                  
            1                     
      1                           
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1

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


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
2
  
1    1                         1
   1 1                         1
1    1 1    1    1    1      
         1       1 1            
            1                1   
            1 1             1   
            1    1          1   
                  1 1       1   
1                      1       1
1             1          1 1 1
            1                1   
      1 1                1    1
  
1    1                         1
   1 1                         1
1    1 1    1    1    1      
         1       1 1            
            1                1   
            1 1             1   
            1    1          1   
                  1 1       1   
1                      1       1
1             1          1 1 1
            1                1   
      1 1                1    1
  
1    1                         1
   1 1                         1
1    1 1    1    1    1      
         1       1 1            
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1                1       1
1    1    1 1          1 1 1
            1                1   
1    1 1    1    1    1    1
3
  
1    1 1                1    1
   1 1 1                1    1
1    1 1    1 1 1    1 1 1
         1       1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1                1       1
1    1    1 1          1 1 1
            1                1   
1    1 1    1    1    1    1
  
1    1 1    1    1    1    1
1 1 1 1    1    1    1    1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1             1 1    1
1    1 1 1 1          1 1 1
            1                1   
1    1 1    1 1 1    1 1 1
  
1    1 1    1    1    1    1
1 1 1 1    1    1    1    1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
4
  
1    1 1    1    1    1    1
1 1 1 1    1    1    1    1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1             1 1    1
1    1 1 1 1          1 1 1
            1                1   
1    1 1    1 1 1    1 1 1
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
5
  
1    1 1    1 1 1    1 1 1
1 1 1 1    1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1    1    1 1 1    1
1    1 1 1 1    1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
6
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1    1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
7
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1
8
  
1    1 1 1 1 1 1    1 1 1
1 1 1 1 1 1 1 1    1 1 1
1    1 1 1 1 1 1    1 1 1
         1 1    1 1       1   
            1                1   
            1 1             1   
            1    1          1   
            1    1 1       1   
1    1 1 1 1 1 1 1 1 1 1
1    1 1 1 1 1 1    1 1 1
            1                1   
1    1 1 1 1 1 1    1 1 1

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


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


矩阵相乘的次数 相乘矩阵自乘的方法 幂乘的方法 快速Warshall转移法
1
子、亥、
丑、亥、
寅、卯、酉、
卯、未、
辰、戌、
巳、戌、
午、戌、
午、未、
子、申、
子、巳、酉、
辰、戌、
寅、亥、
子、亥、
丑、亥、
寅、卯、酉、
卯、未、
辰、戌、
巳、戌、
午、戌、
午、未、
子、申、
子、巳、酉、
辰、戌、
寅、亥、
子、亥、
丑、亥、
寅、卯、酉、
卯、未、
辰、戌、
巳、戌、
午、戌、
午、未、
子、申、
子、巳、酉、
辰、戌、
寅、亥、
2
子、寅、亥、
丑、寅、亥、
子、寅、卯、巳、未、酉、
卯、午、未、
辰、戌、
辰、巳、戌、
辰、午、戌、
午、未、戌、
子、申、亥、
子、巳、酉、戌、亥、
辰、戌、
寅、卯、酉、亥、
子、寅、亥、
丑、寅、亥、
子、寅、卯、巳、未、酉、
卯、午、未、
辰、戌、
辰、巳、戌、
辰、午、戌、
午、未、戌、
子、申、亥、
子、巳、酉、戌、亥、
辰、戌、
寅、卯、酉、亥、
子、寅、亥、
丑、寅、亥、
子、寅、卯、巳、未、酉、
卯、午、未、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、申、亥、
子、寅、辰、巳、酉、戌、亥、
辰、戌、
子、寅、卯、巳、未、酉、亥、
3
子、寅、卯、酉、亥、
丑、寅、卯、酉、亥、
子、寅、卯、巳、午、未、酉、戌、亥、
卯、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、申、亥、
子、寅、辰、巳、酉、戌、亥、
辰、戌、
子、寅、卯、巳、未、酉、亥、
子、寅、卯、巳、未、酉、亥、
子、丑、寅、卯、巳、未、酉、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、申、酉、亥、
子、寅、卯、辰、巳、酉、戌、亥、
辰、戌、
子、寅、卯、巳、午、未、酉、戌、亥、
子、寅、卯、巳、未、酉、亥、
子、丑、寅、卯、巳、未、酉、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
4
子、寅、卯、巳、未、酉、亥、
子、丑、寅、卯、巳、未、酉、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、申、酉、亥、
子、寅、卯、辰、巳、酉、戌、亥、
辰、戌、
子、寅、卯、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
5
子、寅、卯、巳、午、未、酉、戌、亥、
子、丑、寅、卯、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、巳、未、申、酉、亥、
子、寅、卯、辰、巳、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
6
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
7
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
8
子、寅、卯、辰、巳、午、未、酉、戌、亥、
子、丑、寅、卯、辰、巳、午、未、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
卯、辰、午、未、戌、
辰、戌、
辰、巳、戌、
辰、午、戌、
辰、午、未、戌、
子、寅、卯、辰、巳、午、未、申、酉、戌、亥、
子、寅、卯、辰、巳、午、未、酉、戌、亥、
辰、戌、
子、寅、卯、辰、巳、午、未、酉、戌、亥、

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



矩阵相乘的次数 相乘矩阵自乘的方法 逐次平方法 快速转移法,Warshall快速转移
1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
  
1                               1
   1                            1
      1 1                1      
         1          1            
            1                1   
               1             1   
                  1          1   
                  1 1            
1                      1         
1             1          1      
            1                1   
      1                         1
2
1   1                 1
  11                 1
1   11   1   1   1    
      1     1 1        
        1           1  
        1 1         1  
        1   1       1  
            11     1  
1               1     1
1         1       11 1
        1           1  
    11           1   1
1   1                 1
  11                 1
1   11   1   1   1    
      1     1 1        
        1           1  
        1 1         1  
        1   1       1  
            11     1  
1               1     1
1         1       11 1
        1           1  
    11           1   1
1   1                 1
  11                 1
1   11   1   1   1    
      1     1 1        
        1           1  
        1 1         1  
        1   1       1  
        1   11     1  
1   1           1     1
1   1   1 1       11 1
        1           1  
1   11   1   1   1   1
3
1   11           1   1
  111           1   1
1   11   11 1   11 1
      1     11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1           1     1
1   1   1 1       111
        1           1  
1   11   1   1   1   1
1   11   1   1   1   1
1 111   1   1   1   1
1   111 11 1   11 1
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1 1         11   1
1   1 1 1 1       111
        1           1  
1   11   1 1 1   11 1
1   11   1   1   1   1
1 111   1   1   1   1
1   111 11 1   11 1
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   11 1 1 1 1 11 1 1
1   11 111 1   111
        1           1  
1   111 11 1   11 1
4
1   11   1   1   1   1
1 111   1   1   1   1
1   111 111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   11         11   1
1   11 11       111
        1           1  
1   11   11 1   11 1
1   111 11 1   11 1
11111 11 1   11 1
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   111 1 1 1 111 1
1   11111 1   111
        1           1  
1   111 111   111
1   111 11 1   11 1
11111 11 1   11 1
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1111111111
1   111111   111
        1           1  
1   111111   111
5
1   11   11 1   11 1
1111   11 1   11 1
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   11   1   1 11   1
1   1111   1   111
        1           1  
1   111 111   111
1   111111   111
11111111   111
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1111111111
1   111111   111
        1           1  
1   111111   111
1   111111   111
11111111   111
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1111111111
1   111111   111
        1           1  
1   111111   111
6
1   111 111   111
11111 111   111
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   11   11 1111 1
1   11111 1   111
        1           1  
1   111111   111
7
1   111111   111
11111111   111
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   111 1111111
1   111111   111
        1           1  
1   111111   111
8
1   111111   111
11111111   111
1   111111   111
      11   11     1  
        1           1  
        11         1  
        1   1       1  
        1   11     1  
1   1111111111
1   111111   111
        1           1  
1   111111   111

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