2018-09-06

准备面试,重温了一下之前做竞赛用到的一些算法,先来总结一下A星算法吧,这个算法应该是解决寻路问题中最常用的算法之一了.这里我参考了csdn的一篇博客,原文地址如下:A星算法详解, 下面是我的一些总结与理解,方便加深自己的印象同时也捋清文章的思路.

1. 问题介绍
   先看问题,如下图所示,问题是现在假设有人要从绿点(假设为A)走到红点(假设为B),但是中间有一堵墙(蓝色部分),这个人希望找到从绿点走到红点的最短路径.

   
   image.png
   

   这里我们为了简化问题,将地图划分为若干个方块,这个人每次只能移动到相邻的格子(也就是当前位置的8邻域).

2. 开始搜索
   现在我们开始搜索最短路径:

   1. 从起点A开始,并把它加入到一个open list中去, 这个open list目前只有A一个节点, open list中节点就是我们可能需要check的节点, 注意的是open list中的节点只是备选项,也就是说路径的节点是从中选出来的,但是大部分的节点可能是不在路径上的.
   2. 接下来,查找与起点A相邻的方格(忽略不能走的方格,在本例里面就是墙壁格子),把可到达的节点都加入到open list中去,把起点A设为这些方格的父节点,为什么要设置父节点呢,很简单,用于回溯路径的,我们已经到达终点时,我们一层一层向上找父节点,直到回到起点,这个时候最短路径也就找到了.

   3. 将A从open list中移除,加入到close list中去,close list里面是我们不用关注的节点的集合
      下面是我们执行完这一步搜索之后的图片,深绿色的方格为起点，它的外框是亮蓝色，表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点，这里是起点A.

      
      image.png

3. 选择下一步
   现在我们需要从open list中选择下一步要去的方格,这个时候我们应该选择哪一个节点呢, 答案是根据open list中节点的F值大小来选,选择具有最小F值的那个节点,那么F值应该怎么算呢,下面给出计算方式:
   F = G + H. 这里G=从起点A移动到指定方格的移动代价,H=从指定方格到达终点B的估算代价,这个H实际上肯定是猜出来的,如果我们已经知道了每个方格到B的实际代价,那何必要这个算法呢(笑),所以这个H是一个估计值,那么既然是估算值,我们应该如何估算呢,这里比较常用的估算方式是曼哈顿距离,不过值得注意的是曼哈顿距离的计算是不能斜着走的,也就是说只能向上向下向左向右走,斜着走是不行的,另外很重要的一点是计算曼哈顿距离时,我们不考虑障碍物,也就是在计算曼哈顿距离时,我们假设我们拥有超能力可以直接穿越障碍物.
   这里我们假设计算G的时候上下左右走一个的距离是10,斜着走的距离是14,实际上也就是10*根号2,然后近似为14,这里是为了方便计算,我们将计算出来的G和H相加便得到F,第一次计算出来的结果如下图所示,方格的左上角是F,左下角是G,右下角是H.

   
   image.png

4. 选择下一步的格子
   我们从open list中选择F值最小的节点,然后对该节点进行以下操作:
   a. 把它从open list中取出来,加入close list中去
   b. 检查所有与它相邻的方格,忽略已经在close list或者是障碍物的方格,如果方格不在open list中,那么把方格加入到open list中去.
   c. 把我们选定的方格设定为这些新加入方格的父亲.
   d. 如果某个相邻方格(假设为X)已经在open list中(也就是说从当前节点的父节点也能够到达这个方格),那么检查这条路径是否是最优的,也就说check从当前方格到达X是否有更小的G值,如果没有的话,就不进行任何操作.相反如果G值更小,则把X的父亲节点设为当前方格,然后重新计算X的F值.
   带入我们这个例子里面,流程大概如下:

   
   image.png
   

   根据上一步的结果,我们选择F=40的节点作为当前节点,当前节点被加入到close list中,目前close list中的两个节点用蓝线打亮,open list目前7个节点,用绿色框表出,现在我们检查当前节点的相邻节点,根据上面所说的规则,障碍物节点不考虑,已经处于close list的节点也不考虑,因此我们只考虑剩下的4个节点.
   剩下的四个节点都已经处于open list中,因此我们需要检查从当前节点到达那里的路径是否会更好,使用G值来判定,先看看上面的方格,如果我们通过当前方格来到达上面的方格,那么G值应该是10+10=20,但是目前上面这个节点的G值是14,显然20>14,所以我们不做任何改变.
   检查其他四个节点,发现都不需要改变,因此我们结束这一步,进入下一步

5. 继续下一步
   再次遍历我们的open list,这时open list里面只有7个节点,我们需要继续选择F值最小的那个,但是这个时候有两个F值最小的节点,这个时候没有规律要求我们要选哪个节点,所以我们随便选择一个节点,假设我们选择下面的那个节点,结果如下所示

   
   image.png
   

   这个时候需要我们稍微注意点的是,我们忽略了右下角的那个格子,这个能不能到达取决于题目规则,假设我们这里是不能穿越障碍物边角叭,也就是不能斜着到障碍物下面的格子.

6. 然后我们重复执行前面的操作,直到终点也到达open list中,最后结果图大致如下所示:

   
   image.png
   

   个人感觉这个图的第三个节点选择的是右上方的节点,并不是我们在前面写的右下方的节点,因为如果选择的是右下的节点,那么找出来的路是会走上面的路而不是下面的路.这个应该是作者从其他地方摘录的时候没注意的一点.
   这个时候,我们从图上可以很明显的看出从终点回到起点的顺序,这就是我们使用父节点的原因.

7. 总结步骤

• 把起点加入open list
• 重复以下过程:
  1. 遍历open list,查找F值最小的节点,把它作为当前要处理的节点.
  2. 把这个节点加入close list
  3. 对当前节点的相邻8个节点,如果是不可达的或者在close list中,就忽略它,如果不是的话,那么分两种情况,如果这个节点不在open list中,那么将这个节点加入open list中,并且把当前节点设为它的父节点,计算该节点的F,G和H值.如果在open list的话,检查从当前节点到那个节点是否是更好的路径,用G值作为参考,更小的G值代表更好的路径.如果确实从当前节点到那个节点是更好的路径,那么注意要将那个节点的父节点改为当前节点,并且重新计算其G和F值
• 如果我们终点已经找到,或者open list为空,算法停止.
• 保存路径,从终点开始,每个方格沿着父节点移动直至起点,这就是最短路径.

8. 额外的话
   值得一提的是A星算法中最重要的应该是open list的维护了,因为我们需要寻找open list中的具有最小F值的节点,因此我们可以根据F值对open list进行排序,最常用的应该是最小堆,不过需要注意的是,如果是根据F值排序的话,在步骤的第三步,如果F值发生改变的话,那么就对open list进行重新排序了.