嵌入式gis系統(tǒng)中dijcke算法的優(yōu)化處理

嵌入式gis系統(tǒng)中dijcke算法的優(yōu)化處理

dijkat算法是荷蘭計算機科學家提出的最短路徑算法。這是圖論中最短路徑問題的經(jīng)典算法。為了計算兩點之間的最短路徑問題，使用了心理激勵策略。這是目前已知理論最完整、最廣泛使用的算法，具有很強的抗差性和穩(wěn)定性。但是經(jīng)典Dijkstra算法在搜索過程中由于缺乏方向性,即使在找到終點時結(jié)束算法,仍然有大量的冗余計算,在實際應(yīng)用中也有一定的難度.因此自Dijkstra算法提出以來,眾多科研人員就最短路徑問題提出了很多改進方法.過去的研究主要集中在基于數(shù)據(jù)存儲結(jié)構(gòu)的優(yōu)化(采用鄰接表、十字鏈表等)限制搜索區(qū)域(陸峰在1999年提出的橢圓限制搜索區(qū)域)以及優(yōu)化優(yōu)先級隊列結(jié)構(gòu)(基于堆結(jié)構(gòu)和桶結(jié)構(gòu))方面.筆者提出了針對單源單匯點的最短路徑算法,先限制搜索區(qū)域來減少計算量,再根據(jù)城市道路的特點修改存儲結(jié)構(gòu),并將它應(yīng)用到GIS決策系統(tǒng)中以檢驗其實際效果.1西jkas官僚的sspp算法1.1d[n]求解Dijkstra算法是一種比較-添加模型,它將結(jié)點分成三部分——未標記、永久標記和臨時結(jié)點.設(shè)圖G(V,E),w為權(quán)值.算法將V分成S和T2個子集,S存放永久標記結(jié)點,T=V-S,表示目前還沒有計算的結(jié)點.d[N]是長度為N的一維數(shù)組,用來存放從源點到其他結(jié)點的最短路徑長度.求解從源點s到i的最短路徑的過程如下:(1)初始化,S={},T=V;(2)構(gòu)建圖的鄰接矩陣為Neighbour[N][M],其中,N為結(jié)點數(shù),M為最大鄰接結(jié)點數(shù).并根據(jù)Neighbour[N][M]來初始化d[N];(3)從d[N]中選擇最小的元素,并假設(shè)此結(jié)點編號為i;(4)將結(jié)點i放到S中,并從T中刪除;利用結(jié)點i來更新d[N]數(shù)組:其中,judge[i][j]為判斷矩陣,它的值可參照矩陣Neighbour[N][M]來獲得.(5)重復(3)和(4),循環(huán)結(jié)束條件為T={}.1.2資源費過多且存在地域差異從上述Dijkstra算法流程中可見,直接影響算法的速度是頂點集V的大小.由于步驟(3)和步驟(4)是個循環(huán)比較過程,此時如果不經(jīng)任何處理就選擇1個權(quán)值最小的結(jié)點,那么算法就必須掃描頂點集V中所有的結(jié)點.此時,整個算法的時間復雜度為O(N2),對于嵌入式系統(tǒng)來說,資源耗費過多.其次,由于傳統(tǒng)Dijkstra算法獲得的最短路徑上的結(jié)點是無序的,而對于嵌入式GIS系統(tǒng)中的用戶來說,要求看到的是能在圖上顯示的路徑,也就說必須是有序的.而在實際應(yīng)用中,由于城市的道路網(wǎng)絡(luò)異常復雜,用戶的指令也實時產(chǎn)生,并且往往隨機和不確定地定義起點和終點.因此,此時經(jīng)典Dijkstra算法就無法滿足這些需求,但單源單匯點算法就較為適合這些要求.2改進的dijkstra算法2.1最短路徑電商及其獲取步驟由Jonson算法可知,在計算兩點間的最短路徑時,無需遍歷搜索整個道路網(wǎng)絡(luò),而只需搜索局部的道路網(wǎng)絡(luò)就可得到它們間的最短路徑.因此,此時可通過預處理結(jié)點集合,來進一步縮小結(jié)點集合的范圍以提高算法效率.而橢圓模型是控制路網(wǎng)規(guī)模算法中最常用的一種.定理假設(shè)圖G(V,E),S為源點,D為終點(S,D∈V).對于G中結(jié)點i到S和D的歐式距離分別為SI和DI,則SI+DI≤M,其中,M為最短路徑對應(yīng)的大致極限距離(圖1).顯然,I的軌跡正好形成了一個以S和D為焦點,M為長軸的橢圓,因此搜索區(qū)域只需考慮橢圓范圍之內(nèi)即可.而本文中的M是針對杭州市城市道路網(wǎng)絡(luò)情況,其獲取步驟如下:(1)選取典型的城市道路區(qū)域網(wǎng)絡(luò),構(gòu)造2個結(jié)點集合1T,2T.其中,C中的元素(t1,t2)是待求最短路徑的起始點和目的地對.(2)計算C中每個元素結(jié)點對間的歐氏距離Eij以及最短路徑長度Dij,此時的比值系數(shù)集合(3)對R進行分析后求得δ,并且使得R的總數(shù)滿足置信水平閥值?,?=0.95即表明在橢圓內(nèi)找到全局最短路徑的可能性≥95%.則橢圓的長軸M為M=δ?Eij,Rij<δ.(4)對于(xi,yi),(xj,yj)兩點,得到限制橢圓方程為:其中,a,b分別為橢圓中心位置坐標;φ為x軸正方向與橢圓長軸的夾角;A,B分別代表橢圓的長半軸和短半軸.2.2第5類:節(jié)點前趨功能由于Dijkstra算法不對求出的結(jié)點進行排序此時可引入前趨表的概念.前趨表(hprtable)主要由頭結(jié)點和它的n個鏈表組成,其中的n為路網(wǎng)結(jié)點數(shù),其結(jié)構(gòu)如圖2所示.圖2中的1,…,n為結(jié)點編號,Vi,Vj為直接前趨結(jié)點(0≤i,j<n,n為結(jié)點總數(shù)),next為指向下個直接相連的結(jié)點指針.此時的前趨表中存儲了目前路徑上結(jié)點的所有直接前趨,因此只需沿著終點就能找到它的直接前趨結(jié)點,最后直至源點.此過程就能順利地解決一條按順序進行排序的最短路徑上的結(jié)點集.而圖3(a)為道路節(jié)點網(wǎng)絡(luò),圖3(b)則為其對應(yīng)的前驅(qū)圖.這樣,利用前趨表可以很方便地求出V1至V6的最短路徑(V1,V3,V5,V6).2.3生成新的前趨結(jié)論設(shè)前趨表為hpr,源點為sV,終點為dV,改進的算法步驟如下:(1)利用2.1劃定源點至終點的橢圓搜索區(qū)域,判斷條件可放寬至橢圓的外接矩形.橫坐標的取值范圍為:縱坐標的取值范圍為:(2)將源點sV放入永久標記集合S中,計算出所有結(jié)點的distance屬性值,如果kVdistance≠∞,那么hpr[k]此時僅有1個直接前趨值V0,否則pr[k]=∧(0<k≤n-1);(3)如果當前處理的結(jié)點即為終點,或者S中結(jié)點的范圍超出步驟(1)的取值范圍,則算法退出;(4)選擇剩余結(jié)點中distance最小的結(jié)點k,并將其標記為永久結(jié)點,放入S中;(5)如dist[i]>dist[k]+cost[i][k],則刪除pr[i]中所有的直接前趨,建立新的直接前趨結(jié)點k;如果dist[i]=dist[k]+cost[i][k],則直接把結(jié)點k插入到pr[i]中.綜上所述,較之經(jīng)典的Dijkstra算法,改進算法能大大減少搜索范圍,減少執(zhí)行的時間.3原實驗數(shù)據(jù)及搜索結(jié)果分析在嵌入式GIS系統(tǒng)中應(yīng)用上述算法,運行環(huán)境如下:WindowsCE操作系統(tǒng),Pentium4CPU3.60GHz,2G內(nèi)存.地圖選用杭州市市區(qū)圖,相關(guān)坐標為北京54坐標系,1:10000的地籍數(shù)據(jù)采集,其中總共包含3982個道路交點.表1中的原采集坐標數(shù)據(jù)精確到小數(shù)點后13位,而文中取值精確到小數(shù)點后2位.Nsd為經(jīng)典Dijkstra算法實際標記的結(jié)點數(shù),Nsd’為改進算法實際標記的結(jié)點數(shù),Tsd為Dijkstra算法所需時間,Tsd’為改進算法所需時間.而表1中的(80.76,82.68)到(82.01,81.65)由于算法沒有在限制的范圍內(nèi)找到通路,因此造成改進算法運算時間反而增加.對于落在橢圓范圍內(nèi)的結(jié)點對而言,搜索范圍基本上小于原來算法的1/4(平均可達到0.235左右).但是由于道路網(wǎng)絡(luò)實際分布上的差異,勢必會造成某些樣本的