A是什么算法

① 什么是A搜索算法

A*搜索算法，俗称A星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

② 人工智能 A*算法原理

A 算法是启发式算法重要的一种，主要是用于在两点之间选择一个最优路径，而A 的实现也是通过一个估值函数

上图中这个熊到树叶的 曼哈顿距离 就是蓝色线所表示的距离，这其中不考虑障碍物，假如上图每一个方格长度为1，那么此时的熊的曼哈顿距离就为9.
起点（X1,Y1）,终点（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我们也可以通过几何坐标点来算出曼哈顿距离，还是以上图为例，左下角为（0，0）点，熊的位置为（1，4），树叶的位置为（7，1），那么H=|7-1|+|1-4|=9。

还是以上图为例，比如刚开始熊位置我们会加入到CLOSE列表中，而熊四周它可以移动到的点位我们会加入到OPEN列表中，并对熊四周的8个节点进行F=G+H这样的估值运算，然后在这8个节点中选中一个F值为最小的节点，然后把再把这个节点从OPEN列表中删除，加入到Close列表中，从接着在对这个节点的四周8个节点进行一个估值运算，再接着依次运算，这样说大家可能不是太理解，我会在下边做详细解释。

从起点到终点，我们通过A星算法来找出最优路径

我们把每一个方格的长度定义为1，那从起始点到5位置的代价就是1，到3的代价为1.41，定义好了我们接着看上图，接着运算

第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算，运算结果如上图，这其中大家看到一个小箭头都指向了起点，这个箭头就是指向父节点，而open列表的G值都是根据这个进行计算的，意思就是我从上一个父节点运行到此处时所需要的总代价，如果指向不一样可能G值就不一样，上图中我们经过计算发现1点F值是7.41是最小的，那我们就选中这个点，并把1点从OPEN列表中删除，加入到CLOSE列表中，但是我们在往下运算的时候发现1点的四周，2点，3点和起始点这三个要怎么处理，首先起始点已经加入到了CLOSE，他就不需要再进行这种运算，这就是CLOSE列表的作用，而2点和3点我们也可以对他进行运算，2点的运算，我们从1移动到2点的时候，他需要的代价也就是G值会变成2.41，而H值是不会变的F=2.41+7=9.41，这个值我们发现大于原来的的F值，那我们就不能对他进行改变（把父节点指向1，把F值改为9.41，因为我们一直追求的是F值最小化），3点也同理。

在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41，此时我们系统就可能随机选择一个点然后进行下一步运算，现在我们选中的是3点，然后对3点的四周进行运算，结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大，所以不发生改变。我们在看整个OPEN列表中，也就2点的7.41值是最小的，那我们就选中2点接着运算。

我们在上一部运算中选中的是1点，上图没有把2点加入OPEN列表，因为有障碍物的阻挡从1点他移动不到2点，所以没有把2点加入到OPEN列表中，整个OPEN列表中3的F=8是最小的，我们就选中3，我们对3点四周进行运算是我们发现4点经过计算G=1+1=2，F=2+6=8所以此时4点要进行改变，F变为8并把箭头指向3点（就是把4点的父节点变为3），如下图

我们就按照这种方法一直进行运算，最后 的运算结果如下图

而我们通过目标点位根据箭头（父节点），一步一步向前寻找最后我们发现了一条指向起点的路径，这个就是我们所需要的最优路径。 如下图的白色选中区域

但是我们还要注意几点

最优路径有2个

这是我对A*算法的一些理解，有些地方可能有BUG，欢迎大家指出，共同学习。

③ A*算法优化

A算法是游戏中路径搜索的常见算法。Dijkstra是最短路径的经典算法，A算法的思路基本上和Dijkstra算法一致，在Dijkstra算法的基础上增加了启发函数，也就是：

f(n) = g(n) + h(n)

其中，n是路径上某一点，g(n)是从出发点到该点的cost，h(n)是关于该点的启发函数，通常是对从该点到目标花费的一个估计，例如到目标的直线距离或者曼哈顿距离。 A算法每次选择f(n)最小的点，然后更新所有g(n)。
如果你明白Dijkstra算法，那么在这里h(n) = 0 的话，A算法就和Dijkstra算法一样了。
本文不详细讲解A算法，需要详细了解A算法的具体过程的，参见以下两篇文章：

理解A*算法的具体过程
A*算法详解

A*算法优化的关键在于h(n)的选择。 一个启发函数h(n)被称为admissible的，是指h(n)的估计，不会超过节点N到目标的实际花费。
如果h(x)满足以下条件，h(x)被称为单调的(monotone, or consistent)。 对于任意一条边(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的长度

如果满足这个条件，就意味着没有任何节点需要被处理多次，也就是说，在Dijkstra算法中，新加入一个节点会导致已添加节点中cost降低的情况不会存在，也就不需要去更新已添加节点(称为close set)。

如果一个启发函数是单调的，那么该启发函数一定是admissible的。如果该启发函数是admissible的，那么可以证明A*在同类算法中搜寻到最短的路径。

问题出在这里：如果我们更在意的是搜索的时间空间花费，而不是最优结果，那么A*算法就有优化空间。所以我们放松要求，修改我们的启发函数，使得我们搜寻到的路径不会比最佳路径差太多，就是优化算法，称为ε-admissible算法。

有多种ε-admissible算法，在此只举例最简单直接的一种： 加权A*(静态加权)算法。

假如ha(n)是一个admissible的启发函数，我们选取新的启发函数hw(n) = ε ha(n)，其中ε>1 作为启发函数。就可以在某种程度上进行优化。 下图1是使用ha(n)作为启发式算法，下图2是使用hw(n)作为启发式算法，其中ε取5.

图1：ha(x)作为启发算法

图2：hn(x)作为启发算法

可以看出，ha(n)可以找到最小路径，但是多了许多无用的搜索；而hw(n)找到的不是最优路径，但是减少了大量无用搜索。
其他的优化算法思路类似都是在于启发函数的选择。详见参考文献。

参考文献：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic