發(fā)布時間：2018-04-29 07:10

  本文選題：最短路徑問題 + 近似算法��； 參考：《遼寧大學》2017年碩士論文

【摘要】：最短路徑算法作為圖論研究和算法設(shè)計中的經(jīng)典問題之一,旨在尋找圖中兩個節(jié)點之間的最短路徑,已經(jīng)在現(xiàn)實生活中的諸多領(lǐng)域得到了廣泛的應(yīng)用,例如應(yīng)用在社會網(wǎng)絡(luò)、交通地理信息系統(tǒng)、路徑規(guī)劃、生物醫(yī)學、生物信息網(wǎng)絡(luò)及軍事綜合運輸?shù)�。最短路徑算法不僅是計算機科學技術(shù)領(lǐng)域研究的熱點問題,也得到了其他各個領(lǐng)域研究人員的密切關(guān)注。隨著近些年大數(shù)據(jù)時代的到來,數(shù)據(jù)規(guī)模不斷增加,數(shù)據(jù)的拓撲結(jié)構(gòu)也愈來愈復(fù)雜,目前的最短路徑算法已經(jīng)無法滿足日益增長的數(shù)據(jù)規(guī)模和查詢速度的需求,因此需要設(shè)計一個更加快速有效的最短路徑算法。本文深入研究了現(xiàn)有的最短路徑算法,發(fā)現(xiàn)無論是精確的最短路經(jīng)算法還是目前熱門研究的近似最短路徑算法,都已經(jīng)無法滿足數(shù)據(jù)量不斷增長、結(jié)構(gòu)越來越復(fù)雜的大規(guī)模網(wǎng)絡(luò)圖,針對復(fù)雜網(wǎng)絡(luò)具有的小世界模型特征和無標度的特點,目前最短路徑算法的研究方向一般都從兩階段查詢法入手,第一階段對數(shù)據(jù)進行預(yù)處理工作,建立標簽索引信息,第二階段利用預(yù)處理數(shù)據(jù)的結(jié)果對目標問題進行在線搜索。因此,如何均衡預(yù)處理代價、在線查詢速度和查詢結(jié)果的精確度這三者之間的關(guān)系,將是兩階段查詢法的關(guān)鍵問題,也是本文研究的主要內(nèi)容和方向。本文針對現(xiàn)實生活中復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的拓撲特性,提出一種適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)圖的近似最短路徑算法,基于區(qū)域樞紐點建立快速干道的近似最短路徑算法(Hub Vertex of area and Core Expressway,HEA-CE)。該算法首先計算節(jié)點的度和平衡值,在圖中選取少量的區(qū)域樞紐點,利用區(qū)域樞紐點將復(fù)雜網(wǎng)絡(luò)分割成一定數(shù)量的子圖區(qū)域,其中在每個子圖區(qū)域中,度最大的區(qū)域樞紐點稱為該子圖的區(qū)域核心點。利用區(qū)域樞紐點為每個子圖區(qū)域內(nèi)部構(gòu)建Core Expressway快速干道圖,用區(qū)域核心點為子圖區(qū)域間建立Freeway高速公路圖。根據(jù)預(yù)處理工作得到的區(qū)域樞紐點、區(qū)域樞紐點、Core Expressway快速干道圖和Freeway高速公路圖,本文提出了近似最短路徑的查詢算法,并給出了相應(yīng)的查詢策略。根據(jù)以上數(shù)據(jù)預(yù)處理的結(jié)果,及節(jié)點所在子圖區(qū)域的不同,通過區(qū)域樞紐點間、區(qū)域核心點間、區(qū)域樞紐點和區(qū)域核心點之間的最短路徑來近似計算大規(guī)模復(fù)雜網(wǎng)絡(luò)中兩個節(jié)點之間的最短路徑,能夠有效的減少搜索空間,提高了在線查詢效率。最后,通過和其他三種近似最短路徑算法的實驗結(jié)果進行對比分析,證明本文提出的近似最短路徑算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)分析中能夠良好的降低算法的復(fù)雜性,提高了在線查詢效率,并且具有較高的精準度,驗證了本文算法的有效性。
[Abstract]:As one of the classical problems in graph theory research and algorithm design, the shortest path algorithm is aimed at finding the shortest path between two nodes in the graph. It has been widely used in many fields in real life, such as social network. Transportation geographic information system, path planning, biomedicine, biological information network and military integrated transportation. The shortest path algorithm is not only a hot topic in the field of computer science and technology, but also received close attention by researchers in other fields. With the arrival of big data era in recent years, the scale of data is increasing, and the topology of data is becoming more and more complex. The shortest path algorithm can not meet the increasing demand of data scale and query speed. Therefore, it is necessary to design a faster and more effective shortest path algorithm. In this paper, the existing shortest path algorithm is deeply studied, and it is found that neither the accurate shortest path algorithm nor the most popular approximate shortest path algorithm can meet the increasing amount of data. In view of the small world model and scale-free characteristic of complex network, the research direction of shortest path algorithm generally starts with two-stage query method. In the first stage, the data is preprocessed and the label index information is established. In the second stage, the target problem is searched online using the results of the preprocessing data. Therefore, how to balance the cost of preprocessing, the speed of online query and the accuracy of query results will be the key problem of two-stage query, and the main content and direction of this paper. In view of the topological characteristics of complex network structure in real life, this paper presents an approximate shortest path algorithm suitable for large-scale complex network graphs. The approximate shortest path algorithm based on regional hub points to establish fast trunk roads is Hub Vertex of area and Core express approach to HEA-CEE. The algorithm first calculates the degree and balance of nodes, selects a small number of regional hub points in the graph, and divides the complex network into a certain number of subgraph regions by using the regional hub points. The maximum degree of regional hub point is called the regional core of the subgraph. The Core Expressway fast trunk road map is constructed by using the regional hub point as the interior of each sub-map area, and the Freeway expressway map is built by using the regional core point as the sub-map area. According to the regional hub point, the regional hub point Expressway fast trunk road map and the Freeway highway map, this paper puts forward the query algorithm of approximate shortest path, and gives the corresponding query strategy. According to the results of the data preprocessing above, and the different regions of the sub-graph where the nodes are located, through the regional hub points, between the regional core points, The shortest path between the regional hub point and the regional core point to approximate calculate the shortest path between the two nodes in the large-scale complex network can effectively reduce the search space and improve the efficiency of online query. Finally, by comparing the experimental results with other three approximate shortest path algorithms, it is proved that the proposed approximate shortest path algorithm can reduce the complexity of the algorithm well in the large-scale complex network analysis. The efficiency of online query is improved, and the accuracy is high. The validity of this algorithm is verified.
【學位授予單位】：遼寧大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5

【參考文獻】

相關(guān)期刊論文 前5條

1 Michael Small;Lvlin Hou;Linjun Zhang;;Random complex networks[J];National Science Review;2014年03期

2 唐晉韜;王挺;王戟;;適合復(fù)雜網(wǎng)絡(luò)分析的最短路徑近似算法[J];軟件學報;2011年10期

3 楊育彬;李寧;張瑤;;基于社會網(wǎng)絡(luò)可視化分析的數(shù)據(jù)挖掘(英文)[J];軟件學報;2008年08期

4 鄔開俊;鄭麗英;王鐵君;;復(fù)雜網(wǎng)絡(luò)幾種模型的比較與分析[J];科技信息(學術(shù)版);2006年03期

5 段凡丁;關(guān)于最短路徑的SPFA快速算法[J];西南交通大學學報;1994年02期

相關(guān)博士學位論文 前1條

1 張鐘;大規(guī)模圖上的最短路徑問題研究[D];中國科學技術(shù)大學;2014年

相關(guān)碩士學位論文 前1條

1 龔詩楠;大規(guī)模復(fù)雜網(wǎng)絡(luò)的最短路徑近似算法研究[D];電子科技大學;2013年

，

本文編號：1818931