什么是沃舍爾算法

用來(lái)計(jì)算關(guān)系的傳遞閉包的一種高效率算法，

專注于為中小企業(yè)提供做網(wǎng)站、成都做網(wǎng)站服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)管城免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了千余家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

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

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

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

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

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

2. 接著是沃舍爾算法，這個(gè)算法比前面的標(biāo)準(zhǔn)算法復(fù)雜度上少了一階。沃舍爾算法使用了一條路徑的“內(nèi)點(diǎn)”的概念。即如a，b，c，.....，x樣的一條路徑，除去a和x之外的所有端點(diǎn)稱為這條路徑的內(nèi)點(diǎn)。

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

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

總結(jié)來(lái)說(shuō)，標(biāo)準(zhǔn)算法是通過(guò)n階布爾冪來(lái)化簡(jiǎn)多重傳遞，并在過(guò)程中進(jìn)行了矩陣合并的運(yùn)算以保證所有路徑都被保留；而沃舍爾算法在每階矩陣的每個(gè)元素上，最多只進(jìn)行2次布爾運(yùn)算就可以取代標(biāo)準(zhǔn)算法的一個(gè)復(fù)雜度為O(n)的矩陣運(yùn)算，因此效率得以提升。

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

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

如圖所示