不確定圖中的生成樹(shù)算法研究
發(fā)布時(shí)間：2018-10-16 09:33
【摘要】：圖論作為數(shù)學(xué)的一個(gè)重要分支,在計(jì)算機(jī)科學(xué)中也扮演著非常重要的角色。隨著大數(shù)據(jù)時(shí)代的到來(lái),圖數(shù)據(jù)的規(guī)模也隨之增大,因此圖算法的效率對(duì)于解決圖論問(wèn)題至關(guān)重要。由于現(xiàn)實(shí)問(wèn)題中可能會(huì)遇到很多的意外情況,如機(jī)器故障,信號(hào)傳輸?shù)牟环�(wěn)定性等,最終導(dǎo)致實(shí)際數(shù)據(jù)存在不確定性。因此不確定圖已經(jīng)成為一個(gè)非常熱門的研究領(lǐng)域。本文對(duì)不確定圖中的生成樹(shù)算法進(jìn)行了研究,主要獲得了如下成果:(1)由于不確定圖的邊存在不確定性,所以傳統(tǒng)的最小生成樹(shù)定義已經(jīng)不能完全適用于不確定圖。因此提出了最優(yōu)生成樹(shù)的概念,它主要是在最小生成樹(shù)定義的基礎(chǔ)上增加了對(duì)概率的最優(yōu)化定義。然后我們借助貪心的思想設(shè)計(jì)了不確定圖中最優(yōu)生成樹(shù)算法。(2)為了能夠找到不確定圖中的所有關(guān)鍵邊,我們?cè)O(shè)計(jì)了Top-K最小生成樹(shù)算法,并提出了基于并查集的優(yōu)化算法和基于啟發(fā)式搜索的優(yōu)化算法。當(dāng)值較小時(shí),基于啟發(fā)式搜索的優(yōu)化算法具有明顯的優(yōu)勢(shì)。(3)對(duì)最小生成樹(shù)在不確定圖中的可靠性進(jìn)行了分析。將可靠性定義為所有包含最小生成樹(shù)的蘊(yùn)含圖的存在概率之和,主要使用了邊集劃分的方法將所有蘊(yùn)含圖進(jìn)行歸類,在同一類中的蘊(yùn)含圖具有相同的最小生成樹(shù),通過(guò)求同一類中所有蘊(yùn)含圖存在的概率來(lái)獲得不確定圖的可靠性。(4)針對(duì)不確定有向圖,給出了最優(yōu)樹(shù)形圖的定義,設(shè)計(jì)了最優(yōu)樹(shù)形圖算法。最后將TOP-K最小生成樹(shù)算法的思想和最優(yōu)樹(shù)形圖的性質(zhì)相結(jié)合設(shè)計(jì)了TOP-K最小樹(shù)形圖查詢算法。最后,我們對(duì)不確定圖中生成樹(shù)的研究進(jìn)行了相關(guān)的實(shí)驗(yàn)驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,設(shè)計(jì)的算法的運(yùn)行效率與理論分析基本一致,且能夠完全正確的得到問(wèn)題的解。
[Abstract]:As an important branch of mathematics, graph theory also plays a very important role in computer science. With the arrival of big data era, the scale of graph data increases, so the efficiency of graph algorithm is very important to solve graph theory problem. Many unexpected situations may be encountered in practical problems, such as machine failure, instability of signal transmission and so on, resulting in uncertainty of actual data. Therefore, uncertainty graph has become a very popular research field. In this paper, the spanning tree algorithm in uncertain graphs is studied. The main results are as follows: (1) because of the uncertainty in the edges of uncertain graphs, the traditional definition of minimum spanning tree can no longer be fully applied to uncertain graphs. Therefore, the concept of optimal spanning tree is proposed, which mainly adds the optimal definition of probability on the basis of the definition of minimum spanning tree. Then we design the optimal spanning tree algorithm in uncertain graph with greedy idea. (2) in order to find all the key edges of uncertain graph, we design the Top-K minimum spanning tree algorithm. An optimization algorithm based on parallel search set and an optimization algorithm based on heuristic search are proposed. When the value is small, the heuristic search based optimization algorithm has obvious advantages. (3) the reliability of the minimum spanning tree in uncertain graphs is analyzed. The reliability is defined as the sum of the existential probability of all the implied graphs containing the minimum spanning tree. The edge set partition method is mainly used to classify all the implied graphs, and the implied graphs in the same class have the same minimum spanning tree. The reliability of uncertain graphs is obtained by finding the probability of the existence of all implicit graphs in the same class. (4) for uncertain digraphs, the definition of optimal tree graphs is given, and an optimal tree graph algorithm is designed. Finally, the idea of TOP-K minimum spanning tree algorithm and the properties of the optimal tree graph are combined to design the TOP-K minimum tree graph query algorithm. Finally, the experimental results show that the efficiency of the proposed algorithm is consistent with the theoretical analysis, and the solution of the problem can be obtained correctly.
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
本文編號(hào)：2273938
[Abstract]:As an important branch of mathematics, graph theory also plays a very important role in computer science. With the arrival of big data era, the scale of graph data increases, so the efficiency of graph algorithm is very important to solve graph theory problem. Many unexpected situations may be encountered in practical problems, such as machine failure, instability of signal transmission and so on, resulting in uncertainty of actual data. Therefore, uncertainty graph has become a very popular research field. In this paper, the spanning tree algorithm in uncertain graphs is studied. The main results are as follows: (1) because of the uncertainty in the edges of uncertain graphs, the traditional definition of minimum spanning tree can no longer be fully applied to uncertain graphs. Therefore, the concept of optimal spanning tree is proposed, which mainly adds the optimal definition of probability on the basis of the definition of minimum spanning tree. Then we design the optimal spanning tree algorithm in uncertain graph with greedy idea. (2) in order to find all the key edges of uncertain graph, we design the Top-K minimum spanning tree algorithm. An optimization algorithm based on parallel search set and an optimization algorithm based on heuristic search are proposed. When the value is small, the heuristic search based optimization algorithm has obvious advantages. (3) the reliability of the minimum spanning tree in uncertain graphs is analyzed. The reliability is defined as the sum of the existential probability of all the implied graphs containing the minimum spanning tree. The edge set partition method is mainly used to classify all the implied graphs, and the implied graphs in the same class have the same minimum spanning tree. The reliability of uncertain graphs is obtained by finding the probability of the existence of all implicit graphs in the same class. (4) for uncertain digraphs, the definition of optimal tree graphs is given, and an optimal tree graph algorithm is designed. Finally, the idea of TOP-K minimum spanning tree algorithm and the properties of the optimal tree graph are combined to design the TOP-K minimum tree graph query algorithm. Finally, the experimental results show that the efficiency of the proposed algorithm is consistent with the theoretical analysis, and the solution of the problem can be obtained correctly.
【學(xué)位授予單位】：湘潭大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【相似文獻(xiàn)】
相關(guān)期刊論文 前3條
1 胡楓,于福溪;最小生成樹(shù)算法在多元連接中的應(yīng)用及算法分析[J];青海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期
2 程媛媛;;基于Prim最小生成樹(shù)算法的時(shí)間成本研究[J];河北北方學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年06期
3 ;[J];;年期
相關(guān)會(huì)議論文 前1條
1 周惠巍;黃德根;高潔;楊元生;;最大生成樹(shù)算法和Nivre算法相結(jié)合的中文依存關(guān)系解析[A];中國(guó)計(jì)算語(yǔ)言學(xué)研究前沿進(jìn)展（2009-2011）[C];2011年
相關(guān)重要報(bào)紙文章 前1條
1 ;最偉大的網(wǎng)絡(luò)技術(shù)發(fā)明者[N];網(wǎng)絡(luò)世界;2007年
相關(guān)碩士學(xué)位論文 前2條
1 唐杰;不確定圖中的生成樹(shù)算法研究[D];湘潭大學(xué);2015年
2 楊寅;社會(huì)網(wǎng)絡(luò)分析工具中的分布式最小生成樹(shù)算法[D];北京郵電大學(xué);2011年
，本文編號(hào)：2273938
本文鏈接：http://sikaile.net/kejilunwen/yysx/2273938.html
最近更新
教材專著
