A算法，A（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

基本概念

• 首先在大学我们遇到最多的算法Dijkstra、Floyd、广度搜索、深度搜索。关于这些算法我们以后再慢慢的研究，今天的重点在A算法上。A算法是一种启发式算法。与上述几种算法不同的是A*算法在考虑起始节点的同时还会考虑到目标节点的代价。
• 在A*算法中我们给每个节点都定义一些属性。最基本的就是下文提到的三基数-这里的三基数是我自己定义的一个名词。什么叫启发式就是在探索路径的时候既要选择里起始点最近也要考虑到里目标节点的消费问题。

三基值

• 上面的一些概念可能会使你很模糊，这里我们直接看定义。

F=G+H : 表示一个节点的总消费值；换句话说就是离起始节点和目标节点距离的总和 G : 表示该从其实节点到该节点的消费值； H : 表示从该节点到目标节点的消费值；(这里注意一下，这里的消费值其实是一个预估值，因为我们无法判断到目标节点的具体路径，这个H值得获取本文会提供三种方法，其中使用最广泛的是曼哈顿距离)

图1

三基值计算

常规约定

• 在方格地图中我们约定横向或者纵向单位消费为10
• 在方格地图中斜向单位消费为14
• 在墙（墙、河流等不可经过的节点统称）角我们是不可以斜着穿越的，这是常识。实际中我们每个移动的物体都是有自己的空间的，如下图这样S–>E的过程S’已经占用了Q（墙）的领域了。

图2

• 在非墙角地方根据自己需求可以设定可穿越，也可以设定不可穿越。本文设定是可穿越的。

G值计算

• 三基数在上面定义中我们已经列出了其计算公式，可能有的人看的不是很明白。我们这里详细解释一下
• 首先我们先看三基值中的G值，G表示该从其实节点到该节点的消费值，这句话的意思从开始节点移动到当前节点需要的实际的消费，这里是需要考虑到不可经过的节点的。如下图S表示起始点，E表示目标节点,N表示当前节点，黑色的表示墙(不可经过的节点集合)。我们规定在墙角是无法斜着穿过去，在其他地方是可以斜着经过的。有了这个约定，我们可以算出图3中 S—>N1 消费10， S—>N2消费14，因为从S到N2不是处于墙角。 途中N3—>N4就是明显的墙角。所以N3—>N4消费是20。在此我向大家推荐一个架构学习交流圈。交流学习伪鑫：1253431195（里面有大量的面试题及答案）里面会分享一些资深架构师录制的视频录像：有Spring，MyBatis，Netty源码分析，高并发、高性能、分布式、微服务架构的原理，JVM性能优化、分布式架构等这些成为架构师必备的知识体系。还能领取免费的学习资源，目前受益良多

H值计算方式

• H值和G值作用相反，H值是预估到目标节点的消费值。

-  首先G是针对其实点的，而H值是针对目标节点的-  其次G值是真实值，而H值是预估值-  最后G值得计算是允许斜线行走的，但是H值计算只能横向和纵向的结合

• 下图(图4中从N2—>E点的H=40+10),其中40部分已经穿墙了。这里因为是预估值所以不考虑墙的存在。到这里我们基本的定义已经结束了

图4

集合列表

• 在我们A*寻路的过程中，我们需要用到两个集合，一个我们成为开放集合(OpenList),另外一个我们称之为闭合集合(ClosedList)。
• 举个例子我们去超市购物，我们都会推个手推车，把喜欢的东西放进购物车里。最后结算的时候或者是中途我们会选择价格更实惠的东西替代我们已经选择的同等产品
• 在A中我们也是这样，openList就相当于购物车，我们会将见到的喜欢的物品加入购物车，但是加入购物车并不一定最后会买，在A中，我们会将节点周围可用的节点加入openList，但是并不一定最后需要。在openList添加的过程我们会慢慢用’更实惠’的节点代替已经选择的相同的节点。在超市最后放到我们自己的包里才是最后我们要带回家的东西。在A*算法中加到closedList中才是我们最后的东西。

寻路解析

本小节图片来源以下文章。其中思想参考源以下文章

• 经过上面的介绍我们了解了A*中我们一些约定的定义，理解上面这些定义的基础上我们下面的流程会很易懂。

