發(fā)布時間：2018-05-09 12:32

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

【摘要】：現(xiàn)如今,城市規(guī)模擴大,汽車數(shù)量增多,交通擁堵問題成我國亟需解決的重要問題之一。解決城市路網(wǎng)交通擁堵問題的關鍵技術在于最短路徑的研究。因此,基于城市路網(wǎng)的最短路徑算法研究具有重要意義。本課題重點研究了求解城市路網(wǎng)最短路徑的Dijkstra算法以及求解K最短路徑的Yen算法,主要工作如下:(1)在存儲城市路網(wǎng)圖方面,鄰接矩陣存儲稀疏圖時,存在數(shù)據(jù)冗余度大的問題,本文提出用鄰接表數(shù)據(jù)結(jié)構存儲城市路網(wǎng)圖,降低Dijkstra算法的空間復雜度。(2)在搜索范圍優(yōu)化方面,Dijkstra算法存在搜索范圍廣、遍歷節(jié)點多,耗時長的問題,本文對橢圓搜索算法、矩形搜索算法優(yōu)化Dijkstra算法的問題進行深入的分析,結(jié)合路網(wǎng)特征給出兩種算法的具體搜索范圍和面積公式。并通過實驗對比分析,證明了采用矩形算法優(yōu)化Dijkstra算法的可行性和高效性。(3)針對Yen算法在求解K最短路徑計算比較復雜,時間復雜度高的問題,對Yen算法做了改進。通過引入估價函數(shù),求解最短路徑時只選取估價值最小的節(jié)點作為最終的偏離節(jié)點,降低了算法的復雜度。并通過實驗,從算法尋路時間、算法所求的路徑長度及尋路過程中產(chǎn)生的候選路徑數(shù)目方面對比分析了兩種算法,驗證了算法的有效性。(4)基于unity3d和3ds Max,利用了模型優(yōu)化技術設計實現(xiàn)了虛擬城市路網(wǎng)尋路系統(tǒng),將矩形搜索算法和基于啟發(fā)式搜索改進的Yen算法應用到虛擬城市路網(wǎng)尋路系統(tǒng)中,并驗證了本文所提觀點在具體應用中的高效性和可行性,達到了預期的尋路效果。
[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.
【學位授予單位】：中北大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：U491;TP301.6

【參考文獻】

相關期刊論文 前10條

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

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

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

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

5 楊亞偉;王璐;王斐;;一種改進的A*算法在電纜敷設設計中的應用[J];電線電纜;2016年03期

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

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

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

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

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

，

本文編號：1866024