基于路径阻断的求解最短路径的BFS算法研究

发布时间：2018-04-12 06:09

本文选题：路径阻断 + 广度优先遍历　；参考：《北京化工大学》2017年硕士论文

【摘要】：最近几年,随着网络的诞生与兴起,网络学科被广泛地应用到更多其他的学科,例如,物理、化学、生物、政治、经济、互联网络、工程开发和社会生活等方面。随着大数据时代的来临,基于每一个学科提取和抽象出的复杂网络的规模将会变得越来越大。而以最短路径为主的最优路径问题一直是计算机科学、交通科学、工程科学、控制科学、交通工程学以及地理信息科学等。它也是许许多多问题的基础和研究热点,例如设计路线、分配资源等。而计算机处理数据量的不断增加和变大,许许多多经典的算法求解的时间变得越来越长,例如Dijkstra算法需要O(n2)的时间复杂度,而且也使得计算机的负荷变得也来越大,无法满足大规模网络求解最短路径的实时需求。因此对网络分析算法的性能有进一步和更高的时间要求——即要求在更短的时间内完成大规模网络的全源最短路径的计算。因此在这样的课题背景下提出基于路径阻断的BFS算法。本文的主要工作如下,1.本课题是是以网络的经典遍历算法——BFS (广度优先遍历)作为研究的基础,引入路径阻断的策略。得到了本论文的核心算法之一——基于路径阻断的BFS算法(block算法),并详细地阐述了 block算法的整个处理网络的过程。2.在通过对block算法分析的基础上,加入阻断点的选择、求解单源最短路径的节点排序等3个策略,得到几个性能比BFS算法,block算法更好,求解全源最短路径的时间更短的算法。(1)第一个阻断策略是通过对求解单源最短路径的节点按照节点的度值降序进行排序。这个策略是通过先求解大规模复杂网络中的一些关键的节点(最短路径问题中体现为度值较大的节点),能够使得算法在后续的处理中能够使得阻断的效果更好。在block算法的基础上,通过引入这个策略,得到了 blockODD (block of descendant degree)算法。(2)第二个阻断的策略是限制阻断的次数,在Block算法处理网络的实验基础上,得到了 block算法阻断的次数和block算法的处理时间呈现出一个相似的趋势,为了进一步减少block算法的处理时间,通过一个实时的统计进入待遍历队列的节点个数以及一个阈值的比较进一步使得选择阻断点的条件更加严苛,使得算法的效率进一步提高。在block算法的基础上,通过引入这个策略,得到enqueue-block算法簇。(3)第三个阻断的策略是以最短路径形成的生成树作为及理论依据,通过分析网络的结构得到在以起始节点的邻居节点的阻断效果是比较好的,而且通过一次阻断之后,起始节点的单源最短路径具有较高的正确率,尤其是度值为1的节点通过邻居节点的阻断效果是最好的,正确率是最高。在block算法的基础上,通过引入这个策略,得到first-level-block算法。在基于block算法的基础上,比较了若干个算法求解全源最短路径和单源最短路径的时间。在实验得到几个比BFS算法更快的算法。
[Abstract]:In recent years, with the birth and rise of the network, network has been widely used in many other disciplines, such as physics, chemistry, biology, politics, economy, Internet, engineering development and social life.With the advent of big data era, the scale of complex network based on each subject will become larger and larger.The optimal path problem with the shortest path is computer science, traffic science, engineering science, control science, traffic engineering and geographic information science.It is also the basis of many problems and research hot spots, such as design routes, allocation of resources, and so on.With the increasing and increasing amount of data processed by computer, the time of solving many classical algorithms becomes longer and longer, for example, the time complexity of Dijkstra algorithm needs ON2), and the load of computer becomes larger, too.It can not meet the real-time requirement of solving the shortest path in large scale networks.Therefore, the performance of the network analysis algorithm has further and higher time requirements-that is, to complete the calculation of the full source shortest path of large-scale network in a shorter time.Therefore, under this background, the BFS algorithm based on path blocking is proposed.The main work of this paper is as follows.Based on the classical traversal algorithm BFS (breadth first traversal), this paper introduces the path blocking strategy.In this paper, one of the core algorithms of this thesis, BFS algorithm based on path blocking, is obtained, and the whole process of processing network of block algorithm is described in detail.On the basis of the analysis of block algorithm, adding the selection of blocking points and solving the node sorting of single source shortest path, three strategies are obtained, which are better performance than BFS algorithm.The first blocking strategy is to sort the nodes of the single source shortest path in descending order according to the degree of the nodes.The strategy is to solve some key nodes in large-scale complex networks (the shortest path problem is represented by a large number of nodes), so that the algorithm can make the blocking effect better in the subsequent processing.On the basis of block algorithm, by introducing this strategy, we get the second blocking strategy of blockODD block of descendant degree of degree algorithm. The second strategy is to limit the number of times of blocking. On the basis of the experiment of Block algorithm to deal with the network,In order to further reduce the processing time of block algorithm, the number of blocking of block algorithm and the processing time of block algorithm show a similar trend.Through a real-time statistics of the number of nodes entering the queue to be traversed and the comparison of a threshold, the conditions for selecting blocking points are more stringent, and the efficiency of the algorithm is further improved.On the basis of block algorithm, by introducing this strategy, we get that the third blocking strategy of enqueue-block algorithm cluster is based on the spanning tree formed by the shortest path and the theoretical basis.By analyzing the structure of the network, it is found that the blocking effect of the neighbor node with the starting node is better, and after one block, the single source shortest path of the starting node has a higher accuracy.In particular, the blocking effect of nodes with degree of 1 through neighbor nodes is the best and the correct rate is the highest.On the basis of block algorithm, the first-level-block algorithm is obtained by introducing this strategy.Based on the block algorithm, the time of solving the full source shortest path and the single source shortest path is compared.In the experiment, several algorithms are obtained faster than the BFS algorithm.
【学位授予单位】：北京化工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6;O157.5

【相似文献】