基于路網(wǎng)分層的多級(jí)搜索算法的研究與實(shí)現(xiàn).pdf

1、近年來(lái)，智能交通系統(tǒng)(ITS)、車載GPS定位系統(tǒng)、城市交通誘導(dǎo)系統(tǒng)等相關(guān)地理信息系統(tǒng)(GIS)技術(shù)的廣泛應(yīng)用對(duì)電子地圖搜索服務(wù)提出了更高的要求。因此，對(duì)電子地圖搜索及其相關(guān)領(lǐng)域的研究已變得炙手可熱。 本文研究了電子地圖搜索服務(wù)中的一個(gè)核心議題：最短路徑問(wèn)題求解。擁有海量數(shù)據(jù)是GIS系統(tǒng)的一個(gè)顯著特點(diǎn)，合理地提取、組織、分析和處理電子地圖數(shù)據(jù)是提高尋徑效率的關(guān)鍵。傳統(tǒng)最短路徑問(wèn)題的研究更多地注重算法的改進(jìn)和優(yōu)化，或者是基于少量地

2、圖數(shù)據(jù)的尋徑系統(tǒng)的實(shí)現(xiàn)；本文則側(cè)重于海量數(shù)據(jù)下的尋徑及其性能優(yōu)化，提出基于路網(wǎng)分層的多級(jí)搜索算法，實(shí)現(xiàn)了全美國(guó)的Door2Door(門牌號(hào)到門牌號(hào))尋徑系統(tǒng)。其主要研究工作如下： 1.提出基于路網(wǎng)分層的多級(jí)搜索算法，并比較幾種傳統(tǒng)尋徑算法的優(yōu)劣，選擇了適合GIS中大數(shù)據(jù)量尋徑的A*算法作為其通用最短尋徑算法； 2.將分層思想引入路網(wǎng)數(shù)據(jù)組織，從地圖數(shù)據(jù)中提取出需要的數(shù)據(jù)通過(guò)分層、合并、簡(jiǎn)化等方式組織成特定的道路數(shù)據(jù)文件，

3、并建立路網(wǎng)數(shù)據(jù)庫(kù)； 3.通過(guò)實(shí)驗(yàn)得出了適用于全美尋徑系統(tǒng)的A*算法的估價(jià)函數(shù)的加權(quán)模型；以此為基礎(chǔ)提出了基于海量數(shù)據(jù)下的各種尋徑策略，并討論其具體實(shí)現(xiàn)的細(xì)節(jié)問(wèn)題； 4.討論尋徑中的必備工具--RTree模塊，研究TIGER數(shù)據(jù)和Shape文件的組織格式； 5.基于前面的研究實(shí)現(xiàn)了一個(gè)實(shí)用高效的尋徑系統(tǒng)。 全文主要對(duì)GIS尋徑問(wèn)題中海量數(shù)據(jù)的處理進(jìn)行了較為深入的探索并提出相應(yīng)的算法，并且初步實(shí)現(xiàn)了全美國(guó)的D