【摘要】：概括了當(dāng)前GIS中最短路徑算法,分析了元胞自動機在最短路徑分析算法中的原理及應(yīng)用現(xiàn)狀,并從兩個方面對基于元胞自動機的最短路徑算法進行優(yōu)化即直線優(yōu)化的元胞自動機最短路徑算法。(1)將A*算法中的啟發(fā)函數(shù)引入元胞自動機模型,提出了直線優(yōu)化元胞自動機最短路徑模型;(2)考慮道路網(wǎng)特征對最短路徑算法的影響,得出具有道路網(wǎng)自適應(yīng)性的最短路徑分析模型。最后選取不同形態(tài)特征的shp道路網(wǎng)數(shù)據(jù),驗證了優(yōu)化算法在實際應(yīng)用中的適用性和高效性。
【圖文】：

路信息，利用圖論理論尋求出指定節(jié)點間的最短路徑。CA最短路徑算法的思想就是在此基礎(chǔ)上將無向圖的所有頂點定義為一個元胞集合，與某一元胞連通的所有節(jié)點組成該元胞的鄰居集合，元胞狀態(tài)根據(jù)演化規(guī)則分為未被尋路和已被尋路等若干離散狀態(tài)。元胞初始狀態(tài)均為未被尋路，從起始元胞開始，依據(jù)演化規(guī)則，其鄰居元胞的狀態(tài)發(fā)生翻轉(zhuǎn)，在下一時刻相鄰的元胞又依據(jù)規(guī)則并行的向各自相鄰的節(jié)點演化，并記錄元胞的變化信息，以此類推，直到終點元胞被尋路，最先到達目標(biāo)節(jié)點的元胞演化記錄就是所求的最短路徑。以無向圖G(圖1)為例，構(gòu)造CA模型:A=(d，S，N，f)，式中:元胞空間d={v1，v2，…，vn};元胞vx鄰居為N(vx)={(vx，v)∈E∨(v，vx)∈E∨v=vx}。最短路徑算法建立的關(guān)鍵是制定元胞的演化規(guī)則，并根據(jù)規(guī)則確定元胞的狀態(tài)集合S。圖1無向圖GFig．1UndirectedgraphG學(xué)者針對元胞自動機在最短路徑算法中的應(yīng)用開展了廣泛而深入的研究，產(chǎn)生了一系列研究成果。吳曉軍和薛惠鋒(2004)對元胞自動機在最短路徑分析中的應(yīng)用進行了探索，利用元胞自動機在元胞空間上的并行特性，采用元胞動態(tài)鄰居、時間段自適應(yīng)調(diào)整的方法，構(gòu)造出一種新的基于元胞自動機擴展模型的圖最短路徑搜索算法，即通過簡單規(guī)則的元胞狀態(tài)演化，得到帶權(quán)圖的最短路徑。定義狀態(tài)集S={S_N，S_G，S_B，S_M};其中S_N表示初始狀態(tài)，未被搜尋;S_G表示該元胞正在被搜尋，處于生長狀態(tài);S_B表示元胞狀態(tài)正在向領(lǐng)導(dǎo)擴展，處于繁殖狀態(tài);S_M表示已經(jīng)被搜尋結(jié)束，處于成熟狀態(tài)。演化規(guī)則f設(shè)定為:假設(shè)t時刻，中心元胞為vx，剩余權(quán)(中心元胞到起始元胞的最短距離)記為r(vx)。(1)若vx為S_M狀態(tài)，表示該點已被搜尋，狀態(tài)不變。(2)?

(1)當(dāng)中心元胞vx的狀態(tài)為S_N時，考察鄰居:若鄰居存在S_B狀態(tài)，，則翻轉(zhuǎn)為S_G，且r(vx)=w(vn，vx)+g(vx);否則狀態(tài)不變，且r(vx)=∞。(2)當(dāng)中心元胞vx狀態(tài)為S_M時，狀態(tài)不變。(3)當(dāng)中心元胞vx狀態(tài)為S_B時，翻轉(zhuǎn)為S_M。(4)當(dāng)中心元胞vx狀態(tài)為S_G時，考察鄰居:若鄰居存在S_B狀態(tài)且g(vx)+wt－1(vn，vx)＜r(vx)，則r(vx)=g(vx)+wt－1(vn，vx);若r(vx)－min(r(vx))=0則狀態(tài)翻轉(zhuǎn)為S_B，否則狀態(tài)不變。優(yōu)化算法與原算法的元胞演化域的比較如圖2所示。圖2優(yōu)化前與優(yōu)化后基于CA的最短路徑算法演化域Fig．2OptimizationbeforeandaftertheoptimizationoftheshortestpathalgorithmbasedontheCAevolutiondomain
【作者單位】： 信息工程大學(xué)測繪學(xué)院;
【分類號】：P208;U495

【參考文獻】

相關(guān)期刊論文 前2條

1 王海梅;周獻中;;直線優(yōu)化A~*算法在最短路徑問題中的改進與實現(xiàn)[J];工程圖學(xué)學(xué)報;2009年06期

2 吳曉軍,薛惠鋒;基于元胞自動機擴展模型的圖的最短路徑算法[J];計算機應(yīng)用;2004年05期

