A*，那个传说中的算法
版权声明
本文版权属于：简单的老王 SimpleMain。如侵权请联系博主删除。
场景介绍
周日的下午，微信simplemain，老王又来找大伙儿聊技术了~~
今天想跟大家聊的，是我们经常用到，但是却让大家觉得十分神秘的那个算法：A* 。
想必大家都玩儿过对战类的游戏，老王读书那会儿，中午吃完饭就会跟几个好哥们儿一起来两局红警。后来升级了，玩儿星际（是不是暴露年龄了，哈哈~~）。
玩儿的时候，就会发现这里面的兵（为了方便描述，把坦克、飞艇、矿车、龙骑等统称为兵），你只要指定好地点，他们就会自己朝目的地进发，最终去向你指定的地点。不过红警的实现似乎要差一点，经常走绕路，然后在路上就莫名其妙被人干了……
于是，老王就对这个找路算法做了些研究，去查了查资料。所有的资料都一致显示，这些寻路算法，基本上使用的都是一个叫做A*的算法。不过当时看了算法，没有去实践，所以也没有太深入的思考，只是知道他是一种启发式的搜索算法，能够比较快的找到相对优的路径。说来也巧，后来因为百度的A-Star算法比赛进入百度实习，才了解了很多互联网相关的技术。
说在前面的话：因为老王不是做游戏的，游戏的寻路算法肯定有做各种优化，老王只是聊聊自己理解的A*算法，所以讲的不对的地方请专家们指正，专家们切勿生气_
好了，背景说完了，我们开始吧~
广度优先（BFS）和深度优先（DFS）搜索
在谈A*之前，还是要先聊聊搜索算法中的老祖宗，深度和广度优先搜索算法。这两个算法，基本上各教科书都会有讲解，各种面试基本上也都会面到。不过为了讲清楚A*，我们还是先一起来看看他们吧。
深度优先搜索，用俗话说就是不见棺材不回头。算法会朝一个方向进发，直到遇到边界或者障碍物，才回溯。一般在实现的时候，我们采用递归的方式来进行，也可以采用模拟压栈的方式来实现。
如下图，S代表起点，E代表终点。我们如果按照右、下、左、上这样的扩展顺序的话，算法就会一直往右扩张，直到走到地图的右边界，发现没找到目标点，然后再回溯。
深度优先搜索
这个算法的好处就是实现简单，可能就十几行代码。不过问题也很明显，就是：
- 路径可能不是最优解；
- 寻路时间比较长。
广度优先搜索
这个算法的优点：
- 简单。代码也就几十行；
- 路径能找到最优解；
不足：
- 算法消耗的时间比较大，遍历的点会很多。
这里就引出一个问题：为什么广度优先算法能找到最优路径，但是却很耗时呢？
A*算法
广度优先搜索之所以能找到最优的路径，原因就是每一次扩展的点，都是距离出发点最近、步骤最少的。如此这样递推，当扩展到目标点的时候，也是距离出发点最近的。这样的路径自然形成了最短的路线。
任何事情都有正反两面。正是由于广度优先搜索一层层的扩展，虽然让他找到了最优的路线，但是，他却很傻的走完了绝大多数格子，才找到我们的目标点。也就是，他只关注了当前扩展点和出发点的关系，而忽略了当前点和目标点的距离。如果，如果，如果……我们每扩展一个点，就踮起脚尖，看看诗和远方，找找我们要寻找的那个目标，是不是就有可能指引我们快速的去往正确的方向，而不用傻乎乎的一层层的发展了呢？
我们来看看下图：
同样是从出发点S走了两步以后到达的M1和M2两个点，如果让你来选择，你会选择他们中的谁来做扩展点呢？很明显，只要是眼力不差的人，都会选择M1。为什么呢？因为M2需要再走9步，才能到达终点E；而M1只需要7步！！！
注意了！我们的判断依据，除了考虑了中间这个点同出发点的距离以外，还考虑了这个点同目标点的距离，对吧~
如果你想到了这一点，恭喜你，你已经掌握了A*算法的秘诀了：A*算法相对广度优先搜索算法，除了考虑中间某个点同出发点的距离以外，还考虑了这个点同目标点的距离。这就是A*算法比广度优先算法智能的地方。也就是所谓的启发式搜索。
我们简单的抽象一下，如果用f(M)表示：从起点S到终点E（经过M点）的距离，那他就可以表示成为两段距离之和，即：S→M的距离 + M→E的距离。如果我们用符号表示的话，就可以写成：f(M) = g(M) + h(M)。
怎么样，看起来这个公式是否是很简单呢？
我们扩展到M点的时候，S→M的距离就已经知道，所以g(M)是已知的。但是M到E的距离我们还不知道。如果我们能用某种公式，能大概预测一下这个距离，而这个预测的值又比较精确，我们是不是就能很精确的知道每一个即将扩展的点是否是最优的解路径上的点呢？这样找起路来，是不是就很快呢？
所以，接下来最关键的问题，就是怎么计算这个h(M)的值！
可能大家都会问一个问题：从M→E的距离不是很好计算嘛？用横向的距离+纵向的距离就完了！
这个问题问的很好，但是结论是：既对，又不对。如果按照我们之前的图来看，这个结论是正确的。但是，如果是下面这张图呢？
在M和E之间，有一堵蓝色的墙，这个时候，M→E的距离，还是横向的直线距离 + 纵向的直线距离嘛？明显不是了，他需要绕道！
这个时候，似乎希望破灭了……
前两天有个朋友给我说，两口子的相处之道，就是相互包容，不要太较真儿。如果我们将这个思想用到这里，把h(M)看做一个估计的值，而不是精确值，那问题是不是就解决了呢？
也就是说，我们尽可能找那些f(M)=g(M)+h(M)小的点（其中h(M)是个估算值），当做我们的路径经过点，即使实际的h'(M)值可能和h(M)值不等也没关系，我们就当做一个参考（总比广度优先搜索好吧~）。如果通过这个估算，能干掉很多明显很差的点，我们也就节省了很多不必要的花销，也算赚到了，对吧！
比如，上图中， M点即使是绕路，也比M'点要强，对吧。在估算的时候，我们就可以将S左边的点基本上都抛弃掉，从而减少我们扩展的点数，节约计算的时间。
说完上面的东东，我们大面儿上的东西就说的差不多了，接下来就省两个问题要去解决了：
1. 这个估算的函数h(M)怎么样去计算？
2. 对于不同的估算函数h(M)来讲，对于我们的搜索结果会有什么样的影响？
那我么一个个的来回答吧。
估算函数h(M)如何计算？
常见的距离计算公式有这么几种：
1. 曼哈顿距离：这个名字听起来好高端，说白了，就是上面我们讲的横向格子数+纵向格子数；
2. 欧式距离：这个名字听起来也很高端，说白了，就是两点间的直线距离sqrt((x1-x2)2 + (y1-y2)2)。
除了上述的距离计算公式以外，还有一些变种的距离计算公式，如：对角线距离等等。这个就在具体的问题中做具体的优化了。
不同估算函数对于结果的影响
那距离公式选择不同，对我们的寻路结果有哪些影响呢？
-
当估算的距离h完全等于实际距离h'时，也就是每次扩展的那个点我们都准确的知道，如果选他以后，我们的路径距离是多少，这样我们就不用乱选了，每次都选最小的那个，一路下去，肯定就是最优的解，而且基本不用扩展其他的点。如下图：
- 如果估算距离h小于实际距离h'时，我们到最后一定能找到一条最短路径(如果存在另外一条更短的评估路径，就会选择更小的那个)，但是有可能会经过很多无效的点。极端情况，当h==0的时候，最终的距离函数就变成：
f(M)=g(M)+h(M)
=> f(M)=g(M)+0
=> f(M)=g(M)
- 如果估算距离h大于实际距离h'时，有可能就很快找到一条通往目的地的路径，但是却不一定是最优的解。
因此，A*算法最后留给我们的，就是在时间和距离上需要考虑的一个平衡。如果要求最短距离，则一定选择h小于等于实际距离；如果不一定求解最优解，而是要速度快，则可以选择h大于等于实际距离。
好了，口水话讲了这么多，来看代码吧。老王粘贴了最核心的那段代码，如下：
/**
* 搜索算法
*/
static void search()
{
final MinHeap heap = new MinHeap(); // 用最小堆来记录扩展的点
final int[][] directs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 可以扩展的四个方向
heap.add(new Data(START_PNT, 0, 0, null)); // 把起始点放入堆
Data lastData = null; // 找到的最后一个点的数据,用来反推路径
for (boolean finish = false; !finish && !heap.isEmpty(); )
{
final Data data = heap.getAndRemoveMin(); // 取出f值最小的点
final Point point = data.point;
if (MAP[point.x][point.y] == SPACE) // 将取出的点标识为已访问点
{
MAP[point.x][point.y] = VISITED;
}
for (int[] d : directs) // 遍历四个方向的点
{
final Point newPnt = new Point(point.x + d[0], point.y + d[1]);
if (newPnt.x >= 0 && newPnt.x < MAX_PNT.x && newPnt.y >= 0 && newPnt.y < MAX_PNT.y)
{
char e = MAP[newPnt.x][newPnt.y];
if (e == END) // 如果是终点,则跳出循环,不用再找
{
lastData = data;
finish = true;
break;
}
if (e != SPACE) // 如果不是空地,就不需要再扩展
{
continue;
}
final Data inQueueData = heap.find(newPnt);
if (inQueueData != null) // 如果在堆里,则更新g值
{
if (inQueueData.g > data.g + 1)
{
inQueueData.g = data.g + 1;
inQueueData.parent = data;
}
}
else // 如果不在堆里,则放入堆中
{
double h = h(newPnt);
Data newData = new Data(newPnt, data.g + 1, h, data);
heap.add(newData);
}
}
}
}
// 反向找出路径
for (Data pathData = lastData; pathData != null; )
{
Point pnt = pathData.point;
if (MAP[pnt.x][pnt.y] == VISITED)
{
MAP[pnt.x][pnt.y] = ON_PATH;
}
pathData = pathData.parent;
}
}
完整的代码请参见老王的github：
https://github.com/simplemain/astar
（也可以点击左下角“阅读原文”查看）
老王定义了一张地图:
// 地图元素
static final char START = 'S'; // 起点
static final char END = 'E'; // 终点
static final char SPACE = '.'; // 空地
static final char WALL = 'W'; // 墙
static final char VISITED = '-'; // 被访问过
static final char ON_PATH = '@'; // 在结果路径上
// 地图字符串
static final String[] S_MAP = {
". . . . . . . . . . . . . . . . . . . .",
". . . W W W W . . . . . . . . . . . . .",
". . . . . . W . . . . . . . . . . . . .",
". . . . . . W . . . . . . . . . . . . .",
". . S . . . W . . . . . . . . . . . . .",
". . . . . . W . . . . . . . . . . E . .",
". . . . . . W . . . . . . . . . . . . .",
". . . . . . W . . . . . . . . . . . . .",
". . . W W W W . . . . . . . . . . . . .",
". . . . . . . . . . . . . . . . . . . ."
};
当用以下距离公式计算h值的时候，效果如图：
(需要说明的是 - 表示已经被搜索，@表示选择的路径，.则是没有被搜索)
- 曼哈顿距离：
. . - - - - - - - . . . . . . . . . . .
. - - W W W W - - . . . . . . . . . . .
- - - - - - W - - - - . . . . . . . . .
- - - - - - W - - . - - - - - . . . . .
- - S - - - W - - - - - - - - . . . . .
- - @ - - - W - - - - - - - - - . E . .
- - @ - - - W - - - @ @ @ @ @ @ @ @ . .
- - @ - - - W @ @ @ @ - - - . . . . . .
. - @ W W W W @ . . . . . . . . . . . .
. . @ @ @ @ @ @ - - - . . . . . . . . .
很明显，大部分的空白点都没有去遍历，而且最终找到了最优的路径。
- 欧式距离：
- - - - - - - - - - - - - - - - - . . .
- - - W W W W - - - - - - - - - - . . .
- - - - - - W - - - - - - - - - - . . .
- - - - - - W - - - - - - - - - - . . .
- - S - - - W - - - - - - - - - - . . .
- - @ - - - W . . . . . . . . . . E . .
- - @ - - - W - - - - - - - - @ @ @ . .
- - @ - - - W - - - - - - - - @ - . . .
- - @ W W W W - - - - - - - @ @ - . . .
. - @ @ @ @ @ @ @ @ @ @ @ @ @ - - . . .
同曼哈顿距离一样，效果差不多，不过多扩展了几个点。
- 欧式距离的平方
. . . . . . . . . . . . . . . . . . . .
. . - W W W W . . . . . . . . . . . . .
. . - - - - W . . . . . . . . . . . . .
. . - - - - W . . . . . . . . . . . . .
. . S - - - W . . . . . . . . . . . . .
. . @ - - - W . . . . . . . . . . E . .
. . @ - - - W . . . . . . . . . @ @ . .
. . @ - - - W . . . . . . . . @ @ . . .
. . @ W W W W . . . . . . . @ @ . . . .
. . @ @ @ @ @ @ @ @ @ @ @ @ @ . . . . .
这种情况就是h值大于等于实际距离的，明显他扩展的点很少，不过找到的路径却不是最短路径。
4、BFS的情况（h值恒为0）
这种算法基本等同于BFS，所有点基本都被扩展了，但是还是找到了最优的那个路径。
- - - - - - - - - - - - - - - - - - - -
- - - W W W W - - - - - - - - - - - - -
- - - - - - W - - - - - - - - - - - - .
- - - - - - W - - - - - - - - - - - . .
- - S - - - W - - - - - - - - - - . . .
- - @ - - - W - - - - - - - - - . E . .
- - @ - - - W - - - - - - - - - - @ . .
- - @ - - - W - - - - - - - - @ @ @ . .
- - @ W W W W - - - - - - - @ @ - - - .
- - @ @ @ @ @ @ @ @ @ @ @ @ @ - - - - -
好了，以上就是今天的内容，你看懂了嘛？如果觉得老王讲的还有点意思，就请继续关注老王的微信吧，每周固定时间，不见不散哦
老王微信公众号
