a算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用

《a算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用劉浩,鮑遠(yuǎn)律(中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系，安徽合肥230027)摘要:A*算法是啟發(fā)式搜索算法的一種，廣泛應(yīng)用于圖搜索和路徑規(guī)劃。本文簡(jiǎn)要介紹了A*算法，并通過(guò)對(duì)A*算法可接納性和一致性的分析，說(shuō)明了A*算法是一類適合矢量地圖最優(yōu)路徑搜索的較好算法。關(guān)鍵詞:最優(yōu)路徑，A*算法，矢量地圖，GISA*AlgorithmfortheShortestPathonVectorMapsLIUHao，BAOYuanlu(DepartmentofAutomation,UniversityofScienceandTechnologyofChin

2、a,HefeiAnhui230027)【Abstract】A*algorithmisoneofheuristicsearchalgorithms,whichcommonlyusedingraphsearchandpathplan.ThisthesisintroducesA*algorithmbriefly.ThroughtheanalysisofadmissibilityandconsistencyofA*algorithm,theauthorillustratesthatA*algorithmisakindoffairlygoodalgorithmsuitab

3、leforvectormaps.【Keywords】optimalpath,A*algorithm,vectormap,GIS1問(wèn)題的由來(lái)求解最短路徑問(wèn)題的首選算法，同時(shí)也是經(jīng)典算法，最優(yōu)路徑問(wèn)題是一個(gè)很古老的問(wèn)題，其原型是其優(yōu)勢(shì)在于求解單個(gè)頂點(diǎn)到其余所有頂點(diǎn)間的最優(yōu)運(yùn)籌學(xué)中的最短路徑間題，目前在互聯(lián)網(wǎng)的尋址計(jì)路徑，但用以求解單對(duì)頂點(diǎn)間的最優(yōu)路徑問(wèn)題時(shí)必算、智能交通系統(tǒng)，地理信息系統(tǒng)等領(lǐng)域有著廣泛然產(chǎn)生冗余，故不是一個(gè)應(yīng)用到實(shí)際路徑尋優(yōu)的較的應(yīng)用?，F(xiàn)代意義上的最優(yōu)路徑已不再僅僅是指地好算法?；趩l(fā)式搜索的A*算法，因其在路徑搜理意義上的距離最短，它還可以是指時(shí)

4、間最少、費(fèi)索過(guò)程中對(duì)問(wèn)題域信息的充分利用，使得搜索的目用最省、線路容量最大等等。但無(wú)論采用何種標(biāo)準(zhǔn)，標(biāo)性更加明確，是求解單對(duì)頂點(diǎn)間最優(yōu)路徑的一類最優(yōu)路徑問(wèn)題都可歸結(jié)為在帶權(quán)網(wǎng)絡(luò)中尋找最短路較好算法。[1～5]徑的研究，即圖論中的最短路徑問(wèn)題。2最優(yōu)路徑的研究現(xiàn)狀隨著信息科學(xué)的發(fā)展,地理信息系統(tǒng)(GIS)廣泛最優(yōu)路徑問(wèn)題的本質(zhì)是路徑搜索。從搜索算法應(yīng)用于人們生產(chǎn)和生活的各個(gè)領(lǐng)域，在各類的GIS的實(shí)時(shí)性的角度可以分為兩類：靜態(tài)最優(yōu)路徑和動(dòng)應(yīng)用中，交通地理信息系統(tǒng)(GIS-T)又是其中的一個(gè)態(tài)最優(yōu)路徑。前者在路徑尋優(yōu)的過(guò)程中路徑的權(quán)值熱點(diǎn)研究領(lǐng)域。當(dāng)代世界各發(fā)達(dá)國(guó)家和

5、部分發(fā)展中為定值，后者路徑的權(quán)值則可以根據(jù)交通狀況實(shí)時(shí)國(guó)家都在積極發(fā)展智能交通系統(tǒng)(ITS)，以緩解由于變化，以適應(yīng)動(dòng)態(tài)尋優(yōu)。雖然后者更能反應(yīng)實(shí)際的經(jīng)濟(jì)發(fā)展導(dǎo)致的出行需求增長(zhǎng)和由于交通智能化不情況，但是對(duì)交通環(huán)境的智能化要求也較高，即要夠?qū)е碌某鲂行枨蟛荒艿玫捷^好滿足之間的矛盾。求能夠?qū)崟r(shí)接收交通信息以更新路徑的權(quán)值。在國(guó)[1]在ITS所包含的6個(gè)高級(jí)交通系統(tǒng)中，有4個(gè)與外，動(dòng)態(tài)最優(yōu)路徑算法研究是的一個(gè)熱點(diǎn)，尤其是GIS-T支持下的交通網(wǎng)絡(luò)分析直接相關(guān)。交通網(wǎng)絡(luò)在一些發(fā)達(dá)國(guó)家。我國(guó)目前在交通網(wǎng)絡(luò)最優(yōu)路徑方分析的一個(gè)重要組成部分是路徑分析，而路經(jīng)分析面的研究主要還

6、是集中在靜態(tài)最優(yōu)路徑算法上，其的核心為最優(yōu)路徑算法。因此，對(duì)最優(yōu)路徑問(wèn)題的中一個(gè)重要原因在于我國(guó)的交通智能化水平不高，研究不但具有重要的理論價(jià)值,而且具有重要的應(yīng)限于人口、環(huán)境、經(jīng)濟(jì)發(fā)展等種種因素，我國(guó)的ITS用價(jià)值?？傮w上仍然還處在一個(gè)初級(jí)的發(fā)展階段。矢量地圖是大多數(shù)GIS應(yīng)用(如定位、導(dǎo)航、監(jiān)從問(wèn)題求解目標(biāo)的不同，可將搜索算法分為求控等等)的基礎(chǔ)，是對(duì)實(shí)際交通網(wǎng)絡(luò)拓?fù)涞囊粋€(gè)近似基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(60272040)反映。從而，我們可將在交通網(wǎng)絡(luò)分析中的最優(yōu)路作者簡(jiǎn)介：劉浩(1980-),男,碩士研究生,主研方向：智徑問(wèn)題的研究轉(zhuǎn)化為在矢量地圖

7、中求解最優(yōu)路徑算能交通網(wǎng)絡(luò)系統(tǒng)，最優(yōu)路徑；鮑遠(yuǎn)律,教授。法的研究。Dijkstra算法是目前GIS應(yīng)用領(lǐng)域用于E-mail：haohanliu@gmail.com解單源點(diǎn)多匯點(diǎn)的最優(yōu)路徑和所有頂點(diǎn)對(duì)之間的最[3]4A*算法的簡(jiǎn)介優(yōu)路徑。前者的典型代表如Dijkstra算法，后者的4.1算法的提出典型代表如Floyd算法。Nilsson曾開發(fā)一個(gè)通用的圖搜索算法。根據(jù)插入到OPEN表(一種表示已搜索到但尚未擴(kuò)展的節(jié)從搜索算法的是否具有智能性的角度，可將其點(diǎn)集合的數(shù)據(jù)結(jié)構(gòu))中的新產(chǎn)生節(jié)點(diǎn)重排方式的不分為兩大類，即盲目搜索和啟發(fā)搜索。前者如BFS同，這個(gè)圖搜索算法可以

8、演化成寬度優(yōu)先算法算法、