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

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

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

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