趙 佳，胡 燕，來炳恒，王 瑞

（西安建筑科技大學 信息與控制工程學院，陜西 西安710055）

在地理信息系統(tǒng)中，最優(yōu)路徑是一個很重要的問題。快速求解道路網(wǎng)兩節(jié)點間的最短路徑，應考慮道路網(wǎng)本身的特點。在圖論中求解最短路徑最著名的是Dijkstra算法[1]。該算法是基于圖論中的網(wǎng)絡模型，在求解時有可能并準備搜索所有的網(wǎng)絡節(jié)點，算法的時間復雜度為O（N2），N為網(wǎng)絡節(jié)點數(shù)。顯然，在擁有大量節(jié)點的城市道路網(wǎng)中，該算法運算量太大，難以滿足用戶要求。從幾何學中知道，兩點間線段最短。在道路網(wǎng)圖中，從起點開始，如果每次取與終點直線距離最短的節(jié)點為新的節(jié)點開始搜索，則這條路徑是最短路徑的可能性也較大。本文采用A*搜索算法，充分考慮當前搜索點與終點間距離所帶來的影響。實驗表明，引入這個因子后，算法搜索空間小，求解速度快。

1 嵌入式模擬器

嵌入式平臺構建于微軟的Windows CE系列操作系統(tǒng)之上，微軟按主要智能設備、自身硬件設備特性的不同以及用戶體驗的差異，定制出了Windows CE.NET 4.x系列操作系統(tǒng)的兩個主要分支，分別安裝在不同的嵌入式硬件設備中，從而也就構成了我們通常所說的Pocket PC和Smartphone。Pocket PC最大的特點是將熟悉的 Windows桌面擴展到了移動設備中，這使得基于嵌入式的電子地圖系統(tǒng)更方便普通用戶的使用。

為正確實現(xiàn)路徑詢優(yōu)算法，系統(tǒng)需安裝eMbedded Visual C++4.0，Microsoft Pocket PC 2003 SDK.msi，Pocket PC 2003 SDK Chinese Simplified Emulation Images.msi等輔助開發(fā)軟件[2]。在模擬器上部署Pocket PC應用程序，并在模擬器上安裝Microsoft.NET Compact Framework，接著會下載并啟動智能應用程序×.exe。

2 A*算法

A*算法[3]是人工智能中一種典型的啟發(fā)式搜索算法，通過在狀態(tài)空間中的搜索,對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。啟發(fā)中的估價是用估價函數(shù)表示的，如： f（n）=g（n）+h（n）。 其中 f（n）是節(jié)點n的估價函數(shù)，g（n）是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h（n）是從n到目標節(jié)點最佳路徑的估計代價。g（n）是已知的,它代表了搜索廣度的優(yōu)先趨勢。當h（n）遠大于 g（n）時，可以省略 g（n），而提高效率。

3 算法設計與實現(xiàn)

數(shù)字電子地圖采用MapInfo公司提供的電子地圖數(shù)據(jù)格式。每張單獨的地圖都被表示成單獨的一個圖層，所有的圖層存儲在layers集合中，如圖1所示。

Layers[4]合由Layer對象組成，按順序編號為0到n。Layer對象由features對象組成，features對象又是由Feature對象組成，對應于地圖中的點、線、區(qū)域或符號。最上面一層為Layers（1），Layers（2）位于 Layers（1）的下面，以次類推。 最下面的圖層最先繪制，最上面的圖層最后繪制。

圖1 地圖數(shù)據(jù)組織結構Fig.1 Framewok of map data organization

3.1 建立地圖的拓撲結構

在MapInfo電子地圖格式中，公路或街道都是以實體的形式存儲。線圖元是以一組節(jié)點坐標（xi，yi）存儲的，同一條道路相鄰結點之間的連線近似為直線。節(jié)點坐標和道路名稱分別保存在MIF和MID文件中。通過讀取文件的操作，可以獲取地圖上數(shù)據(jù)點的信息。為此，定義如下的數(shù)據(jù)結構：

