论文部分内容阅读
摘要：从起点绕开障碍物快速达终点是A*算法的主要研究内容，该文针对该算法存在效率低，不适合面积大的路径的缺点，提出了改进的A*算法措施，主要从优化Open表，优化估计函数等两个主要方面进行改进。仿真实验将改进后的A*算法与基本A*算法在消耗時间和节点访问量方面进行了对比，取得了明显的效果，说明该文算法具有一定的研究价值。
关键词： A*算法；优化函数；open表
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）29-0184-03
A*算法是一种时间最优的启发式搜索算法，它能够高效而且准确的找到一条可达的最短路径，并被广泛应用于GIS系统和寻找路径的方案中，它与老式的搜索算法诸如深度优先搜索算法，广度优先搜索算法，Dijkstra搜索算法[1-2]，在时间复杂度和空间复杂度要好的很多，但由于它的性能消耗伴随着搜索地图规模的扩大而成指数级增加。一些学者对其进行了研究，文献[4]提出一种基于改进A*算法的电动车能耗最优路径规划方法。通过，建立运行能耗函数，设计了新的启发式能耗预估代价对A*算法进行改进，证明了所提出的启发式能耗预估代价满足可采纳性和一致性；文献[5]使用最小二叉堆和标记数组两种混合数据结构优化open表的存储和遍历，用夹角余弦值作为新的启发信息，减少搜索过程中对非最有节点的考察量；文献[6]提出了一种改进的A*算法。首先，采用栅格方法建立环境模型，使用A*算法进行初步的路径规划。其次，针对A*算法规划的路径冗余点较多以及路径长度和转折角度较大的缺陷，提出将A*算法规划出的路径按较小的分割步长进行分割，得到一系列路径节点。
本文在文献[7]研究的基础上，根据A*算法出现的问题进行改进，从优化Open表，沿着目标方向搜索，沿着目标点移动，避免“死胡同”等方面进行描述，取得了比较好的效果。
1 A*算法
A*算法是一种启发式的路径搜索算法，其本质是从起点到终点尽可能地选择一条最短路径的算法。与目前经典的搜索算法不同，在A*算法中，设计了一个估价函数，其表达如下：
其中表示是从当前结点展开搜索出来的结点的估计函数，表示从当前节点结点到预处理搜索点的实际函数，则表示预处理的结点到目标节点的估价函数。采用Start表示起点，open表示存储没有访问的节点，使用End表存储已经访问过的节点，其步骤如下：
步骤1：把起点作为第一个结点放入Start列表中。
步骤2：处理start的周围结点，一般选择该节点周围（上下，左右，左右斜上斜下）中的8个方位的节点，且将8个方位的父节点设置为该Start结点。
步骤3：当周围结点搜索完毕后，将start节点从open表的集合列表中删除，同时放入end集合列表中。
步骤4：先检查没有访问的这些节点，当确认是可用结点，则计算那些预处理结点的，和值并进行比较，将最小的结点存储到open集合列表中，以便下一次使用。
步骤5：当某个预处理结点已经在open集合列表中了，如果此时使用新的路径对应的估价函数值更低，则使用此条路径进行更新，反之则不更新。
步骤6：判断该节点周围的节点是否为终点，如果不是则重复执行步骤4和5，反之则结束并根据之前每个结点存在的父节点进行回溯找到终点，记录这条路径，算法结束。
从A*中算法中发现最重要的步骤就是启发式函数的选择，当选择不同的启发式函数就会造成不同搜索范围，当搜索范围越小则搜索路径越精确从而造成的误差就会越少。一旦在前进路径中出现多个障碍的时候，就会出现无意义的搜索，因此浪费了大量不必要的时间和空间。
2 改进的A*算法
2.1 优化Open表
A*算法的运行过程中主要是按照移入、排序、移出的步骤来进行的，其中所耗费的主要代价在于”排序”，其目的是为了能够方便的寻找出open表中最小的顶点。当移动机器人所处的面积比较大的时候，出行路线很长的话，open表中的数据量将很大，当反复查询这张open表的时候会导致算法运行所需的时间代价更高。因此open表的数据结构决定了算法效率的高低，在一定程度上能够有效地提高搜索效率，因此能够迅速的寻找出值最小的顶点。
在A*算法运行过程中，需要重复搜索open表中值最小的顶点，当采用最小二叉堆的存储方式保存open表，则最小二叉堆的堆顶点的值就是需要搜索的数值。在最小二叉堆的存储方法过程中使用堆排序的方法就能迅速地找到值。
2.2 优化估计函数
A*算法中的估价函数中整个算法的核心部分，这是因为估价函数的效果直接影响到算法在运行过程中遍历的顶点数，从而减少了open表中的数据量，因此可以提高算法的寻径效率，从而搜索出更优的路径。从A*算法中的表达式来看，作为既定值，其改进空间不大，启发函数才是估价函数的重要组成部分。本文使用向量空间中的方向识别模型，对的计算量进行优化。其优化主要集中在决策阶段和行动阶段，也就是下一个行动点和向下一个行动点移动的两个阶段。传统的算法中在决定下一个移动点的时候，只有依靠的最小值，从open列表中选择出估值函数最小的节点。本文对open列表中的节点进行双层排序，也就是说估值函数大小的排序和是否在当前节点到目标节点方向上的排序。当存在可以到达路径的情况下，优化选择在目标方向上移动的节点，会更快地完成寻优的路径。在行动过程中，根据决策阶段的选择进行寻路的过程中会存在这样的问题，在可能出现的目标方向上，选择的路径可能无法走通，即“死胡同”路径，为了避免这种情况的发生，就需要记录途中被舍弃的邻居节点，这样当路径进入死胡同的时候，还可以从已经被记录下的舍弃的邻居节点中选择最优的方案。因此本文算法的优化策略如下。
2.2.1 沿着目标方向搜索 规则1：在已知节点S，起始节点和目标节点G，设节点S和邻居节点构成集合NS，节点S和集合NS中的每个节点对应的向量SG构成集合W。当集合W中的元索与起始节点和目标节点所构成向量的点积大于0，或者节点S有且仅有一个邻居节点，称集合W中元索对应的邻居节点在目标方向上。
在图1中当节点G在节点S的水平位置或者竖直向上位置的时候，根据规则1，可以得到S-up，S-left和S-down这些节点不满足规则1.因此，可以去掉S-up，S-left和S-down这三个节点的计算。同理，如图2所示，节点S-left和节点S-down这两个节点也不满足规则1，因此需要去除这两个节点的计算，当沿着目标方向进行搜索的时候，当沿着SG方向走入“死胡同”的时候，为了能够返回被去除的节点，需要将这些节点存储到RightList中。
2.2.2 沿着目标点移动
根据规则1中去掉的那些不在目标方向上的节点，因此减少了计算量。根据一般的寻路原理，不会往远离目标方向的节点移动。因此如图3所示，在一次寻路过程中某个中间位置，节点S1的四个邻居节点都在目标方向上，会选择从节点S-right和节点S-down中选择最优节点作为下一个前进节点，因此定义如下规则
规则2：当已经目标节点G，节点S1在目标方向上，节点S1与它所有邻居节点构成集合NS1，节点S与集合NS1中的每一个节点对应的向量构成集合W1。当集合W1中元索与节点S1和目标节点构成了向量S1G的点面积大于0，或者S1有且仅有一个邻居节点，因此集合W1中的元索对应的邻居节点在移动方向上。 当向目标方向移动的过程中，所有满足规则2的节点都放入OpenList表中，这样能够保证节点在走入“死胡同”的时候，能够返回到被去除的节点，将规则2中的去除的节点存入ReverseList，如图4所示，图中的节点S-down和节点S-right满足规则2，因此放入Openlist中，节点S-up与节点S-light不满足规则2，将他们放入ReverseMovelist中，这样能够有效的减少节点S1-up和节点S1-left的计算，能够减少对这2个节点的的计算。
2.2.3 采用回溯法避免“死胡同”
根据规则1和规则2，当向着目标节点移动的过程中，进入“死胡同”的情况时候，先将ReverseMoveList中的元索移入到OpenList中，然后继续查询，如果还没有移动到目标节点，则表示前进的方向是错误的，需要将RightList表移动到OpenList中，继续寻找路径，这样可以使得使得计算效率上明显优于传统的A*算法。
3 改进的A*算法代码描述
选择一个N*N的网格地图；其中设置Open列表和Close列表分别用来存放将要访问的节点和己经访问过并且被排除掉的节点，两个集合中的节点按估值函数大小升序排序；使用Temp栈用来存放在方向引导过程中删除的节点；设置起始点节点S和目标节点E。如果从始点节点S到目标节点E存在可以到达的最短路径，则利用函数reconstruc_path输出该路径上所有节点集合；否则，输出不存在路径，即节点集合为空。
部分伪代码如下：
[Open ={S}， Close={}， Temp={}
while Open has Node do
if tempNode equal E then output path with tempNode
else do
Set NList={neighbours of tempNode}
for each node in N1List do
if Close not contains node then
if N1ist.Count >1 and node is not in direction from S to E then
push node into Temp
else do
if node is in direction from tempNode to E then
calculate the value of heuristic function for node
push node into Open
set tempNode as node’s parrent node
else do
push node into Temp
push tempNode into Close
remove tempNode from Open
if Open. Count =0 and tempNode is not E
Popup the first node in Temp，and push it into Open
if tempNode is not E
There is no way from S to E ]
4 實验分析
创建一个地图，如图5所示。并在网格地图中进行以下说明，设置起始节点和目标节点；在网格地图中设置障碍物；调用A*优化算法；得出最短路径。同时对地图进行相关参数方面的设置。按照上述模拟实验步骤，设置网格面积分别为20*20， 30*30， 40*40，50*50，进行多次模拟实验，最终得出了A*优化算法和传统A*算法的消耗时间和节点访问数量对应的数据，如表1和表2所示。
结束语
本文首先对A*算法存在的问题进行了描述，提出了优化A*算法的相关步骤，并通过实验的对比来说明了优化后的算法的性能优于基本算法，取得了比较好的效果。
参考文献：
[1] 田翠华，许卫平，陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报：自然科学版，2013， 29（3）；19-24.
[2] 卢启衡，冯晓红.基于宽度优先搜索的路径生成算法[J].现代计算机：专业版，2006（12）；87-89.
[3] 蔚洁，杨怀雷，成汝震.基于Dijkstra算法的最优路径搜索方法[J].河北师范大学学报：自然科学版，2008，32（5）； 590-593.
[4] 顾青.基于改进A*算法的电动车能耗最优路径规划[J].农业机械学报，2015，46（12）：316-322.
[5] 陈素琼.基于改进A*算法的地图游戏寻径研究[J].重庆师范大学学报：自然科学版，2017，34（4）：75-78.
[6] 孙炜.基于一种改进A*算法的移动机器人路径规划[J].湖南大学学报：自然科学版，2017，44（4）：94-101.
[7] 赵振国.向量空间中A*算法的优化及应用[D].哈尔滨理工大学，2016，3.
关键词： A*算法；优化函数；open表
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）29-0184-03
A*算法是一种时间最优的启发式搜索算法，它能够高效而且准确的找到一条可达的最短路径，并被广泛应用于GIS系统和寻找路径的方案中，它与老式的搜索算法诸如深度优先搜索算法，广度优先搜索算法，Dijkstra搜索算法[1-2]，在时间复杂度和空间复杂度要好的很多，但由于它的性能消耗伴随着搜索地图规模的扩大而成指数级增加。一些学者对其进行了研究，文献[4]提出一种基于改进A*算法的电动车能耗最优路径规划方法。通过，建立运行能耗函数，设计了新的启发式能耗预估代价对A*算法进行改进，证明了所提出的启发式能耗预估代价满足可采纳性和一致性；文献[5]使用最小二叉堆和标记数组两种混合数据结构优化open表的存储和遍历，用夹角余弦值作为新的启发信息，减少搜索过程中对非最有节点的考察量；文献[6]提出了一种改进的A*算法。首先，采用栅格方法建立环境模型，使用A*算法进行初步的路径规划。其次，针对A*算法规划的路径冗余点较多以及路径长度和转折角度较大的缺陷，提出将A*算法规划出的路径按较小的分割步长进行分割，得到一系列路径节点。
本文在文献[7]研究的基础上，根据A*算法出现的问题进行改进，从优化Open表，沿着目标方向搜索，沿着目标点移动，避免“死胡同”等方面进行描述，取得了比较好的效果。
1 A*算法
A*算法是一种启发式的路径搜索算法，其本质是从起点到终点尽可能地选择一条最短路径的算法。与目前经典的搜索算法不同，在A*算法中，设计了一个估价函数，其表达如下：
其中表示是从当前结点展开搜索出来的结点的估计函数，表示从当前节点结点到预处理搜索点的实际函数，则表示预处理的结点到目标节点的估价函数。采用Start表示起点，open表示存储没有访问的节点，使用End表存储已经访问过的节点，其步骤如下：
步骤1：把起点作为第一个结点放入Start列表中。
步骤2：处理start的周围结点，一般选择该节点周围（上下，左右，左右斜上斜下）中的8个方位的节点，且将8个方位的父节点设置为该Start结点。
步骤3：当周围结点搜索完毕后，将start节点从open表的集合列表中删除，同时放入end集合列表中。
步骤4：先检查没有访问的这些节点，当确认是可用结点，则计算那些预处理结点的，和值并进行比较，将最小的结点存储到open集合列表中，以便下一次使用。
步骤5：当某个预处理结点已经在open集合列表中了，如果此时使用新的路径对应的估价函数值更低，则使用此条路径进行更新，反之则不更新。
步骤6：判断该节点周围的节点是否为终点，如果不是则重复执行步骤4和5，反之则结束并根据之前每个结点存在的父节点进行回溯找到终点，记录这条路径，算法结束。
从A*中算法中发现最重要的步骤就是启发式函数的选择，当选择不同的启发式函数就会造成不同搜索范围，当搜索范围越小则搜索路径越精确从而造成的误差就会越少。一旦在前进路径中出现多个障碍的时候，就会出现无意义的搜索，因此浪费了大量不必要的时间和空间。
2 改进的A*算法
2.1 优化Open表
A*算法的运行过程中主要是按照移入、排序、移出的步骤来进行的，其中所耗费的主要代价在于”排序”，其目的是为了能够方便的寻找出open表中最小的顶点。当移动机器人所处的面积比较大的时候，出行路线很长的话，open表中的数据量将很大，当反复查询这张open表的时候会导致算法运行所需的时间代价更高。因此open表的数据结构决定了算法效率的高低，在一定程度上能够有效地提高搜索效率，因此能够迅速的寻找出值最小的顶点。
在A*算法运行过程中，需要重复搜索open表中值最小的顶点，当采用最小二叉堆的存储方式保存open表，则最小二叉堆的堆顶点的值就是需要搜索的数值。在最小二叉堆的存储方法过程中使用堆排序的方法就能迅速地找到值。
2.2 优化估计函数
A*算法中的估价函数中整个算法的核心部分，这是因为估价函数的效果直接影响到算法在运行过程中遍历的顶点数，从而减少了open表中的数据量，因此可以提高算法的寻径效率，从而搜索出更优的路径。从A*算法中的表达式来看，作为既定值，其改进空间不大，启发函数才是估价函数的重要组成部分。本文使用向量空间中的方向识别模型，对的计算量进行优化。其优化主要集中在决策阶段和行动阶段，也就是下一个行动点和向下一个行动点移动的两个阶段。传统的算法中在决定下一个移动点的时候，只有依靠的最小值，从open列表中选择出估值函数最小的节点。本文对open列表中的节点进行双层排序，也就是说估值函数大小的排序和是否在当前节点到目标节点方向上的排序。当存在可以到达路径的情况下，优化选择在目标方向上移动的节点，会更快地完成寻优的路径。在行动过程中，根据决策阶段的选择进行寻路的过程中会存在这样的问题，在可能出现的目标方向上，选择的路径可能无法走通，即“死胡同”路径，为了避免这种情况的发生，就需要记录途中被舍弃的邻居节点，这样当路径进入死胡同的时候，还可以从已经被记录下的舍弃的邻居节点中选择最优的方案。因此本文算法的优化策略如下。
2.2.1 沿着目标方向搜索 规则1：在已知节点S，起始节点和目标节点G，设节点S和邻居节点构成集合NS，节点S和集合NS中的每个节点对应的向量SG构成集合W。当集合W中的元索与起始节点和目标节点所构成向量的点积大于0，或者节点S有且仅有一个邻居节点，称集合W中元索对应的邻居节点在目标方向上。
在图1中当节点G在节点S的水平位置或者竖直向上位置的时候，根据规则1，可以得到S-up，S-left和S-down这些节点不满足规则1.因此，可以去掉S-up，S-left和S-down这三个节点的计算。同理，如图2所示，节点S-left和节点S-down这两个节点也不满足规则1，因此需要去除这两个节点的计算，当沿着目标方向进行搜索的时候，当沿着SG方向走入“死胡同”的时候，为了能够返回被去除的节点，需要将这些节点存储到RightList中。
2.2.2 沿着目标点移动
根据规则1中去掉的那些不在目标方向上的节点，因此减少了计算量。根据一般的寻路原理，不会往远离目标方向的节点移动。因此如图3所示，在一次寻路过程中某个中间位置，节点S1的四个邻居节点都在目标方向上，会选择从节点S-right和节点S-down中选择最优节点作为下一个前进节点，因此定义如下规则
规则2：当已经目标节点G，节点S1在目标方向上，节点S1与它所有邻居节点构成集合NS1，节点S与集合NS1中的每一个节点对应的向量构成集合W1。当集合W1中元索与节点S1和目标节点构成了向量S1G的点面积大于0，或者S1有且仅有一个邻居节点，因此集合W1中的元索对应的邻居节点在移动方向上。 当向目标方向移动的过程中，所有满足规则2的节点都放入OpenList表中，这样能够保证节点在走入“死胡同”的时候，能够返回到被去除的节点，将规则2中的去除的节点存入ReverseList，如图4所示，图中的节点S-down和节点S-right满足规则2，因此放入Openlist中，节点S-up与节点S-light不满足规则2，将他们放入ReverseMovelist中，这样能够有效的减少节点S1-up和节点S1-left的计算，能够减少对这2个节点的的计算。
2.2.3 采用回溯法避免“死胡同”
根据规则1和规则2，当向着目标节点移动的过程中，进入“死胡同”的情况时候，先将ReverseMoveList中的元索移入到OpenList中，然后继续查询，如果还没有移动到目标节点，则表示前进的方向是错误的，需要将RightList表移动到OpenList中，继续寻找路径，这样可以使得使得计算效率上明显优于传统的A*算法。
3 改进的A*算法代码描述
选择一个N*N的网格地图；其中设置Open列表和Close列表分别用来存放将要访问的节点和己经访问过并且被排除掉的节点，两个集合中的节点按估值函数大小升序排序；使用Temp栈用来存放在方向引导过程中删除的节点；设置起始点节点S和目标节点E。如果从始点节点S到目标节点E存在可以到达的最短路径，则利用函数reconstruc_path输出该路径上所有节点集合；否则，输出不存在路径，即节点集合为空。
部分伪代码如下：
[Open ={S}， Close={}， Temp={}
while Open has Node do
if tempNode equal E then output path with tempNode
else do
Set NList={neighbours of tempNode}
for each node in N1List do
if Close not contains node then
if N1ist.Count >1 and node is not in direction from S to E then
push node into Temp
else do
if node is in direction from tempNode to E then
calculate the value of heuristic function for node
push node into Open
set tempNode as node’s parrent node
else do
push node into Temp
push tempNode into Close
remove tempNode from Open
if Open. Count =0 and tempNode is not E
Popup the first node in Temp，and push it into Open
if tempNode is not E
There is no way from S to E ]
4 實验分析
创建一个地图，如图5所示。并在网格地图中进行以下说明，设置起始节点和目标节点；在网格地图中设置障碍物；调用A*优化算法；得出最短路径。同时对地图进行相关参数方面的设置。按照上述模拟实验步骤，设置网格面积分别为20*20， 30*30， 40*40，50*50，进行多次模拟实验，最终得出了A*优化算法和传统A*算法的消耗时间和节点访问数量对应的数据，如表1和表2所示。
结束语
本文首先对A*算法存在的问题进行了描述，提出了优化A*算法的相关步骤，并通过实验的对比来说明了优化后的算法的性能优于基本算法，取得了比较好的效果。
参考文献：
[1] 田翠华，许卫平，陈玉明.深度优先遍历算法、随机布点法及回溯法在迷宫游戏中的应用[J].河北北方学院学报：自然科学版，2013， 29（3）；19-24.
[2] 卢启衡，冯晓红.基于宽度优先搜索的路径生成算法[J].现代计算机：专业版，2006（12）；87-89.
[3] 蔚洁，杨怀雷，成汝震.基于Dijkstra算法的最优路径搜索方法[J].河北师范大学学报：自然科学版，2008，32（5）； 590-593.
[4] 顾青.基于改进A*算法的电动车能耗最优路径规划[J].农业机械学报，2015，46（12）：316-322.
[5] 陈素琼.基于改进A*算法的地图游戏寻径研究[J].重庆师范大学学报：自然科学版，2017，34（4）：75-78.
[6] 孙炜.基于一种改进A*算法的移动机器人路径规划[J].湖南大学学报：自然科学版，2017，44（4）：94-101.
[7] 赵振国.向量空间中A*算法的优化及应用[D].哈尔滨理工大学，2016，3.