不確定圖中的生成樹算法研究.pdf

1、圖論作為數(shù)學(xué)的一個重要分支，在計算機(jī)科學(xué)中也扮演著非常重要的角色。隨著大數(shù)據(jù)時代的到來，圖數(shù)據(jù)的規(guī)模也隨之增大，因此圖算法的效率對于解決圖論問題至關(guān)重要。由于現(xiàn)實問題中可能會遇到很多的意外情況，如機(jī)器故障，信號傳輸?shù)牟环€(wěn)定性等，最終導(dǎo)致實際數(shù)據(jù)存在不確定性。因此不確定圖已經(jīng)成為一個非常熱門的研究領(lǐng)域。
　　本研究主要內(nèi)容包括：⑴由于不確定圖的邊存在不確定性，所以傳統(tǒng)的最小生成樹定義已經(jīng)不能完全適用于不確定圖。因此提出了最優(yōu)生成樹的

2、概念，它主要是在最小生成樹定義的基礎(chǔ)上增加了對概率的最優(yōu)化定義。然后我們借助貪心的思想設(shè)計了不確定圖中最優(yōu)生成樹算法。⑵為了能夠找到不確定圖中的所有關(guān)鍵邊，我們設(shè)計了Top-K最小生成樹算法，并提出了基于并查集的優(yōu)化算法和基于啟發(fā)式搜索的優(yōu)化算法。當(dāng)K值較小時，基于啟發(fā)式搜索的優(yōu)化算法具有明顯的優(yōu)勢。⑶對最小生成樹在不確定圖中的可靠性進(jìn)行了分析。將可靠性定義為所有包含最小生成樹的蘊含圖的存在概率之和，主要使用了邊集劃分的方法將所有蘊含圖