發(fā)布時(shí)間：2019-05-12 11:42

【摘要】：最短路徑問(wèn)題是圖論與算法設(shè)計(jì)中的經(jīng)典問(wèn)題,同時(shí)也在路徑規(guī)劃、物流規(guī)劃、GPS導(dǎo)航、社交網(wǎng)絡(luò)、基于位置的服務(wù)(LBS)等現(xiàn)實(shí)世界的應(yīng)用中扮演著重要的角色。交通路網(wǎng)上最短路徑問(wèn)題由最短路徑問(wèn)題衍生而來(lái),特點(diǎn)為交通網(wǎng)數(shù)據(jù)規(guī)模大(如北京市主干路網(wǎng)就包含了10萬(wàn)個(gè)頂點(diǎn)與10萬(wàn)條邊),計(jì)算請(qǐng)求頻繁且實(shí)時(shí)性要求很高,傳統(tǒng)的最短路徑算法并不能滿足計(jì)算需求。 “預(yù)處理——查詢”模型是一種交通路網(wǎng)上最短路徑問(wèn)題的兩階段方法。在第一階段對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,包括獲得待使用的中間數(shù)據(jù),以降低問(wèn)題的求解難度；第二階段被稱(chēng)為查詢階段,給定查詢請(qǐng)求的源點(diǎn)與目標(biāo)點(diǎn),每個(gè)請(qǐng)求須在極短時(shí)間內(nèi)進(jìn)行響應(yīng)。兩階段的想法源自路網(wǎng)是靜態(tài)的,因此預(yù)處理階段可以僅執(zhí)行一次,其結(jié)果可以應(yīng)對(duì)相同路網(wǎng)上大規(guī)模的查詢請(qǐng)求。 本文主要工作有： 1,基于預(yù)處理——查詢模型的幾種點(diǎn)到點(diǎn)最短路徑算法性能分析 本文針對(duì)“預(yù)處理——查詢”模型上的兩類(lèi)算法——空間相干為基礎(chǔ)的方法和頂點(diǎn)重要性為基礎(chǔ)的方法,選出兩類(lèi)方法中具有代表性的算法,就預(yù)處理時(shí)間、空間消耗、查詢效率進(jìn)行分析比較。 2,針對(duì)一種基于代表元的有效最短路徑近似算法,對(duì)代表元選取策略進(jìn)行研究 由于代表元的選取策略直接影響近似算法的求解精度,因此如何對(duì)路網(wǎng)進(jìn)行區(qū)域劃分、如何在區(qū)域中分配代表元成為了算法是否高效的關(guān)鍵點(diǎn)。本文將結(jié)合已提出的高效劃分方案,提出一種適合最短路徑近似算法的劃分策略,并分析其與求解精度之間的聯(lián)系。 3,通過(guò)模擬真實(shí)環(huán)境下路網(wǎng)上的實(shí)時(shí)查詢請(qǐng)求,對(duì)最短路徑長(zhǎng)度的估算策略進(jìn)行研究 本文通過(guò)結(jié)合可視化的路網(wǎng)動(dòng)態(tài)查詢演示,說(shuō)明近似算法對(duì)于最短路徑中源點(diǎn)與目標(biāo)結(jié)點(diǎn)的近似距離可做進(jìn)一步優(yōu)化,并提出一種基于代表元的兩點(diǎn)間距離估算策略,對(duì)估算誤差進(jìn)行分析。
[Abstract]:The shortest path problem is a classical problem in graph theory and algorithm design. It also plays an important role in the real world applications such as path planning, logistics planning, GPS navigation, social network, location-based service (LBS) and so on. The shortest path problem on the traffic network is derived from the shortest path problem. It is characterized by the large scale of traffic network data (for example, the Beijing backbone network contains 100000 vertices and 100000 edges). The computation request is frequent and the real-time requirement is very high. The traditional shortest path algorithm can not meet the computing requirements. Preprocessing query model is a two-stage method for the shortest path problem on traffic network. In the first stage, the data is preprocessed, including obtaining the intermediate data to be used in order to reduce the difficulty of solving the problem. The second stage is called the query stage. Given the source and target points of the query request, each request must be responded to in a very short period of time. The idea of two stages originates from the fact that the road network is static, so the preprocessing phase can be executed only once, and the result can deal with large-scale query requests on the same road network. The main work of this paper is as follows: 1, Performance Analysis of several Point-to-Point shortest path algorithms based on pre-processing-query Model this paper focuses on the spatial coherence-based method and vertex importance-based method for two kinds of algorithms on the "pre-processing-query" model. The representative algorithms of the two methods are selected, and the preprocessing time, space consumption and query efficiency are analyzed and compared. 2. Aiming at an effective shortest path approximation algorithm based on representative element, this paper studies the selection strategy of representative element, because the selection strategy of representative element directly affects the accuracy of the approximate algorithm, so how to divide the region of the road network is carried out. How to allocate representative elements in the region becomes the key point of whether the algorithm is efficient or not. In this paper, combined with the proposed efficient partition scheme, a partition strategy suitable for the shortest path approximation algorithm is proposed, and the relationship between it and the accuracy of the solution is analyzed. 3. By simulating the real-time query request on the road network, the estimation strategy of the shortest path length is studied in this paper by combining the visual dynamic query demonstration of the road network. It is shown that the approximate distance between the source point and the target node in the shortest path can be further optimized by the approximate algorithm, and a distance estimation strategy between the two points based on the representative element is proposed, and the estimation error is analyzed.
【學(xué)位授予單位】：中國(guó)科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：U491

【共引文獻(xiàn)】

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

1 姚海龍;蔡懿慈;洪先龍;周強(qiáng);;考慮擁擠度和性能的全芯片可控布線系統(tǒng)框架(英文)[J];半導(dǎo)體學(xué)報(bào);2006年07期

2 盧新明;鄭時(shí)德;;求解路網(wǎng)上車(chē)流徑路的啟發(fā)式算法[J];北方交通大學(xué)學(xué)報(bào);1993年03期

3 王海梅;周獻(xiàn)中;;網(wǎng)絡(luò)系統(tǒng)中的最短路徑分析及其應(yīng)用研究[J];兵工學(xué)報(bào);2006年03期

4 李玉擰;徐立業(yè);;不加權(quán)算術(shù)平均組對(duì)方法的改進(jìn)及應(yīng)用[J];北京工業(yè)大學(xué)學(xué)報(bào);2007年12期

5 李玉擰;高凱;;一種改進(jìn)的NJ方法及其應(yīng)用[J];北京工業(yè)大學(xué)學(xué)報(bào);2009年02期

6 陳艷艷;王東柱;;高可靠性應(yīng)急備選路徑啟發(fā)式搜索算法[J];北京工業(yè)大學(xué)學(xué)報(bào);2010年09期

7 彭飛,柳重堪,張其善;車(chē)輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J];北京航空航天大學(xué)學(xué)報(bào);2002年01期

8 趙愛(ài)華;丁志峰;;復(fù)雜速度模型的地震交切定位方法(英文)[J];Applied Geophysics;2007年04期

9 李秉智;李智;;一種新的基于Dijkstra算法的QoS組播樹(shù)啟發(fā)式算法[J];重慶郵電學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年01期

10 龔萍;吳澤忠;;基于效用值的模糊最短路問(wèn)題的研究[J];成都信息工程學(xué)院學(xué)報(bào);2010年04期

，

本文編號(hào)：2475363