想想A*的停止条件,如果算法到达目标节点时 F 值,其中 F 等于 G -到目前为止从起点构建的路径加上启发式值 H 其表示到目标的剩余路径的估计。

在目标节点处, F 等于 G 因为到达目标的剩余路径的估计是0。

只有在以下情况下,停止条件才有效 H 是可接受的,从那时起,我们可以确定 F 我们在目标节点计算的值比其他任何节点都小 F 我们在任何其他节点中计算的值,我们肯定可以确定它是最短的路径,因为没有其他路径可以通过较小的 F 价值

如果它是不可接受的,那么我们可能会为其他节点计算 F 由于高估了通往目标的剩余路径,我们无法停止算法,因为可能存在较短的路径。

对于那些不寻求免费和无偿提供资源的人。

在计算机科学中,特别是与 寻路,如果启发式函数从来没有被认为是可接受的 高估了实现目标的成本,即 达到目标的估计值不高于可能的最低值 路径中当前点的成本。一个可接受的启发式是 也被称为乐观启发式。

这是维基百科的链接:

http://en.wikipedia.org/wiki/Admissible_heuristic

关于第二个问题

当启发式算法没有高估真实成本时,它是可以接受的,因为它是这样定义的。