其中，RoadNum為道路編號，NodeNum為節(jié)點編號，IsJunction為布爾型變量，判斷該節(jié)點是否為道路交點。Lon，Lat為節(jié)點的經(jīng)緯度。Parent定義節(jié)點的父節(jié)點；Child[n]定義節(jié)點出度。

3.2 道路網(wǎng)預處理算法

3.3 路徑搜索算法

4 結果分析

由 A* 算法的基本因子 f（n）=g（n）+h（n），h（n）的信息性其實是在估計一個節(jié)點的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點就越多，估價函數(shù)越好或說這個算法越好。選取適當?shù)膆（n）對結果影響很大。在廣度優(yōu)先算法中h（n）=0，沒有任何啟發(fā)信息。在對實時性要求較高的條件下，充分利用h（n）的信息性[5]是很重要的。采用A*算法，分別定義不同的g（n）和h（n）在西安市道路網(wǎng)中搜索出來的路徑如圖2所示。

圖2 算法1～5搜索的結果Fig.2 Result of algorithm1～5

算法 1：g（n）為已經(jīng)走過的代價，h（n）為當前點與終點間的距離；

算法 2：g（n）為走過的代價，h（n）＝0；

算法 3：g（n）為節(jié)點深度，h（n）為當前點與終點間的距離；

算法 4：g（n）為節(jié)點深度，h（n）＝0；

算法 5：g（n）＝0，h（n）為當前點與終點間距離。

算法讀取西安市部分地區(qū)道路網(wǎng)數(shù)據(jù)，總節(jié)點數(shù)為6 432，道路數(shù)為1 274，交點數(shù)為1 185，結果如表1所示。

算法2，4啟發(fā)因子為0，耗費時間分別為12 506 ms和7 856 ms最多。h（n）的信息越少，它的計算量就越大，耗費的時間就越多。但算法2可以得到理論上最短路徑。算法4目標路徑中節(jié)點數(shù)最少，實際中即為道路的轉(zhuǎn)折點最少。算法5只考慮啟發(fā)因子耗費時間最少，搜索最快，但最終路徑節(jié)點數(shù)也最多。算法1綜合考慮了g和h，搜索節(jié)點數(shù)，目標路徑節(jié)點數(shù)和耗費時間均屬于中等。算法3綜合考慮了節(jié)點深度和搜索當前點與目標點的距離。由結果可知，啟發(fā)因子h對搜索算法的復雜度有很大的影響，如果信息越多或約束條件越多則排除的節(jié)點就越多，估價函數(shù)越好，搜索速度更快。

表1 5種不同啟發(fā)因子的比較結果Tab.1 Comparison result of five different elicitation factors

5 結 論

實驗結果表明，在嵌入系統(tǒng)有限的資源條件下，A*算法具有很好的穩(wěn)定性和適應性。采用啟發(fā)式搜索算法，選取不同的啟發(fā)因子，對結果路徑影響很大。根據(jù)不同領域?qū)Ψ磻俣群吐窂骄嚯x的需求，設定不同的g和h值，可以得到所需要的結果。算法的計算量與地圖的拓撲結構、起始點、終點和啟發(fā)因子有關[6]。在選定了具體的道路網(wǎng)和起始點后，選取合適的g和h是至關重要的。

[1]許卓群.數(shù)據(jù)結構與算法 [M].北京：高等教育出版社，2004.

[2]張冬泉.Windows CE實用開發(fā)技術[M].北京：電子工業(yè)出版社，2006.

[3]王萬良.人工智能及其應用[M].北京：高等教育出版社，2006.

[4]MapInfo Corporation.MapX mobile 5.05 developer guide[Z].MapInfo Corporation，2006.

[5]Fawcett J，Robinson P.Adaptive routing for road traffic[J].IEEE Computers Graphics and Applications，2000，20 （3）:26-53.

[6]ZHAN F B.Three fastest shortest path algorithms on real road networks[J].Journal of Geographic Information and Decision Analysis，1997，1（1）:69-82.