本文選題：路徑阻斷 + 廣度優(yōu)先遍歷��； 參考：《北京化工大學》2017年碩士論文

【摘要】：最近幾年,隨著網(wǎng)絡的誕生與興起,網(wǎng)絡學科被廣泛地應用到更多其他的學科,例如,物理、化學、生物、政治、經(jīng)濟、互聯(lián)網(wǎng)絡、工程開發(fā)和社會生活等方面。隨著大數(shù)據(jù)時代的來臨,基于每一個學科提取和抽象出的復雜網(wǎng)絡的規(guī)模將會變得越來越大。而以最短路徑為主的最優(yōu)路徑問題一直是計算機科學、交通科學、工程科學、控制科學、交通工程學以及地理信息科學等。它也是許許多多問題的基礎和研究熱點,例如設計路線、分配資源等。而計算機處理數(shù)據(jù)量的不斷增加和變大,許許多多經(jīng)典的算法求解的時間變得越來越長,例如Dijkstra算法需要O(n2)的時間復雜度,而且也使得計算機的負荷變得也來越大,無法滿足大規(guī)模網(wǎng)絡求解最短路徑的實時需求。因此對網(wǎng)絡分析算法的性能有進一步和更高的時間要求——即要求在更短的時間內(nèi)完成大規(guī)模網(wǎng)絡的全源最短路徑的計算。因此在這樣的課題背景下提出基于路徑阻斷的BFS算法。本文的主要工作如下,1.本課題是是以網(wǎng)絡的經(jīng)典遍歷算法——BFS (廣度優(yōu)先遍歷)作為研究的基礎,引入路徑阻斷的策略。得到了本論文的核心算法之一——基于路徑阻斷的BFS算法(block算法),并詳細地闡述了 block算法的整個處理網(wǎng)絡的過程。2.在通過對block算法分析的基礎上,加入阻斷點的選擇、求解單源最短路徑的節(jié)點排序等3個策略,得到幾個性能比BFS算法,block算法更好,求解全源最短路徑的時間更短的算法。(1)第一個阻斷策略是通過對求解單源最短路徑的節(jié)點按照節(jié)點的度值降序進行排序。這個策略是通過先求解大規(guī)模復雜網(wǎng)絡中的一些關鍵的節(jié)點(最短路徑問題中體現(xiàn)為度值較大的節(jié)點),能夠使得算法在后續(xù)的處理中能夠使得阻斷的效果更好。在block算法的基礎上,通過引入這個策略,得到了 blockODD (block of descendant degree)算法。(2)第二個阻斷的策略是限制阻斷的次數(shù),在Block算法處理網(wǎng)絡的實驗基礎上,得到了 block算法阻斷的次數(shù)和block算法的處理時間呈現(xiàn)出一個相似的趨勢,為了進一步減少block算法的處理時間,通過一個實時的統(tǒng)計進入待遍歷隊列的節(jié)點個數(shù)以及一個閾值的比較進一步使得選擇阻斷點的條件更加嚴苛,使得算法的效率進一步提高。在block算法的基礎上,通過引入這個策略,得到enqueue-block算法簇。(3)第三個阻斷的策略是以最短路徑形成的生成樹作為及理論依據(jù),通過分析網(wǎng)絡的結(jié)構(gòu)得到在以起始節(jié)點的鄰居節(jié)點的阻斷效果是比較好的,而且通過一次阻斷之后,起始節(jié)點的單源最短路徑具有較高的正確率,尤其是度值為1的節(jié)點通過鄰居節(jié)點的阻斷效果是最好的,正確率是最高。在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

【相似文獻】

相關期刊論文 前10條

1 劉耀林,范延平,唐旭;最短路徑方法在土地定級中的應用[J];武漢測繪科技大學學報;2000年06期

2 黃智星,夏富春;生物基因最短路徑模型分析[J];內(nèi)蒙古科技與經(jīng)濟;2005年07期

3 白青海;;一種求解交通圖最短路徑的方案[J];內(nèi)蒙古民族大學學報(自然科學版);2007年02期

4 高超;;游客最短路徑導游方案的設計[J];商業(yè)文化(下半月);2011年01期

5 吳鵬;;賦權圖上最短路徑的一種簡便算法[J];貴州師范大學學報(自然科學版);2012年05期

6 張玉成,孫俊逸;應用最優(yōu)化選擇原則求最短路徑及長度[J];湖北大學學報(自然科學版);1993年01期

7 班世炳;增刪邊對最短路徑影響的研究[J];廣西民族學院學報(自然科學版);1998年02期

8 潘開靈,呂緒華;罰轉(zhuǎn)向網(wǎng)絡最短路徑研究[J];武漢冶金科技大學學報(自然科學版);1999年01期

9 李?,山秀明,任勇;具有冪率度分布的因特網(wǎng)平均最短路徑長度估計[J];物理學報;2004年11期

10 張帆,李軍,王鈞,景寧;多目標最短路徑進化求解方法[J];系統(tǒng)工程;2005年09期

相關會議論文 前10條

1 溫粉蓮;唐常杰;喬少杰;許剛;劉威;左R，

本文編號：1738492