改进型A*算法在物流配送网络中的应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇改进型A*算法在物流配送网络中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:A*算法是目前路径搜索中应用最广泛的算法,最短路径搜索算法效率是研究人员普遍关注的重点,本文在分析A*算法的基础上,重点介绍了一种改进型A*启发式搜索算法,实验结果表明:提出的改进方法极大地减少算法搜索区域,提高了算法的效率,更加适合交通网络的路径导航。
关键词:空间顺序关系;改进型A*算法;启发式搜索;优先级队列
中图分类号:TP393 文献标识码:A文章编号:1007-9599 (2010) 05-0000-02
Improved A* Algorithm in Logistics Distribution Networks
Li Ming,Tian Fengrui
(Computer Science&Information College of Guizhou University,Guizhou University,Guiyang550025,China)
Abstract:A* path search algorithm is the most widely used algorithms,efficiency of shortest path search algorithm is generally the focus of researchers,on the basis of A * algorithm,the article introduce an improved A * heuristic search algorithm,The experimental results show that:the proposed approach greatly reduce the algorithm search area and improve the efficiency,the algorithm is more suitable for the path of navigation of transportation network.
Keywords:Spatial order relations;Improved A*algorithm;Heuristic search;Priority queue
一、交通网络最短路径问题概述
按照问题特征的起终点特性,最短路径问题可以分两种:单源最短路径问题及所有节点间最短路径问题,其中单源最短路径问题更具有普遍意义,且可为所有节点间最短路径提供良好的借鉴方案,本文以单源最短路径问题为研究对象。
二、图的搜索策略
(一)盲目搜索(blind search)
盲目搜索[3]不考虑具体给定问题的信息,按照事先安排好的搜索方法进行穷举是搜索,在搜索过程中不计权重,只计到达目标点的最少路径数,因此盲目搜索也称为是一致性搜索(uninformed search),主要包括广度优先搜索和深度优先搜索两种基本的图搜索,他们实质是对图中路径进行遍历的过程。因搜索的无向性,导致搜索效率随着图中网络节点的增大迅速下降。
(二)启发式搜索(heuristic search)
启发式搜索,是一种首先对最有希望的节点进行搜索的搜索策略。它通过一定的信息知识进行搜索,即通过选定一种评估函数(heuristic function),在搜索过程中的每一步,寻找评估函数的分值最低的节点作为下一个搜索扩展节点,这样在一定程度上缩小了搜索范围,从而在整体上提高了搜索效率,启发式搜索的核心是估价函数f(n) = g(n) + h(n)。
三、标准A*算法及缺点
A*算法[3]是一种启发式搜索算法,在搜索过程中带有路径信息引导的策略,用启发函数评估当前的状态节点与目标节点之前的路径情况,估价函数表示为:f '(n) = g '(n) + h '(n)
其中 是节点 的估价函数,表示从起始点经过节点 到目标节点的最佳路径代价。 表示从起始点到节点 的代价, 是从节点 到目标节点的最短路径的估价代价,由于 是无法预先知道的,因此,我们用 做近似。 用 近似,但要求 ; 用 近似,但要求 (从节点 到目标的实际代价)。
A*算法的基本过程描述如下:
AStarSearch()
{ 把起始节点StarNode加进OPENLIST ,CLOSEDLIST为空;
While (OPENLIST != NULL)
{
CurrentNode = OPEN LIST 中成本最低的节点;
If (CurrentNode = TargetNode )
Break;// 路径完成
Else
{ For (循环遍历当前节点CurrentNode 的每个相邻节点 )
{
If( 不在OPENLISTAndCLOSEDLIST表中)
{将该节点移进OPEN LIST 并计算其成本;}
Else if ( 在OPEN LIST 中)
{ If( 的估价值
{ 更新OPENLIST的估价值; }
Else// 在CLOSEDLIST表
{ If( 的估价值
{
更新CLOSEDLIST的估价值;
从CLOSEDLIST中移出节点,
并放到OPENLIST表中;
}
}
把当前节点移入到 CLOSEDLIST ;
将OPENLIST表中的节点按估价值升序排列;
}// end for
} //end while
Output(CLOSEDLIST);// 输出路径
} // end function
A*算法具备很多优点,如果起点与终点之间存在路径,A*就一定能找到,只要h(n)是可纳的,就能找到一条最短路径。但是对于交通路网实时性的要求,A*还有几个不得不改进的缺点,如果告诉它搜索能到达的区域,它会搜索整个地图,仅当OPENLIST表和CLOSEDLIST表中的节点都处理后,才会停止,这会浪费大量的CPU时间。
四、改进方案及结果
(一)基于空间顺序关系的限制区域搜索方案
在算法的实现过程中,大多数只考虑了网络节点之间的空间度量关系,如用距离、费用和时间表示的权值,在大范围感知空间内,人们常用方位角来描述顺序空间关系,在交通网络中,当指定起、终点以寻求最短路径时,按照起、终节点之间顺序关系的限制,搜索应局限在一定区域内,按一定方位进行,这是一种基于空间顺序关系、利用分枝界定原理的空间启发式策略。
1.基于椭圆限制搜索区域的最短路径算法
标准和传统的最短路径算法,因只考虑网路的拓扑特征或阶段特征,而忽略了网络的空间分布特征,使得搜索缺乏方向性。我们知道,给定了一定的起始与终止节点,也就决定了最短路径对应的大致极限距离MD,设节点N至起点S、终点G的欧氏距离分别为|SN|与|NG|,把判断条件定为|SN|+|NG|
椭圆限制算法中椭圆限制的关键是求解适合椭圆长轴MD,以结合起终节点坐标限制椭圆。本文采用统计分析方法完成这一工作,首先在交通网络节点集合中系统抽取具有代表性的一定数目的节点,构造两个集合A与B。则其笛卡尔乘积为:
C中的每个元素可看成时待求最短路径的起终点,其欧氏距离为 ,时间最短所对应的长度为 ,则可设比值系数 = ,对于抽取的样本,可得到比值系数集合R,对R中元素进行统计分析,可以得到某一特定值 ,使得R中总数为满足一定置信水平的元素,其值不大于。因此我们可以用 作为长乘数,利用起、终点坐标求得椭圆长轴MD。
椭圆限制搜索算法将搜索节点限制在一定范围内,大幅度减少了最佳路径算法的搜索规模。然而,此算法需要判断每个新扩展的节点是否落在限制的椭圆内,这需要执行大量的乘积与开方计算,占用较多的时间。
2.基于矩形限制搜索区域的最短路径算法
针对椭圆区域算法效率不高的缺点,本文提出矩形限制区域算法,它继承了椭圆搜索算法对搜索规模合理地进行限制的思想,又避免了算法中大量的乘积与开方计算,其基本思想是求出限制椭圆的最小包含矩形,用此作为限制区域减少算法的搜索规模。
在椭圆限制算法中,得到常乘数 后,由起终节点坐标(xs ys),(xg yg)可得椭圆方程为:
+= 1
其中: , ,
,
得到椭圆方程后,分别对x,y求偏导数,可得x,y的极值分别是:
,
由x,y得极值所对应的切线即构成椭圆的最小包含矩形,如图所示:
3.实验结果分析:
我们以长沙市交通网络的中心及边缘区域随机抽取6组60个节点,各区域分别用
Rcc1,Rcc2,Rul,Rur,Rdl,Rdr表示,计算各组节点之间无限制区域、椭圆限制区域及矩形限制区域下的最短路径耗费CPU时间,结果如表所示:
表4-1不同限制区域下样本最短路径算法平均运行时间比较(单位:ms)
Rcc1―RulRcc1―RdrRcc1―Rcc2Rul―RurRul―Rcc1Rul―RdlRul―RdrRdl―Rur
无限制区域 127 104 36 81 75 111 130 120
椭圆限制区域 70 41 19 41 59 111136 134
矩形限制区域 68 42 18385895120115
五、总结
矩形限制算法始终体现出优于无限制区域算法的效率,并大大多数情况下优于椭圆限制算法。此外,由于矩形限制算法较之椭圆限制算法增大了搜索范围,从而进一步提高了最短路径一次搜索成功的置信水平,由此可见矩形限制算法所具有的优越性。
参考文献:
[1]庄越挺,吴飞 译.Rabin S.人工智能游戏编程真言[M].北京:清华大学出版社,2005
[2]刘华.现代物流管理与实务[M].北京:清华大学出版社,2004
[3]王淑礼,张磊 译.DelouraM.游戏编程精粹[M].北京:人民邮电出版社,2004
[4]S.Robin.A* A esthetic Optimizations[J].Game Programming Gems.2000.261-271
[5]王苏.最短路径算法的比较[J].系统工程与电子技术.2006,18(1):24C25
[6]陈和平,张前哨.算法在游戏地图寻径中的应用与实现[J].计算机应用与软件.2000,23(2):210-215.