【共引文獻】

相關(guān)期刊論文 前10條

1 周康;殷燕芳;解智;魏傳佳;;城市交通優(yōu)化中基于對偶算法的元胞自動機[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2010年01期

2 吳曉軍,薛惠鋒,雒雪芳,丁曉陽;元胞自動機生成城市空間影響區(qū)的方法[J];計算機工程與應(yīng)用;2005年27期

3 張俊溪;薛惠鋒;蘇錦旗;;基于CA模型的凝固聚類算法[J];計算機工程與應(yīng)用;2008年23期

4 吳小蘭;王忠群;劉濤;王勇;;基于擴展元胞自動機的在線零售站點的自適應(yīng)[J];計算機應(yīng)用;2006年10期

5 韓瑋;;游戲中路徑搜索算法研究[J];計算機與現(xiàn)代化;2012年10期

6 周明;王韓民;吳曉軍;;基于元胞自動機的距離變換方法[J];陜西師范大學(xué)學(xué)報(自然科學(xué)版);2006年02期

7 錢鑫;吳曉軍;張?zhí)鹛?易宇;;求解關(guān)鍵路徑的元胞自動機算法[J];陜西師范大學(xué)學(xué)報(自然科學(xué)版);2009年06期

8 丁曉陽;郭曉亭;;基于元胞自動機的單源點最短路求解算法[J];陜西師范大學(xué)學(xué)報(自然科學(xué)版);2013年03期

9 孫強;戴志軍;;用元胞自動機求最短路徑的一種新算法[J];計算機技術(shù)與發(fā)展;2009年02期

10 李a\;薛惠鋒;吳曉軍;;改進的基于元胞自動機擴展模型的圖的最短路徑算法[J];微計算機應(yīng)用;2006年03期

相關(guān)博士學(xué)位論文 前3條

1 吳曉軍;復(fù)雜性理論及其在城市系統(tǒng)研究中的應(yīng)用[D];西北工業(yè)大學(xué);2005年

2 陳焰;ETO型機械制造企業(yè)項目管理的資源優(yōu)化方法及應(yīng)用研究[D];武漢理工大學(xué);2009年

3 廖遠;一對一最短路徑算法研究及車載導(dǎo)航系統(tǒng)設(shè)計[D];南昌大學(xué);2012年

【二級參考文獻】

相關(guān)期刊論文 前9條

1 王海梅;周獻中;;網(wǎng)絡(luò)系統(tǒng)中的最短路徑分析及其應(yīng)用研究[J];兵工學(xué)報;2006年03期

2 嚴(yán)寒冰,劉迎春;基于GIS的城市道路網(wǎng)最短路徑算法探討[J];計算機學(xué)報;2000年02期

3 陳則王,袁信;基于分層分解的一種實時車輛路徑規(guī)劃算法[J];南京航空航天大學(xué)學(xué)報;2003年02期

4 樂陽,龔健雅;Dijkstra最短路徑算法的一種高效率實現(xiàn)[J];武漢測繪科技大學(xué)學(xué)報;1999年03期

5 陸鋒,周成虎,萬慶;基于層次空間推理的交通網(wǎng)絡(luò)行車最優(yōu)路徑算法[J];武漢測繪科技大學(xué)學(xué)報;2000年03期

6 陸鋒,盧冬梅,崔偉宏;交通網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法[J];中國圖象圖形學(xué)報;1999年10期

7 陸鋒,盧冬梅,崔偉宏;基于四叉堆優(yōu)先級隊列及逆鄰接表的改進型Dijkstra 算法[J];中國圖象圖形學(xué)報;1999年12期

8 唐文武,施曉東,朱大奎;GIS中使用改進的Dijkstra算法實現(xiàn)最短路徑的計算[J];中國圖象圖形學(xué)報;2000年12期

9 王開義,趙春江,胥桂仙,宋曉宇;GIS領(lǐng)域最短路徑搜索問題的一種高效實現(xiàn)[J];中國圖象圖形學(xué)報;2003年08期

【相似文獻】

相關(guān)期刊論文 前10條

1 胡于杰;李響;;利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍[J];地理與地理信息科學(xué);2010年03期

2 魏二虎;賈滿;李林燕;;最短路徑算法的改進方法研究[J];測繪信息與工程;2007年04期

3 咼維;龔健雅;朱欣焰;;一種基于層次拓?fù)淠Ｐ偷姆植际阶疃搪窂剿惴╗J];武漢大學(xué)學(xué)報(信息科學(xué)版);2009年07期

4 沙宗堯;邊馥苓;;單源最短路徑算法的圖示教學(xué)設(shè)計與實踐[J];測繪通報;2010年04期

5 解德祥;蔣廷耀;;最短路徑算法在GIS中的應(yīng)用與分析[J];科技信息(科學(xué)教研);2007年17期

6 陳珊;張淑驊;石峰;;基于GIS最短路徑算法的改進和應(yīng)用[J];科技資訊;2006年04期

7 況蔚林;;GIS領(lǐng)域最短路徑算法初探[J];科技信息(學(xué)術(shù)研究);2008年10期

8 郭v

本文編號：2542472