algorithm - 如何证明一个兼容的启发式可以是 A* 搜索算法中的一个可接受的启发式

Question

兼容启发式（h）是具有以下条件的启发式：

h(n) <= c(n,a,n') + h(n')

****************************************************

可接受的启发式（h）是具有以下条件的启发式：

0 <= h(n) <= h*(n)

nh*(n) 是节点到节点的实际距离goal

如果启发式是兼容的，如何证明它是可接受的？

非常感谢。

Answer 1

假设h(n)是不可接受的，因此存在一些顶点n使得h(n) > h*(n)。

但是由于h(n)的兼容性，我们知道对于所有n`它都满足h(n) <= c(n,a,n') + h(n')。

现在当n`是顶点G时结合这两个谓词来推导矛盾，从而证明所需的引理归约和荒谬。

Answer 2

如果在 h 上添加一个附加条件（即 h(goal) = 0），则可以通过从 n 到目标状态的最小成本路径上的归纳来证明它。

对于基本情况，当 n = 目标时，最小成本路径为 0。那么 h(goal) = 0 = h*(goal)。

对于一般情况，设 n 是一个节点，设 n' 是从 n 到目标的最小路径上的下一个节点。然后 h*(n) = c(n, n') + h*(n') >= c(n, n') + h(n') >= h(n) 使用归纳假设得到第一个不等式和相容性的定义为二。