初始地图

• 如图5,地图上蓝色方格表示墙，关于墙的定义上面已经解释过了。左边青色的表示S(起始节点)，右边的红色节点表示我们的目标节点。小圆点表示从S到E的最有路径之一。从图5我们可以看出我们在墙角没有斜走，而在其他路段上我们选择斜着走了。下面介绍节点就以图5中的坐标为准。比如起始节点我们就称之为(2,3)。
• 蓝色方格表示不可经过方格
• 青色的边框的方格表示已经加入openList
• 高亮显示的边框表示添加在closedList
• 青色表示其实节点
• 红色表示目标节点

递归寻走

• 首先我们常规的寻路是不可能出现首尾相同的情况。但是项目中得处理这种情况，如果其实节点和目标节点是地图上的统一节点，那么我们的路径就是当前节点。
• 选择当前节点周围可用的节点，如果不在openList集合中则分别计算三基数的值并且加入到openList集合中,计算三基数的同事将待加入openList的节点的父节点设置为当前节点。
• 如果已经存在openList集合中且结合中的G值大于当前节点(周围节点之一)的G值，则将当前节点更新到openList集合中。否则不加入也不更新。
• 周围节点选择完之后我们就把该节点(起始节点)加入closedList中，然后从openList中选择F值最小的节点，在继续重复上面三步骤。

图示流程

• 按照图5中我们可以获得起始节点(2,3)的周围节点列表如图6。并逐个分析是否该加入openList中。

图6

• 通过比较我们发现目前周围的八个节点全部有效且全不在openList中，那么我们就全部加入并计算三基数的值，并设置他们的父节点为(2,3)。如图7

图7

• 从图7中我们可以看出在起始节点(2,3)周围(3,3)这个节点的F值此时在openList中最小，所以此时我们将(2,3)移除openList并将(2,3)加入到closedList中。此时(2,3)由高亮方格显示表示加入closedList集合，
• (2,3)节点就算是结束了他的使命了，加入了closedList集合中的节点我们将不会再去考虑，我们可以认为加入到closedList集合中的点已经成墙了。那么下面我们从openList中选取F值最小(3,3)为新的起始节点，开始重复上面的流程，但是我们发现(3,3)的右上、正右、右下都是墙，还有正左(2,3)在closedList集合中。这四点我们是不用考虑的。在此我向大家推荐一个架构学习交流圈。交流学习伪鑫：1253431195（里面有大量的面试题及答案）里面会分享一些资深架构师录制的视频录像：有Spring，MyBatis，Netty源码分析，高并发、高性能、分布式、微服务架构的原理，JVM性能优化、分布式架构等这些成为架构师必备的知识体系。还能领取免费的学习资源，目前受益良多
  那么只剩下(2,2),(3,2),(2,4),(3,4)这四个点。但是这四个点恰巧有全部在openList中。依照上面的流程我们得以此比较这四个点和openList集合中对应的点的G值谁大谁小。就一个原则谁小留谁。由图8我们可以知道，新获得的这四个点的G值均大于openlist里对应的点的G值，所以我们这里放弃这四个点。他们没有被我们喜欢，我们抛弃这些点。这一轮结束我们将(3,3)加入到closedList集合中。如果新节点G值小于对应的openList中的点的G值得话，我们就要更新openList集合中的对应的那个点。所谓的更新就是将新节点替换原来那个节点。注意此时新节点和openList对应的那个点出了三基数不同，还有父节点也不同了。
• 这里需要解释下为什么新节点的G值都会加10呢，那是因为我们最起始的节点是(2,3)，而此时的起始节点是(3,3),比如我们算(2,2)G值得时候实际上是(2,3)—>(3,3)—>(2,2)整个过程的G值。所以是10+14。

图8

• 由图9我们能够看到此时我们openList中最小F值应该是(3,4)，下面的步骤就是一直重复。

图9

• 直到我们的目标节点成为起始节点就表示循环结束，这个时候我们通过我们的目标节点在closedlist总通过父节点就能反向回去获得整条路径了。

不足之处

• 关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解
  互联网一线大厂面试题库

百度篇：链接：https://pan.baidu.com/s/140KuFVKGWcV6E6n52MdNXQ
提取码：b0p5