启发搜索——A*算法原理

废话 

    用浏览器在网上搜索A*（A星）算法的实现，第一页一半是广告，该死的搜索引擎！！！剩下的只有几篇是内容互不相同的，其他全是复制粘贴一气呵成，半个字都不差！！！而能看的那几篇，又扯什么open表，close表，全篇很长，说不到重点上，看得头疼！！！

    但是我还是自己写出了A*算法，完成了作业。

    方法是什么？看书！

原理

    A*算法是一种搜索算法，可以高效地解决这样的问题：从一个初始状态到达一个目标状态。接下来就以迷宫寻路来说明A*算法的原理。

    要从入口到达出口，假设一次只能向上，下，左，右移动一格。

    （一）通常的做法是依次尝试，比如广度优先搜索，就是一层一层的尝试：

尝试到了第6层才找到出口，显然6层之前的所有格子都会被搜索到。

    （二）深度优先搜索，假设是按左上右下的顺序搜索，则它会一直往一个方向前进直到撞墙，然后后退：

看似比较快就找到出口，但是有点巧合。有趣的是，深度优先是把一条路走到底的，所以，要是开始的方向是错的，比如南辕北辙，那么它可能绕地球一圈后才找到出口！

    （三）A星搜索，A星的思想是：给每个可选的格子设置一个代价值，然后选择代价最低的格子尝试。代价 = 起点到那个格子的代价（已知）+ 那个格子到目标格子的代价（估计）

怎么估计呢？那要用常识，比如直线距离，或者曼哈顿距离，只需要保证那个估计的代价要比实际代价小就行了。比如上图入口到出口的直线距离是 根号18格，而根据规则，我们至少需要走6格才能到目的，那么这个估计就是好的。证明的话，大家去看书吧，我数学证明不太好。顺便说一下，考察邻近的格子称为扩展。

    怎么估计代价呢？适当减轻一下游戏规则。

    A星搜索过程如下：

 可以看到，A星基本是走直线方向的，而由于规则，所以实际的路径是阶梯型的。

总结
    A*的主要思想就是代价估计。

    估计函数可以根据适当放宽规则来设计，具体情况具体分析。大家可以试试把上述用直线距离估计代价改为用曼哈顿距离估计代价，效果应该会更好。曼哈顿距离就是水平直线距离加上垂直直线距离。

    A星算法考虑已经访问过了的格子也不会有问题，因为之前访问时和现在访问时，该格子的到达路径变长了。也就是这样：

这样的话，我们用一个哈希表记录已经访问过了的格子，以便可以不重复访问，那么可以极大的加快搜索速度。我作业里亲自体验了这两者的区别，允许重复的话，搜索次数1万左右，不允许重复则只需要循环630次。

    需要注意的是：选择代价最低的格子时，可选的格子并不是当前格子的周围格子，而是所有已经扩展过但是不重复的格子（也就是经过的格子的周围格子）。因为，可能你走了这条路走到一定时候发现后面格子的代价比之前没走的格子的代价还要大，那肯定是直接跳到那个格子啦，因为的因为，这只是模拟寻路，而不是真正的走路，所以可以跳跃。看图：

    我们位于起点时，估计A比B近，但是我们在A时，B比C近，所以，可选的应该时所以已经扩展的节点。

成功与失败

      要是有路径可以到达出口的话，只要代价估计不超过实际代价（可采纳），就肯定能找到出口。否则的话，就会搜索失败，失败的条件就是没有可扩展的格子了（无路可走）。

    搜索到了出口格子算是成功了，但是并不能保证路径最短。要保证路径最短，就需要估计当前情况下目的格子的代价，并使它的代价比其他可扩展格子的估计代价都小。

    所以真正的成功条件是：搜索到的目的格子代价是最低的。

    至于A星的代码实现，还是另一篇再说吧，因为画图真的很花时间，望大家能点个赞。