地圖服務(wù)系統(tǒng)設(shè)計(jì)及路徑查找算法研究.pdf

1、在科技與經(jīng)濟(jì)日益交融，協(xié)調(diào)發(fā)展的現(xiàn)代社會(huì)，地圖服務(wù)技術(shù)的廣泛應(yīng)用深刻的影響著我們每天接觸到的各個(gè)領(lǐng)域。小范圍包括人們的定位搜索，交通出行和道路導(dǎo)航等，大范圍包括國(guó)家的物流運(yùn)輸，緊急救援和軍事行動(dòng)等。作為地理信息系統(tǒng)(GIS)學(xué)科的一部分，隨著電子計(jì)算機(jī)技術(shù)、人工智能技術(shù)和制圖渲染技術(shù)等的飛速發(fā)展與進(jìn)步，地圖服務(wù)技術(shù)也日趨發(fā)展成熟與完善。
　　地圖服務(wù)的主要功能是存儲(chǔ)、發(fā)布、組織和管理海量的空間數(shù)據(jù)，方便客戶端的在線查詢、檢索、分析

2、和下載等，使得各種實(shí)時(shí)實(shí)地的空間地理信息得以高效利用，滿足不同的現(xiàn)實(shí)需求。作為地圖服務(wù)系統(tǒng)的重要組成部分，因?yàn)椴粩嗤晟频膱D論理論和數(shù)據(jù)結(jié)構(gòu)，路徑查找功能逐步發(fā)展成為地圖服務(wù)的一個(gè)重要應(yīng)用，通過(guò)多種經(jīng)典路徑查找算法的相互結(jié)合，各種新的更切合實(shí)際的最短路徑查找算法不斷地被研究出來(lái)，特別是在算法步驟的易實(shí)現(xiàn)性、算法運(yùn)算的時(shí)間和空間復(fù)雜度以及算法結(jié)果的應(yīng)用范圍等方面各有進(jìn)展。
　　總體來(lái)說(shuō)，在地圖服務(wù)系統(tǒng)中，針對(duì)道路交通網(wǎng)絡(luò)的路徑查找問(wèn)題

3、有三種查找策略，分別是廣度優(yōu)先查找策略、深度優(yōu)先查找策略和啟發(fā)式查找策略。具體的幾種研究較成熟的經(jīng)典路徑查找算法主要包括Dijkstra算法和A*算法等。其中，Dijkstra算法是一種貪心算法，其基本原則是在進(jìn)行每一步的結(jié)點(diǎn)計(jì)算時(shí)都是通過(guò)選擇一個(gè)局部的最優(yōu)解以期得到一個(gè)最終總體的最優(yōu)解。而A*算法是一種先通過(guò)最大可能加載計(jì)算已知信息，向最有希望結(jié)點(diǎn)為查找目標(biāo)去查找的啟發(fā)式查找算法，這種查找策略在靜態(tài)路網(wǎng)中解決最短路問(wèn)題有很好的效果。<

4、br>　　本文對(duì)幾種經(jīng)典的路徑查找算法做了深入分析和研究，在分層路網(wǎng)的基礎(chǔ)上，考慮到實(shí)時(shí)實(shí)地的交通道路網(wǎng)絡(luò)中變量較多的情況，將道路屬性和路況信息等影響因子的不同權(quán)重值加載到路徑查找算法的計(jì)算公式中，通過(guò)算法計(jì)算得出不同的路徑優(yōu)先級(jí)，在每個(gè)計(jì)算結(jié)點(diǎn)處形成不同優(yōu)先級(jí)的路徑集。邊計(jì)算路徑優(yōu)先級(jí)，邊查找下一路徑，在減少路徑查找規(guī)模的同時(shí)，使得路徑查找計(jì)算的邏輯更加清晰。再結(jié)合項(xiàng)目背景和實(shí)際交通道路網(wǎng)絡(luò)的不同限制條件以及用戶不同的實(shí)際需求，計(jì)算出