兼容启发式(h)是具有以下条件的启发式:
h(n) <= c(n,a,n') + h(n')
****************************************************
可接受的启发式(h)是具有以下条件的启发式:
0 <= h(n) <= h*(n)
n
h*(n) 是节点到节点的实际距离goal
如果启发式是兼容的,如何证明它是可接受的?
非常感谢。
兼容启发式(h)是具有以下条件的启发式:
h(n) <= c(n,a,n') + h(n')
****************************************************
可接受的启发式(h)是具有以下条件的启发式:
0 <= h(n) <= h*(n)
n
h*(n) 是节点到节点的实际距离goal
如果启发式是兼容的,如何证明它是可接受的?
非常感谢。
假设h(n)是不可接受的,因此存在一些顶点n使得h(n) > h*(n)。
但是由于h(n)的兼容性,我们知道对于所有n`它都满足h(n) <= c(n,a,n') + h(n')。
现在当n`是顶点G时结合这两个谓词来推导矛盾,从而证明所需的引理归约和荒谬。
如果在 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) 使用归纳假设得到第一个不等式和相容性的定义为二。