基于嵌入式模拟器的路径询优算法的实现

赵 佳，胡 燕，来炳恒，王 瑞

（西安建筑科技大学 信息与控制工程学院，陕西 西安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.