不確定圖P-TopK最小生成樹(shù)查詢(xún).pdf

1、圖的最小生成樹(shù)在網(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)的最小生成樹(shù)不能適用在某些應(yīng)用場(chǎng)景中。例如，無(wú)線傳感網(wǎng)絡(luò)中的通信鏈路存在斷鏈的可能，交通網(wǎng)絡(luò)中某些路段也存在一定的不通行概率，在這樣的圖數(shù)據(jù)巾獲得的最小生成樹(shù)通常也是不確定的。因此，基于不確定圖數(shù)據(jù)研究最小生成樹(shù)相關(guān)問(wèn)題具有重要的理論意義與應(yīng)用價(jià)值。

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

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

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

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