改进型A*算法在物流配送网络中的应用

改进型A*算法在物流配送网络中的应用

李铭，田丰睿

李铭，田丰睿

（贵州大学计算机科学与信息学院通信与信息系统专业，贵阳550025）

摘要：A*算法是目前路径搜索中应用最广泛的算法，最短路径搜索算法效率是研究人员普遍关注的重点，本文在分析A*算法的基础上，重点介绍了一种改进型A*启发式搜索算法，实验结果表明：提出的改进方法极大地减少算法搜索区域，提高了算法的效率，更加适合交通网络的路径导航。

关键词：空间顺序关系；改进型A*算法；启发式搜索；优先级队列

中图分类号：TP393文献标识码：A文章编号：1007-9599(2010)05-0000-02

ImprovedA*AlgorithminLogisticsDistributionNetworks

LiMing,TianFengrui

（ComputerScience&InformationCollegeofGuizhouUniversity,GuizhouUniversity,Guiyang550025,China）

Abstract:A*pathsearchalgorithmisthemostwidelyusedalgorithms,efficiencyofshortestpathsearchalgorithmisgenerallythefocusofresearchers,onthebasisofA*algorithm,thearticleintroduceanimprovedA*heuristicsearchalgorithm,Theexperimentalresultsshowthat:theproposedapproachgreatlyreducethealgorithmsearchareaandimprovetheefficiency,thealgorithmismoresuitableforthepathofnavigationoftransportationnetwork.

Keywords:Spatialorderrelations;ImprovedA*algorithm;Heuristicsearch;Priorityqueue

一、交通网络最短路径问题概述

按照问题特征的起终点特性，最短路径问题可以分两种：单源最短路径问题及所有节点间最短路径问题，其中单源最短路径问题更具有普遍意义，且可为所有节点间最短路径提供良好的借鉴方案，本文以单源最短路径问题为研究对象。

二、图的搜索策略

（一）盲目搜索（blindsearch）

盲目搜索[3]不考虑具体给定问题的信息，按照事先安排好的搜索方法进行穷举是搜索，在搜索过程中不计权重，只计到达目标点的最少路径数，因此盲目搜索也称为是一致性搜索（uninformedsearch），主要包括广度优先搜索和深度优先搜索两种基本的图搜索，他们实质是对图中路径进行遍历的过程。因搜索的无向性，导致搜索效率随着图中网络节点的增大迅速下降。

（二）启发式搜索（heuristicsearch）

启发式搜索，是一种首先对最有希望的节点进行搜索的搜索策略。它通过一定的信息知识进行搜索，即通过选定一种评估函数（heuristicfunction），在搜索过程中的每一步，寻找评估函数的分值最低的节点作为下一个搜索扩展节点，这样在一定程度上缩小了搜索范围，从而在整体上提高了搜索效率，启发式搜索的核心是估价函数f(n)=g(n)+h(n)。

三、标准A*算法及缺点

A*算法[3]是一种启发式搜索算法，在搜索过程中带有路径信息引导的策略，用启发函数评估当前的状态节点与目标节点之前的路径情况，估价函数表示为：f'(n)=g'(n)+h'(n)

其中是节点的估价函数，表示从起始点经过节点到目标节点的最佳路径代价。表示从起始点到节点的代价，是从节点到目标节点的最短路径的估价代价，由于是无法预先知道的，因此，我们用做近似。用近似，但要求；用近似，但要求（从节点到目标的实际代价）。

A*算法的基本过程描述如下：

AStarSearch()

