基于嵌入式模擬器的路徑詢優(yōu)算法的實(shí)現(xiàn)

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

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

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

1 嵌入式模擬器

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

為正確實(shí)現(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應(yīng)用程序，并在模擬器上安裝Microsoft.NET Compact Framework，接著會(huì)下載并啟動(dòng)智能應(yīng)用程序×.exe。

2 A*算法

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

3 算法設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

3.1 建立地圖的拓?fù)浣Y(jié)構(gòu)

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

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

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

3.3 路徑搜索算法

4 結(jié)果分析

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

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

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

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

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

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

算法 5：g（n）＝0，h（n）為當(dāng)前點(diǎn)與終點(diǎn)間距離。

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

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

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

5 結(jié) 論

實(shí)驗(yàn)結(jié)果表明，在嵌入系統(tǒng)有限的資源條件下，A*算法具有很好的穩(wěn)定性和適應(yīng)性。采用啟發(fā)式搜索算法，選取不同的啟發(fā)因子，對(duì)結(jié)果路徑影響很大。根據(jù)不同領(lǐng)域?qū)Ψ磻?yīng)速度和路徑距離的需求，設(shè)定不同的g和h值，可以得到所需要的結(jié)果。算法的計(jì)算量與地圖的拓?fù)浣Y(jié)構(gòu)、起始點(diǎn)、終點(diǎn)和啟發(fā)因子有關(guān)[6]。在選定了具體的道路網(wǎng)和起始點(diǎn)后，選取合適的g和h是至關(guān)重要的。

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

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

[3]王萬(wàn)良.人工智能及其應(yīng)用[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.