基于嵌入式模擬器的路徑詢優算法的實現

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

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

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

1 嵌入式模擬器

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

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

2 A*算法

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

3 算法設計與實現

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

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

圖1 地圖數據組織結構Fig.1 Framewok of map data organization

3.1 建立地圖的拓撲結構

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

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

3.2 道路網預處理算法

3.3 路徑搜索算法

4 結果分析

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

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

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

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

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

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

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

算法讀取西安市部分地區道路網數據，總節點數為6 432，道路數為1 274，交點數為1 185，結果如表1所示。

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

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

5 結 論

實驗結果表明，在嵌入系統有限的資源條件下，A*算法具有很好的穩定性和適應性。采用啟發式搜索算法，選取不同的啟發因子，對結果路徑影響很大。根據不同領域對反應速度和路徑距離的需求，設定不同的g和h值，可以得到所需要的結果。算法的計算量與地圖的拓撲結構、起始點、終點和啟發因子有關[6]。在選定了具體的道路網和起始點后，選取合適的g和h是至關重要的。

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

[2]張冬泉.Windows CE實用開發技術[M].北京：電子工業出版社，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.