一种动态限制搜索区域的最短路径规划算法.doc
《一种动态限制搜索区域的最短路径规划算法.doc》由会员分享,可在线阅读,更多相关《一种动态限制搜索区域的最短路径规划算法.doc(8页珍藏版)》请在三一文库上搜索。
1、一种动态限制搜索区域的最短路径规划算法路径规划是智能交通系统研究的重要内容,是在车辆行驶前或行驶过程中为司机提供从起始点到目标点的一条或若干条路线,用来对司机的行车进行导航1。它一直是计算机科学、运筹学、交通工程学、地理信息学等学科的一个研究热点2,3。路径规划研究方面的专家学者追求的一个主要目标就是路径规划算法的实时性,即对于一个给定了起始点和目标点的特定路径规划问题,要在尽可能短的时间内给出规划后的路径。利用计算机进行路径规划时需要借助图论中的理论。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。由于这些算法主要诞生于计算机科学及运筹学领域,大多数算法
2、均存在一个问题:在设计过程中只考虑了抽象网络的拓扑特性,力求通过各种新型的计算机数据结构和运筹学方法,从理论上减少算法的时间复杂度,而忽略了具体网络可能具有的空间分布特性。 1算法原理 11道路网络的拓扑结构 最短路径算法设计与实现的基础是具有拓扑结构的道路网络4。在计算机中,具有拓扑结构的城市道路网络由节点、边及相应的拓扑关系构成。其中节点是道路的交叉点、端点,边是两节点间的一段道路。与普通的平面网络图相比,描述实际城市道路网络的拓扑图通常具有网络结构相对比较规则(特别是经过规划的现代大都市)的特点2,5。反映在实际道路网络中,相对比较规则指的是政府职能部门在进行城市总体规划时力图使道路布局
3、整齐,以提高行车质量和安全性6。 描述实际城市道路网络的拓扑图通常用邻接矩阵、邻接表、十字链表、邻接多重表等来表示。这几种图的存储结构比较如表17所示。 12经典Dijkstra算法 荷兰计算机科学家Dijkstra于1959年提出了经典Dijkstra算法。其基本思想是按节点距起始点距离递增顺序来产生最短路径,因此该算法在最短路径的搜索过程中具有很大的盲目性,随时都准备向其四面八方展开。这样,最终扫过的搜索区域基本上是以起始点为原点、起始点与目标点的欧氏距离为半径的一个圆,如图1中的圆2。 13椭圆限制搜索区域算法 椭圆限制搜索区域算法最早见于文献8。其基本思想如下:设网络中的一个点N到起始
4、点S和目标点G的直线距离分别为|SN|、|GN|,限制条件可以写成|SN|+|GN|M。显然,这正好形成了一个以S和G为焦点、以M为长轴的椭圆,如图1中的椭圆。在进行路径规划时,算法只考虑位于椭圆之内的节点,对位于椭圆之外的节点不予考虑。在椭圆限制搜索区域算法中,关键是求解合适的椭圆长轴M,以结合起始点、目标点的坐标构造限制椭圆。通常采用统计分析方法求解椭圆限制算法中的长轴M。其方法是:选定一块能够反映城市道路状况的区域,从这个区域中随机取点,分别放入集合A和B,将它们的笛卡尔乘积记为C,即C=AB=(a,b)|(aA)(bB)。所有在C中的元素都可以看成是待求最短路径的起始点和目标点,其直线
5、距离为e,两点间的最短路径为p,它们的比值r=p/e构成采样点的集合R。对这个集合进行统计分析就可以得出一个特定的系数,使得R中总数为满足95%置信水平的元素,其值不大于?怠缓罄?用这个系数作为乘系数,即可以通过起止点之间的距离得出椭圆的长轴长度M=|SG|3,9。以西安市电子地图为例,从4 525个点中分别随机各抽取30个点放入集合A、B中;经过笛卡尔乘积,C中就含有900对点;分别求取r,并对这900对点求算术平均值,可以得到?怠?1352,则M=|SG|=1352|SG|。 在椭圆限制算法中,一般给出的置信水平为95%,这表明在椭圆内找不到全局最短路径的可能性不大于5%。但即使是剩下的5
6、%不是全局最短路径,也至少是局部最短路径,所以一般认为这5%是完全可以忽略的9。 椭圆限制搜索区域算法将搜索节点集限制在椭圆内,大幅度缩小了最短路径算法的搜索规模。但是这种算法的缺点是在判断每个新扩展出的节点是否落在限定的椭圆内时需执行大量的乘积与开方计算,占用的时间较多。 14矩形限制搜索区域算法 针对椭圆限制搜索区域算法效率不高的缺点,陆锋等人提出矩形限制搜索区域算法。其基本思想为求出限制椭圆的最小包含矩形,矩形的四条边处于水平或是垂直方向,以此作为限制区域,减少算法的搜索规模,如图1中大的矩形。以椭圆的最小包含矩形作为限制搜索区域,对新扩展出的节点,判断其是否落在限制搜索区域内,只需将其
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 动态 限制 搜索 区域 路径 规划 算法
链接地址:https://www.31doc.com/p-1591966.html