{把起始节点StarNode加进OPENLIST，CLOSEDLIST为空；

While(OPENLIST!=NULL)

{

CurrentNode=OPENLIST中成本最低的节点;

If(CurrentNode=TargetNode)

Break;//路径完成

Else

{For(循环遍历当前节点CurrentNode的每个相邻节点)

{

If(不在OPENLISTAndCLOSEDLIST表中)

{将该节点移进OPENLIST并计算其成本;}

Elseif(在OPENLIST中)

{If(的估价值<OPENLIST的估价值)

{更新OPENLIST的估价值；}

Else//在CLOSEDLIST表

{If(的估价值<CLOSEDLIST的估价值)

{

更新CLOSEDLIST的估价值；

从CLOSEDLIST中移出节点，

并放到OPENLIST表中；

}

}

把当前节点移入到CLOSEDLIST；

将OPENLIST表中的节点按估价值升序排列；

}//endfor

}//endwhile

Output(CLOSEDLIST)；//输出路径

}//endfunction

A*算法具备很多优点，如果起点与终点之间存在路径，A*就一定能找到，只要h(n)是可纳的，就能找到一条最短路径。但是对于交通路网实时性的要求，A*还有几个不得不改进的缺点，如果告诉它搜索能到达的区域，它会搜索整个地图，仅当OPENLIST表和CLOSEDLIST表中的节点都处理后，才会停止，这会浪费大量的CPU时间。

四、改进方案及结果

（一）基于空间顺序关系的限制区域搜索方案

在算法的实现过程中，大多数只考虑了网络节点之间的空间度量关系，如用距离、费用和时间表示的权值，在大范围感知空间内，人们常用方位角来描述顺序空间关系，在交通网络中，当指定起、终点以寻求最短路径时，按照起、终节点之间顺序关系的限制，搜索应局限在一定区域内，按一定方位进行，这是一种基于空间顺序关系、利用分枝界定原理的空间启发式策略。

1.基于椭圆限制搜索区域的最短路径算法

标准和传统的最短路径算法，因只考虑网路的拓扑特征或阶段特征，而忽略了网络的空间分布特征，使得搜索缺乏方向性。我们知道，给定了一定的起始与终止节点，也就决定了最短路径对应的大致极限距离MD，设节点N至起点S、终点G的欧氏距离分别为|SN|与|NG|，把判断条件定为|SN|+|NG|<MD，N的临界点构成了以S、N为焦点，以MD为长轴的椭圆如图所示：

椭圆限制算法中椭圆限制的关键是求解适合椭圆长轴MD，以结合起终节点坐标限制椭圆。本文采用统计分析方法完成这一工作，首先在交通网络节点集合中系统抽取具有代表性的一定数目的节点，构造两个集合A与B。则其笛卡尔乘积为：

C中的每个元素可看成时待求最短路径的起终点，其欧氏距离为，时间最短所对应的长度为，则可设比值系数=，对于抽取的样本，可得到比值系数集合R，对R中元素进行统计分析，可以得到某一特定值，使得R中总数为满足一定置信水平的元素，其值不大于。因此我们可以用作为长乘数，利用起、终点坐标求得椭圆长轴MD。

椭圆限制搜索算法将搜索节点限制在一定范围内，大幅度减少了最佳路径算法的搜索规模。然而，此算法需要判断每个新扩展的节点是否落在限制的椭圆内，这需要执行大量的乘积与开方计算，占用较多的时间。

2.基于矩形限制搜索区域的最短路径算法

针对椭圆区域算法效率不高的缺点，本文提出矩形限制区域算法，它继承了椭圆搜索算法对搜索规模合理地进行限制的思想，又避免了算法中大量的乘积与开方计算，其基本思想是求出限制椭圆的最小包含矩形，用此作为限制区域减少算法的搜索规模。

在椭圆限制算法中，得到常乘数后，由起终节点坐标（xsys），(xgyg)可得椭圆方程为：

+=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

无限制区域127104368175111130120

椭圆限制区域7041194159111136134

矩形限制区域684218385895120115

五、总结

矩形限制算法始终体现出优于无限制区域算法的效率，并大大多数情况下优于椭圆限制算法。此外，由于矩形限制算法较之椭圆限制算法增大了搜索范围，从而进一步提高了最短路径一次搜索成功的置信水平，由此可见矩形限制算法所具有的优越性。

参考文献：

[1]庄越挺,吴飞译.RabinS.人工智能游戏编程真言[M].北京:清华大学出版社,2005

[2]刘华.现代物流管理与实务[M].北京:清华大学出版社,2004

[3]王淑礼,张磊译.DelouraM.游戏编程精粹[M].北京:人民邮电出版社,2004

[4]S.Robin.A*AestheticOptimizations[J].GameProgrammingGems.2000.261-271

[5]王苏.最短路径算法的比较[J].系统工程与电子技术.2006,18(1):24–25

[6]陈和平,张前哨.算法在游戏地图寻径中的应用与实现[J].计算机应用与软件.2000,23(2):210-215.