本文選題：Dijkstra算法 + 矩形搜索算法�。� 參考：《中北大學(xué)》2017年碩士論文

【摘要】：現(xiàn)如今,城市規(guī)模擴(kuò)大,汽車數(shù)量增多,交通擁堵問(wèn)題成我國(guó)亟需解決的重要問(wèn)題之一。解決城市路網(wǎng)交通擁堵問(wèn)題的關(guān)鍵技術(shù)在于最短路徑的研究。因此,基于城市路網(wǎng)的最短路徑算法研究具有重要意義。本課題重點(diǎn)研究了求解城市路網(wǎng)最短路徑的Dijkstra算法以及求解K最短路徑的Yen算法,主要工作如下:(1)在存儲(chǔ)城市路網(wǎng)圖方面,鄰接矩陣存儲(chǔ)稀疏圖時(shí),存在數(shù)據(jù)冗余度大的問(wèn)題,本文提出用鄰接表數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)城市路網(wǎng)圖,降低Dijkstra算法的空間復(fù)雜度。(2)在搜索范圍優(yōu)化方面,Dijkstra算法存在搜索范圍廣、遍歷節(jié)點(diǎn)多,耗時(shí)長(zhǎng)的問(wèn)題,本文對(duì)橢圓搜索算法、矩形搜索算法優(yōu)化Dijkstra算法的問(wèn)題進(jìn)行深入的分析,結(jié)合路網(wǎng)特征給出兩種算法的具體搜索范圍和面積公式。并通過(guò)實(shí)驗(yàn)對(duì)比分析,證明了采用矩形算法優(yōu)化Dijkstra算法的可行性和高效性。(3)針對(duì)Yen算法在求解K最短路徑計(jì)算比較復(fù)雜,時(shí)間復(fù)雜度高的問(wèn)題,對(duì)Yen算法做了改進(jìn)。通過(guò)引入估價(jià)函數(shù),求解最短路徑時(shí)只選取估價(jià)值最小的節(jié)點(diǎn)作為最終的偏離節(jié)點(diǎn),降低了算法的復(fù)雜度。并通過(guò)實(shí)驗(yàn),從算法尋路時(shí)間、算法所求的路徑長(zhǎng)度及尋路過(guò)程中產(chǎn)生的候選路徑數(shù)目方面對(duì)比分析了兩種算法,驗(yàn)證了算法的有效性。(4)基于unity3d和3ds Max,利用了模型優(yōu)化技術(shù)設(shè)計(jì)實(shí)現(xiàn)了虛擬城市路網(wǎng)尋路系統(tǒng),將矩形搜索算法和基于啟發(fā)式搜索改進(jìn)的Yen算法應(yīng)用到虛擬城市路網(wǎng)尋路系統(tǒng)中,并驗(yàn)證了本文所提觀點(diǎn)在具體應(yīng)用中的高效性和可行性,達(dá)到了預(yù)期的尋路效果。
[Abstract]:Nowadays, with the expansion of the city scale and the increase of the number of cars, the problem of traffic congestion has become one of the most important problems that need to be solved in our country. The research of shortest path is the key technology to solve the problem of traffic congestion in urban road network. Therefore, it is of great significance to study the shortest path algorithm based on urban road network. This paper focuses on the Dijkstra algorithm for solving the shortest path of urban road network and the Yen algorithm for solving the shortest path of urban road network. The main work is as follows: in the storage of urban road network map, the problem of data redundancy exists when the adjacent matrix is used to store sparse map. In this paper, we put forward the problem of storing urban road map using adjacent table data structure to reduce the space complexity of Dijkstra algorithm. In the aspect of searching range optimization, Dijkstra algorithm has the problems of wide search scope, many traversing nodes and long time consuming. In this paper, elliptical search algorithm is discussed. The problem of optimizing Dijkstra algorithm by rectangular search algorithm is analyzed deeply, and the specific search range and area formula of the two algorithms are given according to the road network features. The feasibility and high efficiency of using rectangle algorithm to optimize Dijkstra algorithm are proved by comparing experiments. Aiming at the problem of complex computation and high time complexity of Yen algorithm for solving K shortest path, the Yen algorithm is improved. By introducing the evaluation function, only the node with the smallest estimated value is selected as the final deviation node when solving the shortest path, and the complexity of the algorithm is reduced. Through experiments, the two algorithms are compared and analyzed in terms of the searching time, the path length and the number of candidate paths generated in the route finding process. The validity of the algorithm is verified. Based on unity3d and 3ds Maxs, the virtual city road network routing system is designed and implemented by using model optimization technology. The rectangular search algorithm and the improved Yen algorithm based on heuristic search are applied to the virtual city road finding system. The efficiency and feasibility of this paper are verified, and the expected route finding effect is achieved.
【學(xué)位授予單位】：中北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U491;TP301.6

【參考文獻(xiàn)】

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

1 金歡;;城市智能交通系統(tǒng)車輛路徑規(guī)劃算法優(yōu)化研究[J];信息系統(tǒng)工程;2016年12期

2 倪燁;;3DSMAX在虛擬場(chǎng)景建模中的應(yīng)用分析[J];無(wú)線互聯(lián)科技;2016年22期

3 肖建良;張程;李陽(yáng);;基于Unity3D的室內(nèi)漫游系統(tǒng)[J];電子設(shè)計(jì)工程;2016年19期

4 宋斌斌;金慧琴;李啟超;;改進(jìn)A*算法在突防航跡規(guī)劃中的應(yīng)用[J];兵器裝備工程學(xué)報(bào);2016年07期

5 楊亞偉;王璐;王斐;;一種改進(jìn)的A*算法在電纜敷設(shè)設(shè)計(jì)中的應(yīng)用[J];電線電纜;2016年03期

6 張程程;康維新;;交通動(dòng)態(tài)路網(wǎng)模型與能耗最優(yōu)路徑誘導(dǎo)[J];應(yīng)用科技;2015年04期

7 肖英才;;A*算法在露天礦運(yùn)輸?shù)缆纷顑?yōu)路線的應(yīng)用[J];中國(guó)鉬業(yè);2015年01期

8 游堯;林培群;;基于智能優(yōu)化算法的動(dòng)態(tài)路徑誘導(dǎo)方法研究進(jìn)展[J];交通運(yùn)輸研究;2015年01期

9 孫佳弘;;Kinect系統(tǒng)在Unity3D游戲角色動(dòng)畫制作中的應(yīng)用[J];電子技術(shù)與軟件工程;2013年24期

10 杜雪;劉衛(wèi)光;;智能交通系統(tǒng)中最短路徑算法優(yōu)化的研究[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2013年23期

，

本文編號(hào)：1866024