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

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

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

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

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