不確定圖P-TopK最小生成樹查詢.pdf

1、圖的最小生成樹在網(wǎng)絡設計，VLSI以及道路交通建設等領域中有著重要的應用價值。在現(xiàn)實應用中，隨著系統(tǒng)復雜性的提高，不確定性數(shù)據(jù)頻繁出現(xiàn)在各種領域中。當圖數(shù)據(jù)中存在不確定性因素時，傳統(tǒng)的最小生成樹不能適用在某些應用場景中。例如，無線傳感網(wǎng)絡中的通信鏈路存在斷鏈的可能，交通網(wǎng)絡中某些路段也存在一定的不通行概率，在這樣的圖數(shù)據(jù)巾獲得的最小生成樹通常也是不確定的。因此，基于不確定圖數(shù)據(jù)研究最小生成樹相關問題具有重要的理論意義與應用價值。

2、　　本文面向圖結構不確定的圖數(shù)據(jù)研究最小生成樹查詢相關問題。具體地，圖的任意邊的邊權是一個二元組(W,P)，其中W表示邊的代價權，P表示邊存在的概率，W在邊存在時有效，在該不確定圖上快速查詢P-TopK最小生成樹是本文的研究目標。
　　本文首先提出了基于多維分組組合過濾的查詢算法(CA_MG)來解決該問題。CA_MG算法是在現(xiàn)有的動態(tài)組合過濾算法(CA_Dyn)的基礎上改進的，針對CA_Dyn中對組合分組過多而導致過濾性能差的特點

3、，提出了多維分組的概念，并給出了一種基于多維分組過濾的策略。此外，考慮到算法中對所有組合判樹以及計算最小生成樹概率這兩個過程時間消耗較大，于是提出了一種基于環(huán)匹配的優(yōu)化策略，該策略預處理出圖中所有環(huán)并對環(huán)建立索引，使得上述兩個過程可以簡化為在索引上匹配環(huán)的過程。實驗表明，CA_MG算法在現(xiàn)有的基于組合過濾的算法中，具有最好的性能，加入環(huán)匹配優(yōu)化的CA_MG算法也有相應的性能提升。
　　事實上，所有基于組合過濾的查詢算法都存在因為組

4、合數(shù)量較多而導致查詢性能偏低的特點。CA_Dyn和CA_MG雖然通過對組合進行分組而過濾掉了一部分組合，但組合的局部有序性仍然使得過濾能力受限?；谝陨戏治?，本文提出了基于上界樹過濾的查詢算法(FA_KMUBT)。具體地，首先給出了最大上界樹以及K大上界樹的概念及其計算方法，然后提出了在若干棵全局有序的上界樹中查詢P-TopK最小生成樹的方法，該方法由于候選空間較小，具有較強的過濾能力。實驗表明，F(xiàn)A_KMUBT在所有算法中具有最高的查

5、詢性能。
　　考慮到該問題的計算規(guī)模較大，本文在CA_MG算法的基礎上提出了一種簡單但有效的并行查詢P-TopK最小生成樹的方案。在該方案中，首先提出了組合劃分的概念，在進一步分析了多維分組的性質(zhì)之后，提出了一個基于多維分組的組合劃分算法，可以有效地將組合空間劃分成近似均勻的若干分區(qū)。通過將每個分區(qū)交由不同的處理機并行計算，然后匯總所有分區(qū)的局部計算結果得到最終查詢結果。實驗表明，并行的CA_MG算法由于相對均勻的數(shù)據(jù)劃分和較小的