不确定图中的生成树算法研究
发布时间：2018-10-16 09:33
【摘要】：图论作为数学的一个重要分支,在计算机科学中也扮演着非常重要的角色。随着大数据时代的到来,图数据的规模也随之增大,因此图算法的效率对于解决图论问题至关重要。由于现实问题中可能会遇到很多的意外情况,如机器故障,信号传输的不稳定性等,最终导致实际数据存在不确定性。因此不确定图已经成为一个非常热门的研究领域。本文对不确定图中的生成树算法进行了研究,主要获得了如下成果:(1)由于不确定图的边存在不确定性,所以传统的最小生成树定义已经不能完全适用于不确定图。因此提出了最优生成树的概念,它主要是在最小生成树定义的基础上增加了对概率的最优化定义。然后我们借助贪心的思想设计了不确定图中最优生成树算法。(2)为了能够找到不确定图中的所有关键边,我们设计了Top-K最小生成树算法,并提出了基于并查集的优化算法和基于启发式搜索的优化算法。当值较小时,基于启发式搜索的优化算法具有明显的优势。(3)对最小生成树在不确定图中的可靠性进行了分析。将可靠性定义为所有包含最小生成树的蕴含图的存在概率之和,主要使用了边集划分的方法将所有蕴含图进行归类,在同一类中的蕴含图具有相同的最小生成树,通过求同一类中所有蕴含图存在的概率来获得不确定图的可靠性。(4)针对不确定有向图,给出了最优树形图的定义,设计了最优树形图算法。最后将TOP-K最小生成树算法的思想和最优树形图的性质相结合设计了TOP-K最小树形图查询算法。最后,我们对不确定图中生成树的研究进行了相关的实验验证,实验结果表明,设计的算法的运行效率与理论分析基本一致,且能够完全正确的得到问题的解。
[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.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
本文编号：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.
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【相似文献】
相关期刊论文 前3条
1 胡枫,于福溪;最小生成树算法在多元连接中的应用及算法分析[J];青海师范大学学报(自然科学版);2004年02期
2 程媛媛;;基于Prim最小生成树算法的时间成本研究[J];河北北方学院学报(自然科学版);2013年06期
3 ;[J];;年期
相关会议论文 前1条
1 周惠巍;黄德根;高洁;杨元生;;最大生成树算法和Nivre算法相结合的中文依存关系解析[A];中国计算语言学研究前沿进展（2009-2011）[C];2011年
相关重要报纸文章 前1条
1 ;最伟大的网络技术发明者[N];网络世界;2007年
相关硕士学位论文 前2条
1 唐杰;不确定图中的生成树算法研究[D];湘潭大学;2015年
2 杨寅;社会网络分析工具中的分布式最小生成树算法[D];北京邮电大学;2011年
，本文编号：2273938
本文链接：https://www.wllwen.com/kejilunwen/yysx/2273938.html
