一种动态限制搜索区域的最短路径规划算法摘要：提出一种动态限制搜索区域的最短路径规划算法，它是根据实际道路网络的空间分布特性，动态限制搜索区域，以降低算法的搜索规模，降低算法的时间复杂度和空间复杂度，提高算法的运行效率。实验证明，对于实际城市道路网络结构相对比较规则的最短路径规划，此算法极大地提高了规划的效率。关键词：动态限制搜索区域；最短路径规划算法；Dijkstra算法；道路网络：TP301．6文献标志码：A：1001－3695(2007)07－0089－03路径规划是智能交通系统研究的重要内容，是在车辆行驶前或行驶过程中为司机提供从起始点到目标点的一条或若干条路线，用来对司机的行车进行导航[1]。它一直是计算机科学、运筹学、交通工程学、地理信息学等学科的一个研究热点[2，3]。路径规划研究方面的专家学者追求的一个主要目标就是路径规划算法的实时性，即对于一个给定了起始点和目标点的特定路径规划问题，要在尽可能短的时间内给出规划后的路径。利用计算机进行路径规划时需要借助图论中的理论。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。由于这些算法主要诞生于计算机科学及运筹学领域，大多数算法均存在一个问题：在设计过程中只考虑了抽象网络的拓扑特性，力求通过各种新型的计算机数据结构和运筹学方法，从理论上减少算法的时间复杂度，而忽略了具体网络可能具有的空间分布特性。??1算法原理??1．1道路网络的拓扑结构??最短路径算法设计与实现的基础是具有拓扑结构的道路网络[4]。在计算机中，具有拓扑结构的城市道路网络由节点、边及相应的拓扑关系构成。其中节点是道路的交叉点、端点，边是两节点间的一段道路。与普通的平面网络图相比，描述实际城市道路网络的拓扑图通常具有网络结构相对比较规则(特别是经过规划的现代大都市)的特点[2，5]。反映在实际道路网络中，相对比较规则指的是政府职能部门在进行城市总体规划时力图使道路布局整齐，以提高行车质量和安全性[6]。??描述实际城市道路网络的拓扑图通常用邻接矩阵、邻接表、十字链表、邻接多重表等来表示。这几种图的存储结构比较如表1[7]所示。??1．2经典Dijkstra算法??荷兰计算机科学家Dijkstra于1959年提出了经典Dijkstra算法。其基本思想是按节点距起始点距离递增顺序来产生最短路径，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向其四面八方展开。这样，最终扫过的搜索区域基本上是以起始点为原点、起始点与目标点的欧氏距离为半径的一个圆，如图1中的圆[2]。??1．3椭圆限制搜索区域算法??---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---椭圆限制搜索区域算法最早见于文献[8]。其基本思想如下：设网络中的一个点??N到起始点S和目标点G的直线距离分别为|SN|、|GN|，限制条件可以写成|SN|+|GN|≤M。显然，这正好形成了一个以S和G为焦点、以M为长轴的椭圆，如图1中的椭圆。??在进行路径规划时，算法只考虑位于椭圆之内的节点，对位于椭圆之外的节点不予考虑。在椭圆限制搜索区域算法中，关键是求解合适的椭圆长轴??M，以结合起始点、目标点的坐标构造限制椭圆。通常采用统计分析方法求解椭圆限制算法中的长轴M。其方法是:选定一块能够反映城市道路状况的区域，从这个区域中随机取点，分别放入集合A和B，将它们的笛卡尔乘积记为C，即C=A×B={(a，b)|(a∈A)∧(b∈B)}。所有在C中的元素都可以看成是待求最短路径的起始点和目标点，其直线距离为e，两点间的最短路径为p，它们的比值r=p/e构成采样点的集合R。对这个集合进行统计分析就可以得出一个特定的系数，使得R中总数为满足95%置信水平的元素，其值不大于?怠Ｈ缓罄?用这个系数作为乘系数，即可以通过起止点之间的距离得出椭圆的长轴长度M=|SG|×??[3,9]。以西安市电子地图为例，从4525个点中分别随机各抽取30个点放入集合A、B中；经过笛卡尔乘积，C中就含有900对点；分别求取r，并对这900对点求算术平均值，可以得到?怠?1．352，则M=|SG|×??=1．352×|SG|。????在椭圆限制算法中，一般给出的置信水平为95%，这表明在椭圆内找不到全局最短...