可接受的启发式

在计算机科学中，特别是在与寻路有关的算法中，如果一个启发式函数从未高估过到达目标的成本，即它估计的到达目标的成本不高于从路径中的当前点出发的最低可能成本，则称其为可接受。它与一致启发式的概念有关。虽然所有一致的启发式方法都是可接受的，但并非所有可接受的启发式方法都是一致的。

一个可接受的启发式方法被用来估计在知情搜索算法中到达目标状态的成本。为了使启发式对搜索问题是可接受的，估计的成本必须总是低于或等于到达目标状态的实际成本。搜索算法使用可接受的启发式来寻找从当前节点到目标状态的估计最佳路径。例如，在A*搜索中，评估函数（其中是用启发式函数计算的。在非允许启发式的情况下，A*算法可能会由于高估了f(n)而忽略了搜索问题的最优解。

一个可接受的启发式方法可以从问题的宽松版本中推导出来，也可以通过存储问题子问题精确解的模式数据库的信息，或者使用归纳学习方法。

两个不同的可接受启发式方法的例子适用于15个拼图问题。

曼哈顿距离汉明距离是指错位瓷砖的总数。很明显，这个启发法是可接受的，因为正确排列瓷砖的总步数至少是错位瓷砖的数量（每块未到位的瓷砖必须至少移动一次）。实现目标（一个有序的拼图）的成本（移动次数）至少是拼图的汉明距离。一个谜题的曼哈顿距离定义为考虑下面的谜题，玩家希望移动每张牌，使其数字有序。在这种情况下，曼哈顿距离是一种可接受的启发式方法，因为每张牌至少要在它自己和它的正确位置之间移动多少个位置。下标显示的是每张牌的曼哈顿距离。所示谜题的总曼哈顿距离是。

如果一个可接受的启发式被用在一个算法中，该算法每次迭代只推进几条候选路径中评价最低的路径（当前成本+启发式），在其探索到达目标的那一刻终止，关键是，在终止前从不关闭所有最优路径（如果不特别注意，A*搜索算法也有可能），那么这个算法只能在一条最优路径上终止。要知道为什么，请考虑下面的矛盾证明。假设这样的算法能够在一条真实成本Ttrue大于真实成本S的最优路径上终止。这意味着在终止之前，T的评估成本小于或等于S的评估成本（否则S会被选中）。分别表示这些评估成本Teval和Seval。上述情况可以总结为以下几点。如果我们的启发式是可接受的，那么在倒数第二步，Teval=Ttrue，因为启发式对T的真实成本的任何增加都是不可接受的，而且启发式不能是负的。另一方面，一个可接受的启发式需要Seval≤Strue，结合上述不等式，我们可以得到Teval＜Ttrue，更确切地说，Teval≠Ttrue。由于Teval和Ttrue不可能既相等又不相等，我们的假设一定是错误的，所以一定不可能终止于一条比最优路径更昂贵的路径上。