《人工智能：线代方法》 第二部分问题求解 通过搜索进行问题求解(4)
3.6 启发式函数
启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。
3.6.1 启发式函数的准确性对性能的影响
启发式函数可以控制A*的行为：
一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到最短路径。
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。
如果h(n)精确地等于从n移动到目标的代价，则A将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A会运行得很完美，认识这一点很好。
如果h(n)有时比从n移动到目标的实际代价高，则A不能保证找到一条最短路径，但它运行得更快。
另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A演变成BFS算法。
所以我们得到一个很有趣的情况，那就是我们可以决定我们想要从A中获得什么。理想情况下（注：原文为At exactly the right point），我们想最快地得到最短路径。如果我们的目标太低，我们仍会得到最短路径，不过速度变慢了；如果我们的目标太高，那我们就放弃了最短路径，但A*运行得更快。
在游戏中，A*的这个特性非常有用。例如，你会发现在某些情况下，你希望得到一条好的路径（"good" path）而不是一条完美的路径（"perfect" path）。为了权衡g(n)和h(n)，你可以修改任意一个。
注:在学术上，如果启发式函数值是对实际代价的低估，A算法被称为简单的A算法（原文为simply A）。然而，我继续称之为A，因为在实现上是一样的，并且在游戏编程领域并不区别A和A*。
启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。
2.1 A对启发式函数的使用
启发式函数可以控制A的行为：
一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到最短路径。
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。
如果h(n)精确地等于从n移动到目标的代价，则A将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A会运行得很完美，认识这一点很好。
如果h(n)有时比从n移动到目标的实际代价高，则A不能保证找到一条最短路径，但它运行得更快。
另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A演变成BFS算法。
所以我们得到一个很有趣的情况，那就是我们可以决定我们想要从A中获得什么。理想情况下（注：原文为At exactly the right point），我们想最快地得到最短路径。如果我们的目标太低，我们仍会得到最短路径，不过速度变慢了；如果我们的目标太高，那我们就放弃了最短路径，但A*运行得更快。
在游戏中，A*的这个特性非常有用。例如，你会发现在某些情况下，你希望得到一条好的路径（"good" path）而不是一条完美的路径（"perfect" path）。为了权衡g(n)和h(n)，你可以修改任意一个。
注:在学术上，如果启发式函数值是对实际代价的低估，A算法被称为简单的A算法（原文为simply A）。然而，我继续称之为A，因为在实现上是一样的，并且在游戏编程领域并不区别A和A*。
2.2 速度还是精确度？
A*改变它自己行为的能力基于启发式代价函数，启发式函数在游戏中非常有用。在速度和精确度之间取得折衷将会让你的游戏运行得更快。在很多游戏中，你并不真正需要得到最好的路径，仅需要近似的就足够了。而你需要什么则取决于游戏中发生着什么，或者运行游戏的机器有多快。
假设你的游戏有两种地形，平原和山地，在平原中的移动代价是1而在山地则是3。A* is going to search three times as far along flat land as it does along mountainous land. 这是因为有可能有一条沿着平原到山地的路径。把两个邻接点之间的评估距离设为1.5可以加速A的搜索过程。然后A会将3和1.5比较，这并不比把3和1比较差。It is not as dissatisfied with mountainous terrain, so it won't spend as much time trying to find a way around it. Alternatively, you can speed up up A's search by decreasing the amount it searches for paths around mountains―just tell A that the movement cost on mountains is 2 instead of 3. Now it will search only twice as far along the flat terrain as along mountainous terrain. Either approach gives up ideal paths to get something quicker.
速度和精确度之间的选择前不是静态的。你可以基于CPU的速度、用于路径搜索的时间片数、地图上物体（units）的数量、物体的重要性、组（group）的大小、难度或者其他任何因素来进行动态的选择。取得动态的折衷的一个方法是，建立一个启发式函数用于假定通过一个网格空间的最小代价是1，然后建立一个代价函数（cost function）用于测量（scales）：
g’(n) = 1 + alpha * ( g(n) – 1 )
如果alpha是0，则改进后的代价函数的值总是1。这种情况下，地形代价被完全忽略，A工作变成简单地判断一个网格可否通过。如果alpha是1，则最初的代价函数将起作用，然后你得到了A的所有优点。你可以设置alpha的值为0到1的任意值。
你也可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价。例如，如果你的地图大部分地形是代价为2的草地，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2*距离。
速度和精确度之间的选择并不是全局的。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，因此为何要对后续路径的精确度感到厌烦？或者，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个敌人的村庄逃跑时，安全和速度是最重要的。（译者注：译者认为这里指的是，在安全区域，可以考虑不寻找精确的最短路径而取近似路径，因此寻路快；但在危险区域，逃跑的安全性和逃跑速度是重要的，即路径的精确度是重要的，因此可以多花点时间用于寻找精确路径。）
2.3 衡量单位
A计算f(n) = g(n) + h(n)。为了对这两个值进行相加，这两个值必须使用相同的衡量单位。如果g(n)用小时来衡量而h(n)用米来衡量，那么A将会认为g或者h太大或者太小，因而你将不能得到正确的路径，同时你的A*算法将运行得更慢。
2.4 精确的启发式函数
如果你的启发式函数精确地等于实际最佳路径（optimal path），如下一部分的图中所示，你会看到此时A扩展的结点将非常少。A算法内部发生的事情是：在每一结点它都计算f(n) = g(n) + h(n)。当h(n)精确地和g(n)匹配（译者注：原文为match）时，f(n)的值在沿着该路径时将不会改变。不在正确路径（right path）上的所有结点的f值均大于正确路径上的f值（译者注：正确路径在这里应该是指最短路径）。如果已经有较低f值的结点，A*将不考虑f值较高的结点，因此它肯定不会偏离最短路径。
2.4.1 预计算的精确启发式函数
构造精确启发函数的一种方法是预先计算任意一对结点之间最短路径的长度。在许多游戏的地图中这并不可行。然后，有几种方法可以近似模拟这种启发函数：
Fit a coarse grid on top of the fine grid. Precompute the shortest path between any pair of coarse grid locations.
Precompute the shortest path between any pair of waypoints. This is a generalization of the coarse grid approach.
（译者：此处不好翻译，暂时保留原文）
然后添加一个启发函数h’用于评估从任意位置到达邻近导航点（waypoints）的代价。（如果愿意，后者也可以通过预计算得到。）最终的启发式函数可以是：
h(n) = h'(n, w1) + distance(w1, w2), h'(w2, goal)
或者如果你希望一个更好但是更昂贵的启发式函数，则分别用靠近结点和目标的所有的w1,w2对对上式进行求值。（译者注：原文为or if you want a better but more expensive heuristic, evaluate the above with all pairs w1, w2 that are close to the node and the goal, respectively.）
2.4.2 线性精确启发式算法
在特殊情况下，你可以不通过预计算而让启发式函数很精确。如果你有一个不存在障碍物和slow地形，那么从初始点到目标的最短路径应该是一条直线。
如果你正使用简单的启发式函数（我们不知道地图上的障碍物），则它应该和精确的启发式函数相符合（译者注：原文为match）。如果不是这样，则你会遇到衡量单位的问题，或者你所选择的启发函数类型的问题。