沃舍爾算法如何從m0算到m1

1. 首先是從定義出發(fā)的標準算法，若要求出包含關系R的最小的傳遞閉包，我們就要為R中的每一種可能傳遞的關系補完其可傳遞性。不同于自反和對稱閉包，傳遞的復雜之處在于，他是可以有多重傳遞的，這就造成了初次補完R以后，新添加的關系有可能會和原有的關系一起產(chǎn)生新的傳遞關系（路徑），這時候就需要二次補完。同樣的道理，三次、四次...直到n次（n為R的頂點數(shù)）以后。

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務領域包括：網(wǎng)站設計、成都網(wǎng)站建設、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務，滿足客戶于互聯(lián)網(wǎng)時代的扶風網(wǎng)站設計、移動媒體設計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡建設合作伙伴！

如上描述，求傳遞閉包的標準方法就是依次求出1、2、3...、n階傳遞關系并在每階求完之后與前一階的矩陣聯(lián)合，再進行下一階的求解。具體的操作方法是對原矩陣MR（圖7-11右）進行布爾冪運算。我們可以看到——MR[k] 的值mij正好是其前一階，即MR[k-1] 的i行j列（或者說，頂點i和頂點j之間）傳遞關系存在與否的解。（難理解的話可以親手算一算）

沃舍爾算法的路徑和矩陣描述

2. 接著是沃舍爾算法，這個算法比前面的標準算法復雜度上少了一階。沃舍爾算法使用了一條路徑的“內點”的概念。即如a，b，c，.....，x樣的一條路徑，除去a和x之外的所有端點稱為這條路徑的內點。

具體的操作方法是以R為開頭構造一系列（n個）矩陣，他們是W0 ,W1,W2,W3,W4 .....，其中W0= MR。這看起來和標準算法差不多，但是沃舍爾算法的高階矩陣的值并不是由前一階的布爾冪運算得來。而是這樣定義的：Wk=[wij[k]]，如果存在一條從vi到vj的路徑且這條路徑的所有內點都在集合{v1，v2，....，vk}（表中的前k個頂點）內，那么wij[k]=1，否則為0.（注意有兩個合取的條件）

可以看到，因為Wk-1中的“1”也必然滿足于Wk，所以Wk-1中的“1”可以直接繼承到Wk之中，即wij[k-1]=1→wij[k]=1。而對于Wk-1中的0，從前段的定義中我們可以看到，對于wij[k-1]為0，而wij[k]為1的情況，當且僅當wik[k-1]=1且wkj[k-1]=1。（或者使用路徑的說法——存在一條從vi到vk和一條從vk到vj的路徑，使得當內點集合擴大到vk時才滿足了前段定義的第二條條件）注意這里的下標k，不再泛指k≤n的正整數(shù)，而是實指當前正在運算的Wk的k。舉圖7-11的例子來說明，W1的w24[1]的值應該是w21[0]*w14[0]=1，而在W0中這個位置的值是0.

總結來說，標準算法是通過n階布爾冪來化簡多重傳遞，并在過程中進行了矩陣合并的運算以保證所有路徑都被保留；而沃舍爾算法在每階矩陣的每個元素上，最多只進行2次布爾運算就可以取代標準算法的一個復雜度為O(n)的矩陣運算，因此效率得以提升。

離散數(shù)學沃舍爾算法怎么運算？

沃舍爾算法，得名于沃舍爾，他于1960年給出此算法。該算法能夠有效的計算關系的傳遞閉包。沃舍爾算法只需要使用2n^3次位運算就可以求出傳遞閉包。

如圖所示

什么是沃舍爾算法

用來計算關系的傳遞閉包的一種高效率算法，

比如說要求出n元素集合上關系的傳遞閉包使用2n3(n-1)次位運算，用沃舍爾算法只用2n3次位運算就可以求出