嗨！大家好，我是小蚂蚁。
上一节里我们讲了寻路算法的发展历程，从低效率的广度优先查找算法，发展到为了解决不同的地形因素引入了“成本”概念的Dijkstra算法，再到为了提升查找效率引入“启发式查找”的最佳优先搜索算法，最终进化出了结合“成本”和“启发式查找”的A*算法。
这一节，我们就深入A*算法，了解它的查找过程，知晓它的查找原理。
几个概念
在正式开始之前，我们先来了解几个概念，这些概念对于接下来了解A*算法的查找原理非常重要。
实际代价
实际代价其实就是Dijkstra算法中的“成本”(这里我们给它换了一个名字)，它指的是从起点位置移动到当前位置所需要的代价。
举个例子，如图，兔子位置是起点位置，我们假设每个格子的长度为 1，计算兔子到1，2，3号位置的实际代价，位置1和位置2分别位于兔子的左侧和下侧相邻的格子，所以兔子移动到位置1和位置2的实际代价相同，都是 1。位置3是位于右上方的格子，兔子移动到位置3的距离是等腰直角三角形的斜边，也就是√2。
实际代价在具体使用时其实是一个数字，数字越大表示移动到这个位置上所需要的代价越高。
估计代价
估计代价是最佳优先搜索算法中提到的“启发式查找”（又换了一个名字），它指的是从当前位置移动到目标位置所需要的代价。
如图，还是有1，2，3的三个位置，每个位置的估计代价就是当前位置到目标位置的直线距离，很明显可以看出位置2的估计代价最小，位置1次之，位置3最大。兔子想要找到胡萝卜，选择移动到估计代价最小的位置2更好。
估价函数
估价函数指的就是实际代价与估计代价的总和。
如图，蓝线的总长度是移动到位置1的估价，绿线的总长度是移动到位置2的估价，橙线的总长度是移动到位置3的估价。在通过估价函数计算得到将要移动到的所有位置的估价值之后，做一个比较，选择向估价值最小的那个位置（位置2）移动。
估价函数是A*算法的计算基础，通常使用 f(n) 表示估价函数，g(n) 表示实际代价，h(n) 表示估计代价，最终的估价函数的计算公式是这样：
f(n) = g(n) + h(n)
g(n) 表示当前位置到起点位置的实际代价值。
h(n) 表示当前位置到目标位置的估计代价值。
f(n) 表示当前位置的最终估价值。
该篇文章为付费教程，剩余部分可前往公众号中付费阅读。
