本文選題：A星算法 + 二叉堆��； 參考：《華僑大學(xué)》2015年碩士論文

【摘要】：隨著網(wǎng)絡(luò)時(shí)代的來(lái)臨和城市規(guī)模的日益擴(kuò)大,人們?cè)诔鲂兄?往往會(huì)查詢出行的路線。現(xiàn)在各種各樣的出行路線查詢系統(tǒng)很多,但是優(yōu)質(zhì)的出行路線查詢功能還有待提高,還需要進(jìn)一步對(duì)出行路線的路徑搜索算法進(jìn)行優(yōu)化。A星算法是目前最廣泛使用的城市出行路徑搜索算法之一。它是一種啟發(fā)式搜索算法,其采用的估價(jià)函數(shù)是:F(n)=G(n)+H(n),其中G(n)表示從起始頂點(diǎn)到當(dāng)前頂點(diǎn)的距離的實(shí)際值,H(n)表示從當(dāng)前頂點(diǎn)到目標(biāo)頂點(diǎn)的距離的估算值。兩者相加的結(jié)果為估價(jià)函數(shù)的估價(jià)值,選擇估價(jià)值最小的頂點(diǎn)作為下一步要選擇的頂點(diǎn),如此循環(huán)運(yùn)行估價(jià)函數(shù)從而生成最優(yōu)路徑。本文結(jié)合實(shí)際應(yīng)用,對(duì)標(biāo)準(zhǔn)A算法進(jìn)行了以下兩方面改進(jìn):使用最小二叉堆技術(shù)優(yōu)化0PEN表的查找速度,提高尋徑效率。對(duì)于A星算法的估價(jià)函數(shù),筆者在如下方面進(jìn)行了改進(jìn):1.選擇合適的啟發(fā)函數(shù)。2.增加啟發(fā)函數(shù)在估價(jià)函數(shù)中的比重。3.使用向量?jī)?nèi)積值改進(jìn)啟發(fā)函數(shù)在估價(jià)函數(shù)的比重。4.過(guò)濾內(nèi)積值進(jìn)一步優(yōu)化估價(jià)函數(shù)。從而減少尋徑過(guò)程中遍歷的頂點(diǎn)數(shù),在保證尋徑質(zhì)量整體不變的前提下,較大幅度的提高了尋徑效率。本文在Visual Studio 2010開(kāi)發(fā)平臺(tái)上,使用C++語(yǔ)言分別實(shí)現(xiàn)了標(biāo)準(zhǔn)A星和改進(jìn)A星的路徑搜索算法,在此基礎(chǔ)上統(tǒng)計(jì)它們的尋徑長(zhǎng)度、尋徑時(shí)間、尋徑過(guò)程中遍歷的頂點(diǎn)數(shù)量,以此驗(yàn)證改進(jìn)后的A星算法的可行性和有效性。經(jīng)過(guò)本篇論文第四章仿真實(shí)驗(yàn)驗(yàn)證證明:以最小二叉堆存儲(chǔ)OPEN表中的數(shù)據(jù),使A星算法的尋徑效率提高了10%。以經(jīng)過(guò)過(guò)濾的向量?jī)?nèi)積值作為啟發(fā)函數(shù)在估價(jià)函數(shù)中的比重值,使算法在尋徑質(zhì)量保持不變的同時(shí),A星算法的尋徑效率至少提高了5.2倍,遍歷的頂點(diǎn)數(shù)至少減少了57%,極大的提高了尋徑效率。經(jīng)過(guò)仿真實(shí)驗(yàn)證明,優(yōu)化后的算法達(dá)到了預(yù)期的效果。
[Abstract]:With the advent of the network era and the increasing expansion of the city scale, people often query the route of travel before they travel. At present, there are many kinds of travel route query systems, but the high quality trip route query function still needs to be improved. It is also necessary to optimize the path search algorithm of the trip route. A star algorithm is one of the most widely used urban trip path search algorithms. It is a heuristic search algorithm, and its evaluation function is: F (n) G (n) H (n), where G (n) denotes the actual value of the distance from the starting vertex to the current vertex and H (n) denotes the estimate of the distance from the current vertex to the target vertex. The result of the sum of the two is the estimated value of the valuation function, and the lowest vertex is chosen as the next selected vertex, so that the evaluation function is cycled and the optimal path is generated. Combined with practical application, this paper improves the standard A algorithm in two aspects as follows: using least square stack technology to optimize the search speed of 0PEN table and improve the efficiency of path finding. For the valuation function of the A-star algorithm, the author improves the function in the following aspects: 1. Select the appropriate heuristic function. 2. Increase the proportion of the heuristic function in the valuation function. The value of vector inner product is used to improve the proportion of heuristic function in valuation function. The filter inner product value further optimizes the evaluation function. Thus reducing the number of vertices traversing in the process of tracing, while ensuring that the overall quality of the path searching remains unchanged, the efficiency of tracing is greatly improved. In this paper, the path search algorithms of standard A star and improved A star are implemented in C language on the Visual Studio 2010 development platform. On this basis, their path searching length, seeking time and the number of vertices traversing in the path searching process are counted. The feasibility and effectiveness of the improved A-star algorithm are verified. In the fourth chapter of this paper, the simulation results show that using the least square stack to store the data in open table can improve the path finding efficiency of the A-star algorithm by 10%. Taking the filtered inner product of vector as the specific gravity value of the heuristic function in the evaluation function, the algorithm improves at least 5.2 times the searching efficiency of the A star algorithm while keeping the quality of the path finding constant, and using the value of the filtered inner product of the vector as the value of the specific gravity in the evaluation function. The number of ergodic vertices is reduced by at least 57 points, which greatly improves the path finding efficiency. The simulation results show that the optimized algorithm achieves the desired results.
【學(xué)位授予單位】：華僑大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：U495

【參考文獻(xiàn)】

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

1 姜桂艷;鄭祖舵;白竹;趙佳琪;代磊磊;;基于記憶機(jī)制的動(dòng)態(tài)交通路徑優(yōu)化算法[J];吉林大學(xué)學(xué)報(bào)(工學(xué)版);2007年05期

2 朱靜;Dijkstra算法在GIS中的優(yōu)化實(shí)現(xiàn)[J];計(jì)算機(jī)與現(xiàn)代化;2005年09期

3 唐文武,施曉東,朱大奎;GIS中使用改進(jìn)的Dijkstra算法實(shí)現(xiàn)最短路徑的計(jì)算[J];中國(guó)圖象圖形學(xué)報(bào);2000年12期

，

本文編號(hào)：2059883