本文選題：最短路徑問(wèn)題 + 近似算法　； 參考：《遼寧大學(xué)》2017年碩士論文

【摘要】：最短路徑算法作為圖論研究和算法設(shè)計(jì)中的經(jīng)典問(wèn)題之一,旨在尋找圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑,已經(jīng)在現(xiàn)實(shí)生活中的諸多領(lǐng)域得到了廣泛的應(yīng)用,例如應(yīng)用在社會(huì)網(wǎng)絡(luò)、交通地理信息系統(tǒng)、路徑規(guī)劃、生物醫(yī)學(xué)、生物信息網(wǎng)絡(luò)及軍事綜合運(yùn)輸?shù)取Ｗ疃搪窂剿惴ú粌H是計(jì)算機(jī)科學(xué)技術(shù)領(lǐng)域研究的熱點(diǎn)問(wèn)題,也得到了其他各個(gè)領(lǐng)域研究人員的密切關(guān)注。隨著近些年大數(shù)據(jù)時(shí)代的到來(lái),數(shù)據(jù)規(guī)模不斷增加,數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)也愈來(lái)愈復(fù)雜,目前的最短路徑算法已經(jīng)無(wú)法滿足日益增長(zhǎng)的數(shù)據(jù)規(guī)模和查詢速度的需求,因此需要設(shè)計(jì)一個(gè)更加快速有效的最短路徑算法。本文深入研究了現(xiàn)有的最短路徑算法,發(fā)現(xiàn)無(wú)論是精確的最短路經(jīng)算法還是目前熱門研究的近似最短路徑算法,都已經(jīng)無(wú)法滿足數(shù)據(jù)量不斷增長(zhǎng)、結(jié)構(gòu)越來(lái)越復(fù)雜的大規(guī)模網(wǎng)絡(luò)圖,針對(duì)復(fù)雜網(wǎng)絡(luò)具有的小世界模型特征和無(wú)標(biāo)度的特點(diǎn),目前最短路徑算法的研究方向一般都從兩階段查詢法入手,第一階段對(duì)數(shù)據(jù)進(jìn)行預(yù)處理工作,建立標(biāo)簽索引信息,第二階段利用預(yù)處理數(shù)據(jù)的結(jié)果對(duì)目標(biāo)問(wèn)題進(jìn)行在線搜索。因此,如何均衡預(yù)處理代價(jià)、在線查詢速度和查詢結(jié)果的精確度這三者之間的關(guān)系,將是兩階段查詢法的關(guān)鍵問(wèn)題,也是本文研究的主要內(nèi)容和方向。本文針對(duì)現(xiàn)實(shí)生活中復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)涮匦?提出一種適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)圖的近似最短路徑算法,基于區(qū)域樞紐點(diǎn)建立快速干道的近似最短路徑算法(Hub Vertex of area and Core Expressway,HEA-CE)。該算法首先計(jì)算節(jié)點(diǎn)的度和平衡值,在圖中選取少量的區(qū)域樞紐點(diǎn),利用區(qū)域樞紐點(diǎn)將復(fù)雜網(wǎng)絡(luò)分割成一定數(shù)量的子圖區(qū)域,其中在每個(gè)子圖區(qū)域中,度最大的區(qū)域樞紐點(diǎn)稱為該子圖的區(qū)域核心點(diǎn)。利用區(qū)域樞紐點(diǎn)為每個(gè)子圖區(qū)域內(nèi)部構(gòu)建Core Expressway快速干道圖,用區(qū)域核心點(diǎn)為子圖區(qū)域間建立Freeway高速公路圖。根據(jù)預(yù)處理工作得到的區(qū)域樞紐點(diǎn)、區(qū)域樞紐點(diǎn)、Core Expressway快速干道圖和Freeway高速公路圖,本文提出了近似最短路徑的查詢算法,并給出了相應(yīng)的查詢策略。根據(jù)以上數(shù)據(jù)預(yù)處理的結(jié)果,及節(jié)點(diǎn)所在子圖區(qū)域的不同,通過(guò)區(qū)域樞紐點(diǎn)間、區(qū)域核心點(diǎn)間、區(qū)域樞紐點(diǎn)和區(qū)域核心點(diǎn)之間的最短路徑來(lái)近似計(jì)算大規(guī)模復(fù)雜網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的最短路徑,能夠有效的減少搜索空間,提高了在線查詢效率。最后,通過(guò)和其他三種近似最短路徑算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析,證明本文提出的近似最短路徑算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)分析中能夠良好的降低算法的復(fù)雜性,提高了在線查詢效率,并且具有較高的精準(zhǔn)度,驗(yàn)證了本文算法的有效性。
[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.
【學(xué)位授予單位】：遼寧大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

相關(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];軟件學(xué)報(bào);2011年10期

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

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

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

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

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

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

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

，

本文編號(hào)：1818931